针对恶劣天气条件下可用空域资源不足导致的航班大面积延误问题，基于复杂网络修复理论和交通流分配理论，借鉴交通网络设计思想提出了一种航路网络修复优化策略。首先，建立了航路网络修复场景，基于气象信息生成了恶劣天气飞行受限区。然后，建立了上层模型以修复成本最低为目标函数、下层模型为多约束交通流分配模型的双层规划修复模型，应用改进粒子群算法对模型整体进行求解，结合K最短路径算法对下层模型进行求解。最后，提出局部和全局两类指标对航路网络修复效果进行评估。基于典型航路网络，以两类基础修复策略为对比方法，同时对比了实际运行结果，研究了不同修复策略的修复效果和适用性。仿真结果表明：航路网络修复优化策略既能弥补原有拓扑结构修复策略的结构受限不足，又能解决拓扑结构调整修复策略带来的巨额协调费用问题，能够保证在对正常运行航班干扰最小的同时，以最小的修复成本使所有受影响的航班都恢复正常运行，对于减缓航路拥堵和航班延误有极大的意义。
Aiming at the problem of large-scale flight delays caused by insufficient airspace resources under severe weather conditions, this paper proposes a repair optimization strategy for air route networks based on the complex network repair theory and traffic flow distribution theory and drawing on the traffic network design theory. The repair scenario of the air route network is first established, and the flight constrained area in severe weather generated based on weather information. A bi-level programming repair model is then constructed, in which the upper model takes the lowest repair cost as the objective function, and the lower model is the multi-constrained traffic flow distribution model. The improved particle swarm optimization algorithm and the K shortest path algorithm are applied to solving the whole model and the lower model, respectively. Finally, two types of indicators are proposed to evaluate the repair effect of the air route network from both the local and global perspectives. Based on the typical route network, two basic repair strategies are compared, and the actual operation results compared to study the repair effect and applicability of different repair strategies. The simulation results show that the air route network repair optimization strategy can not only make up for the structural limitation of the repair strategy based on original topology, but also solve the problem of the additional coordination cost brought by the repair strategy based on adjustment topology. The proposed repair optimization strategy minimizes the disruption to normal flight operations and restores all affected flights to normal operation with minimum repair costs, exhibiting considerable significance in mitigating route congestion and flight delays.
[1] 中国民用航空局. 2018年民航行业发展统计公报[N]. 中国民航报, 2019-05-10(002). Civil Aviation Administration of China. Statistical bulletin of china's civil aviation industry development in 2018[N]. Civil Aviation Administration of China News, 2019-05-10(002) (in Chinese).
[2] 中国民用航空局. 中国民航基于性能的导航实施路线图[M]. 北京:中国民用航空局, 2009:10. Civil Aviation Administration of China. Performance based navigation implementation roadmap of CAAC[M]. Beijing:Civil Aviation Administration of China, 2009:10(in Chinese).
[3] KODIALAM M, LAKSHMAN T V. Dynamic routing of bandwidth guaranteed tunnels with restoration[C]//Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway:IEEE Press, 2000:902-911.
[4] LI G I, WANG D M, KALMANEK C, et al. Efficient distributed restoration path selection for shared mesh restoration[J]. IEEE Transactions on Networking, 2003, 11(5):761-771.
[5] 缪志敏, 丁力, 赵陆文, 等. 基于拓扑信息的网络修复[J]. 计算机工程, 2008, 34(5):25-27, 30. MIAO Z M, DING L, ZHAO L W, et al. Network restoration based on topological information[J]. Computer Engineering, 2008, 34(5):25-27, 30(in Chinese).
[6] BEYGELZIMER A, GRINSTEIN G, LINSKER R, et al. Improving network robustness by edge modification[J]. Physica A:Statistical Mechanics and Its Applications, 2005, 357(3-4):593-612.
[7] ZHANG S, LIANG M G, JIANG Z Y, et al. Effective strategy of adding links for improving network transport effective on complex networks[J]. International Journal of Modern Physics C, 2014, 25(6):1450014.
[8] 齐小刚, 张碧雯, 刘立芳, 等. 复杂信息网络的弹性评估和优化方法研究[J]. 计算机科学与探索, 2018, 12(8):1252-1262. QI X G, ZHANG B W, LIU L F, et al. Evaluation and optimization of complex network resilience against attacks[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(8):1252-1262(in Chinese).
[9] HAYASHI Y, MIYAZAKI T. Emergent rewirings for cascades on correlated networks[J]. E-print ArXiv, 2005:cond-mat/0503615.
[10] MA J L, HAN W Z. A link-adding strategy for transport efficiency of complex networks[J]. International Journal of Modern Physics C, 2016, 27(5):1650054.
[11] RHODA D A, PAWLAK M L. The thunderstorm penetration/deviation decision in the terminal area[C]//8th Conference on Aviation, Range, and Aerospace Meteorology (ARAM). Dallas:The American Meteorological Society, 1999:8-17.
[12] 王兴隆, 徐肖豪, 李慧. 改航策略中雷暴飞行受限区划设方法[J]. 科学技术与工程, 2013, 13(10):2906-2910. WANG X L, XU X H, LI H. Planning method of thunderstorms flight restricted area in rerouting policy[J]. Science Technology and Engineering, 2013, 13(10):2906-2910(in Chinese).
[13] 谢春生, 李雄. 危险天气影响航路飞行区域的划设及评估[J]. 中国安全科学学报, 2010, 20(10):47-52. XIE C S, LI X. Division and evaluation of flight forbidden area in severe weather[J]. China Safety Science Journal, 2010, 20(10):47-52(in Chinese).
[14] KROZEL J, PENNY S, PRETE J, et al. Automated route generation for avoiding deterministic weather in transition airspace[J]. Journal of Guidance, Control, and Dynamics, 2007, 30(1):144-153.
[15] GRAHAM R. An efficient algorithm for determining the convex hull of a finite planar set[J]. Information Processing Letters, 1972, 1(4):132-133.
[16] 刘灿齐. 现代交通规划学[M]. 北京:人民交通出版社, 2002:303-306. LIU C Q. Advanced traffic planning[M]. Beijing:China Communications Press, 2002:303-306(in Chinese).
[17] KROZEL J, LEE C, MITCHELL J S B. Estimating time of arrival in heavy weather conditions[C]//AIAA Guidance, Navigation, and Control Conference. Reston:AIAA, 1999:1481-1495.
[18] SHI Y, EBERHART R. A modified particle swarm ptimizer[C]//IEEE World Congress on Computational Intelligence. Piscataway:IEEE Press, 1998:69-73.
[19] 张好智, 高自友. 可变车道的道路交通网络设计优化方法[J]. 中国管理科学, 2007(2):86-91. ZHANG H Z, GAO Z Y. Design optimization method of variable lane road traffic network[J]. China Management Science, 2007(2):86-91(in Chinese).
[20] ZHANG H Z, GAO Z Y. Optimization approach for traffic road network design problem[J]. Chinese Journal of Management Science, 2007(2):86-91.
[21] YEN J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17:712-716.
[22] 何大韧, 刘宗华, 汪秉宏. 复杂系统与复杂网络[M]. 北京:高等教育出版社, 2009:124-125. HE D R, LIU Z H, WANG B H. Complex systems and complex networks[M]. Beijing:Higher Education Press, 2009:124-125(in Chinese).
CJA