基于改进匈牙利算法的航路网络延误优化  

Optimization of en-route network delay based on improved Hungarian algorithm

作　　者：王莉莉 王航臣 Wang Lili;Wang Hangchen(China Tianjin Key Laboratory of ATC Operation Planning&Safety Technology,Civil Aviation University of China,Tianjin 300300,China)

机构地区：[1]中国民航大学天津市空管运行规划与安全技术重点实验室,天津300300

出　　处：《计算机应用研究》2020年第3期759-762,共4页Application Research of Computers

基　　金：国家自然科学基金与中国民用航空局联合基金资助项目(U1633124);国家自然科学基金资助项目(41501430)。

摘　　要：针对我国航路网络流量分配依靠管制员经验,缺乏量化模型协助决策这一问题,对航路网络的延误优化模型及其求解算法展开研究。首先,建立了目标函数为总航行时间最小、带容量约束的流量指派模型;其次,针对经典匈牙利算法只适用于中小型运算的问题,在效率矩阵的计算上作出加圈的零元素个数最大概率与效率矩阵的阶数相等的改进;再次,根据航路运行效率随时间和流量变化的特点,使用M/M/C排队论模型构建了航路的费用函数,用变化的费用替代效率矩阵中不变的效率值,使效率矩阵随时间和流量变化;最后,以中南空管局与西南空管局2016年11月部分空域的实际运行数据作为算例验证该模型与算法。结果表明,在通行能力优化方面,算法能将进场通行能力提升8.372%,离场通行能力提升8.999%;在延误优化方面,能降低每架航空器平均延误;在算法性能方面,具有比经典匈牙利算法迭代次数少、求解时间短的优点,更适用于实际的管制运行。Due to cope with relying on controllers badly and lacking of quantitative models to assist decision-making in air traffic flow management,this paper studied the delay optimization model and its solving algorithm for route network.Firstly,it established a traffic flow assignment model with the objective function of minimum flight time and capacity constraints.Secondly,considering that classical Hungarian algorithm was only suitable for small and medium-sized operations,it made the improvement of the calculation of efficiency matrix by making the maximum probability of the number of zero elements in the cirde equal to the order of the efficiency matrix.Next,it constructed the cost function of the en-route by using the M/M/C queuing theory model.The function,which replaced the constant efficiency value in the efficiency matrix with a variable cost,made the efficiency matrix change with time and flow.Finally,it took part airspaces of China and the actual operational data of 2016 as exa-mples.The results show that the algorithm can increase the access capacity by 8.372%and the departure capacity by 8.999%;In terms of delay optimization,it can reduce the average delay of each aircraft.In terms of algorithm performance,it has less ite-rations and less solution time than the classical Hungarian algorithm,and is more suitable for actual control operation.

关 键 词：航空运输 延误优化 匈牙利算法 航路网络 指派问题 费用函数 

分 类 号：V355.1[航空宇航科学与技术—人机与环境工程] TP391.9[自动化与计算机技术—计算机应用技术]