基于模拟退火算法的单机场地面等待优化策略
2019-05-13张虹熊静黄晓丹尤阔阔张文成
张虹 熊静 黄晓丹 尤阔阔 张文成
摘 要： 随着航空运输需求的不断增加，导致各大机场时隙资源紧张，很多航班不能按时降落，只能在空中排队等待降落。文章研究了基于模拟退火算法的单机场地面等待优化策略，将空中等待策略转变为地面等待策略，让未起飞航班在原机场等待避开高峰期并对时隙进行重新分配。这不仅可以极大的减少航空公司延误损失，还可以提高安全性。最后利用真实数据在Python中仿真测试得出结果并和RBS算法进行对比，最终结果表明，使用模拟退火算法相对RBS算法可以减少航空公司延误损失的27.9%。
关键词： 地面等待； 模拟退火算法； RBS算法； 时隙
中图分类号：V355 文献标志码：A 文章编号：1006-8228（2019）03-09-04
Simulated annealing algorithm based single airport ground waiting optimization strategy
Zhang Hong， Xiong Jing， Huang Xiaodan， You Kuokuo， Zhang Wencheng
（Shanghai University of Engineering Science， Air Transport Institute， Shanghai 201600， China）
Abstract： With the increasing demand for air transportation， the time slot resources of major airports are tight， and many flights cannot land on time and can only wait in line in the air for landing. In this paper， the optimization strategy of single airport ground waiting based on simulated annealing algorithm is studied， and the air waiting strategy is changed into the ground waiting strategy， so that non-departing flights can wait at the original airport to avoid the rush hour and reallocate the time slot， which can not only greatly reduce airline delay losses but also improve safety. Finally， the simulation results in Python with real data are compared with RBS algorithm. The final results show that the simulated annealing algorithm can reduce the delay loss of airlines by 27.9% compared with RBS algorithm.
Key words： ground waiting； simulated annealing algorithm； RBS algorithm； time slot
0 引言
人们对航空运输的需求正逐步扩大，空中交通越来越拥挤。机场遇到恶劣天气时，很多航班不能按计划起飞。而如果航班不能按时降落，那么飞机就不得不在空中等待，这不仅会增加危险系数，还会导致巨大的延误损失。如果预知目的机场拥挤时，可以让未出发的飞机在原机场等待即实施地面等待策略。
在实行地面等待策略时，空中交通流量管理部门统一将时隙进行重新分配，从而达到延误成本最小化的目标。地面等待策略主要有两大研究方向，分别是集权式分配方式和分布式分配方式。本文主要研究集权式分配方式。用集权式分配方式研究地面等待策略是短期高效策略中的一种重要方式。
1987年，Odoni首次系统地阐述了空中交通流量问题的研究领域、基本概念和主要问题，提出了重新安排飞机起飞时间以使拥挤成本最小化的思想[1]。1989年Terrab和Odoni将单机场确定型模型转化成了网络流模型，提出用最小费用流来求解模型[2]。2001年Pulugurtha1等将人工智能遗传算法引入到GHP问题中，采用遗传算法求解静态模型[3]，加快了模型求解的速度，促进了GHP模型在实际中的应用。2017年，Roland Deroo主要提出了一種新的基于运筹学方法的出发排序算法，进而可以进一步优化时隙的分配问题[4]。
2016年，田勇在基于突发事件下导致的机场容量急剧下降的情况下，首次引入生物地理学优化算法对建立的进离场时隙分配模型进行求解[5]。2016年，吴东晖在基于突发事件的基础上提出了对起飞和未起飞航班的延误成本进行区分研究，并建立机场突发事情机场时隙分配模型并利用BBO算法进行求解[6]。2014年，陈亚青对基于CDM下GHP时隙分配和模型进行研究，并提出了未来的研究方向主要是对随机容量的研究[7]。2014年，樊宪标提出了在考虑了不确定天气信息的影响下，结合静态时隙的不足之处建立了动态时隙配置模型[8]。
从近几年的研究看，对集权式分布的研究较多，而少有人用模拟退火算法对此问题进行分析。我们经过分析认为，将时隙分配问题当成一个指派问题来求解，得出的方案更优。本文利用模拟退火算法将时隙分配问题当成工人工作的指派问题来求解，最终得出的结果是可以减少航空公司的延误损失。
1 单机场地面等待策略模型
在建立单机场地面等待策略模型之前，我们先作如下假设。
⑴ 在时间段[0，T]内，目的机场Z的航班着陆出现拥挤，且目的机场Z是空中交通网络中惟一的容量限制单元和唯一产生航班延误的原因。
⑵ 有N个航班（F1、F2…Fn）预计在[0，T]内到达目的机场且每个航班的起飞时间和飞行时间是已知并且确定的，并且所有航班最后都在[0，T]内到达。
⑶ 时间区间[0，T]内，机场容量c（T）已知。根据c（T）变化，把时间区间[0，T]划分为n个着陆时间段，每个着陆时间段内有且只有一架航班着陆。航班Fi的地面等待成本系数，i∈{1，2，…，N}已知。
根据假设建立地面等待策略的成本最小化模型：
2 算法介绍
2.1 RBS算法
RBS算法用于初次分配机场进场的时隙资源，其主要流程如下。
⑴ 首先按免除航班、执行过地面等待程序的航班、其他航班这三类。
⑵ 对每一类航班按最初的时刻表顺序排序。
⑶ 将所有的可用时隙进行升序排列，然后依次排给航班队列中的每一个航班。
2.2 模拟退火算法
模拟退火算法是模仿自然界退火现象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性从某一初始温度开始，伴随温度的不断下降，结合概率突跳特征在解空间中随机寻找全局最优解。模拟退火算法的计算步骤如下。
⑴ 初始化、任选初始解，i∈S，给定初始温度T0，终止温度Tf，令迭代指标k=0，Tk=T0。
⑵ 随机产生一个领域解，j∈N（i）（N（i）表示的领域）计算目标值增量Δf=f（j）-f（i）。
⑶ 若Δf<0，则令i=j转⑷（j比i好，无条件转移）；否则产生ε∈U（0，1），若exp（-Δf/Tk）>ε，则令i=j（j比i好，有条件转移）。
注：Tk高时，广域搜索；Tk低时，局域搜索。
⑷ 若达到热平衡（内循环次数大于n（Tk））转⑸，否则转⑵。
⑸ k=k+1降低Tk，若Tk 注：降低Tk的方法有两种。一是Tk+1=Tk*r，其中r∈（0.95-0.99）（优点：简单易行）。二是Tk+1=Tk-ΔT。 3 算例验证 结合实际情况，我们选取某机场4点-5点之间的实际数据。由于天气原因，飞机的降落架数由10架降为了5架，对此执行地面等待策略， 由于飞机的尾流类型不同，延误成本也有所不同，按照国际民航组织（ICAO）的标准，并按照飞机的尾流强弱，将飞机分为3类，如表1所示。在表1的基础上，根据上述模型建立成本矩阵M。 本文将此优化问题转变成工作指派问题，将控制进场的时间看作工人，将原计划进场时间看作工作，将控制进场时间分配给原计划进场时间之差为航班延误时间，将此延误时间看作工人所做工作时间。但需要注意的是控制进场时间不可早于计划时间，只可以晚于计划时间，而工作指派问题中没有这一问题，因此成本矩阵中，将早于计划时间的情况用无穷大的成本数字表示（这边用10000表示），保证程序指派时会跳过这些组合并通过单机场地面等待模型可得出成本矩阵M如下： 将上述成本矩阵M导入模拟退火算法中，在python下进行仿真运算，运行结果如图1所示，将运行结果和RBS算法对时隙的分配结果作对比，对比结果如表2所示。其中表2的OTA/OTD指的是初始计划进离场时间，CTA/CTD指的是控制进离场时间。 由上述运行结果可知，最终的运行结果在10226终止，说明最优结果为10226。将上述仿真结果统计如表2。 本文将航班的时隙分配问题转化为指派问题之后，运用模拟退火算法对所有时隙进行指派研究，最后得出延误损失为10266相比RBS算法分配结果所得延误损失减少了27.9%。可知运用模拟退火算法并将时隙分配优化问题转化为指派问题可以有效的减少延误损失。 4 结束语 本文研究了基于模拟退火算法的单机场地面等待策略并进行了仿真实验，主要是通过模拟退火算法将单机场时隙分配优化问题转化为类似工人工作的指派问题，将控制进/离场时间早于计划进/离场时间的组合用无穷大延误数据表示，让程序可以跳过这些组合，最终得出延误成本最低的时隙指派组合。结果显示，运用本文的方法相对于RBS算法延误成本减少了27.95%。由此可见，运用模拟退火算法可以有效的解决时隙的分配优化问题。本文只研究了单机场时隙分配情况，而如今延误一般都涉及到多机场，所以多机场时隙分配策略也将是我们研究的重点。 参考文献（References）： [1] Odoni A R.The flow management problem in air traffic control[C]//Flow control of congested networks. Berlin： Springer-Verlag，1987：269-298 [2] AIAA. Ground-holding strategies for ATC flow control[J]. [3] Pulugurtha S S， Nambisan S S. Using Genetic Algorithms to Evaluate Aircraft Ground Holding Policy in Real Time[J]. Journal of Transportation Engineering，2001.127（5）：442-448 [4] Deroo R， Gama A. Optimization of Take-Off Runway Sequences for Airports Under a CDM Framework[M]//Applied Simulation and Optimization 2. Springer International Publishing，2017. [5] 田勇，吳东晖，万莉莉等.基于突发事件的机场进离场时隙分 配研究[J].武汉理工大学学报（信息与管理工程版），2016.38（1）：28-32 [6] 吴东晖.机场时隙分配优化技术研究[D].南京航空航天大学， 2016. [7] 陈亚青，罗亮.基于CDM的GHP时隙分配模型和算法研究[J]. 中国西部科技，2014.12：3-5 [8] 樊宪标.机场时隙资源协同动态配置研究[D].南京航空航天 大学，2014.
