不正常航班恢复模型的贪婪模拟退火算法研究

摘 要:为解决不正常航班恢复对航空公司带来的严重影响,研究了不正常航班恢复模型及其优化算法,对现有不正常航班恢复优化模型提出适当改进,重点设计了一种贪婪模拟退火算法。算法融合了GRASP和模拟退火算法的特点,提高了领域解的选择效率并且降低了陷入局部最优解的概率。实例证明这种算法可以处理大规模的不正常航班恢复问题,并且能够达到时间代价与结果质量的均衡。

关键词:不正常航班恢复;领域解;GRASP;模拟退火算法

中图分类号:F560 文献标识码:A 文章编号:1003-5192(2010)01-0066-05

Research on Greedy Simulated Annealing Algorithm of

Irregular Flight Schedule Recovery Model

TANG Xiao-wei, GAO Qiang, ZHU Jin-fu

(College of Civil Aviation, Nanjing University of Aeronautics & Astronautics, Nanjing 210016, China)

Abstract:Irregular flight schedule recovery is of great importance to the civil aviation industry. The model and optimization algorithm of irregular flight schedule recovery is researched in this Article. First proper improvement is made to the original model, and a new type of greedy randomized simulated annealing algorithm is designed. The new algorithm integrating the characteristics of simulated annealing algorithm and greedy randomized adaptive search procedure improves the efficiency of neighborhood selection and reduce the probability of falling into local optimal solution. Example proves that the algorithm is able to solve the problem of large-scale irregular flight schedule recovery, with the time cost suitable to the outcome quality. Key words:irregular flight schedule recovery; neighborhood; greedy randomized adaptive search procedure; simulated annealing algorithm

1 引言

不正常航班是指由于天气、机械故障、流量控制等原因,造成航班延误、备降或取消。据统计分析,我国2005年由于不正常航班引起的各类经济损失已经超过30亿元,同时造成巨大的社会影响。面对日益突出的不正常航班问题,社会各方面呼吁航空公司尽快采取有效解决措施。不正常航班的恢复首先是飞机计划恢复,第二阶段是机组恢复,第三阶段是旅客中转衔接恢复。关机计划恢复的决策对航空公司的收益影响最大,因此这一步也是最重要的。本文讨论的不正常航班恢复指飞机计划恢复。

航空公司为提高市场竞争力和最大化利用飞机资源,对航班计划(包括飞机计划和机组计划)的优化进行了较多的研究,航班计划基本上没有为应对各种意外的变化留下足够的松弛时间(Slack Time)[1]。因为飞机资源的备份成本极高,没有一家航空公司愿意专门为应付航班计划变化而让一架飞机空闲待命。这是造成航班不正常情况下运力调配困难的主要原因之一。此外,航班计划的运作环境是不确定的,除了考虑飞机可用性、机组可行性和维修约束之外,机场跑道条件、高原地区飞行条件、航线限制等因素都会增加计划调整的复杂性。

刻画不正常航班恢复问题的准确模型和寻找优化算法一直是航空运筹学领域研究的热点,快速有效的算法对于解决航空公司随时可能发生的资源优化利用问题将会产生巨大的经济效益。关于航空公司不正常航班恢复的研究可追溯到20世纪60年代。直至20世纪90年代中期,这方面的研究主要集中于单机型、小规模延误的恢复问题[2~6]。但是单机型模型对于航空公司的作用不是很大,因为很少有航空公司是单一机型的,即使是单机型,同一机型各飞机之间的适航性也存在很大区别,本质上来说也是多机型的。从20世纪90年代中后期至今,多机型、多经停、大规模延误的情况逐渐成为研究的重点,相继出现了资源指派模型和多商品流模型[7~9]。不论是单机型模型还是多机型模型,面临的一个共同问题就是算法的复杂性。不正常航班恢复优化问题是一个约束众多而复杂的实时网络优化问题,其解空间随飞机和航班数量的增加而呈指数级增加,是一个多参数、多约束的NP-hard问题。目前应用比较成熟的算法有GRASP算法、时空网络算法等[7~9]。GRASP是一种启发式算法,应用于小规模问题(10架飞机以内)效果较好,但求解大规模问题的效率较低,收敛性较差,较易陷入局部最优解;时空网络算法试图从重新构造全新的飞机路线来减少延误时间,这种思路使得问题的求解面临巨大的困难,当问题的规模达到20架飞机,80个航班以上时,时空网络算法需要的计算时间远远超过30分钟,很难达到航空公司实时控制的要求。

本文首先对文献[10]提出的不正常航班优化模型作适当改进,重点提出了一种贪婪模拟退火算法。新算法包含GRASP算法中贪婪随机的思想,并且通过设计领域解备选池提高了原GRASP算法的收敛性。算法还融合了模拟退火的特点,降低了问题陷入局部最优解的概率。

2 不正常航班恢复优化模型

(1)式为目标函数,表达的是旅客总延误时间由两部分构成,分别是延误航班的旅客延误时间和取消航班的旅客延误时间;(2)式表达的是实际飞行的同一飞机路线上的航班所必须满足的前后空间衔接关系,即前一个航班的到达机场必须与后一个航班的出发机场相同;(3)式表达的是实际飞行的同一飞机路线上的航班所必须满足的前后时间衔接关系,即前一个航班的预计到达时间加过站时间必须少于等于后一个航班的预计出发时间;(4)式表达的是实际飞行的飞机路线应当满足飞机流平衡,即恢复计划在各机场的过夜飞机数应与原计划各机场的过夜机场数相同;(5)式表达的是航班满足覆盖原则,即原计划的航班在恢复计划中都应被包括,要么在实际飞行的飞机路线中,要么在取消的飞机路线中,只能出现一次;(6)式表达的是所有航班的预计出发时间不超过出发机场宵禁时间,预计到达时间不超过到达机场宵禁时间。

3 原GRASP算法分析

在分析GRASP算法之前,需要先引入四个定义:航班环、航班串、实际飞行飞机路线、取消飞行飞机路线。

定义1 航班环,一组首尾相联的航班,其中第一个航班的出发机场与最后一个航班的到达机场相同;

定义2 航班串,一组首尾相联的航班,其中第一个航班的出发机场与最后一个航班的到达机场不同;

定义3 实际飞行飞机路线:以原计划中的飞机号(4位数字)作为其后航班运行所使用飞机的飞机路线;

定义4 取消飞行飞机路线:以一个虚拟飞机号(虚拟飞机号以V开头)作为其后航班运行所使用飞机的飞机路线。虚拟飞机实质上不是航空公司所拥有的飞机,只是为了运算所假设的飞机。该飞机路线所包含的航班将被取消。

GRASP算法包括不断循环的三个阶段:一是从初始的执行解(可行解)进行领域解的构造;二是把较好的领域解放入RCL表(Restricted Candidate List,限制性候选列表)中;最后从RCL表中随机选择一个领域解来构造执行解。算法的具体操作都是建立在航班环与航班串上的,操作共分为7种:航班环的前缀、航班环的中缀、航班环的后缀、航班环的取消、航班串的尾接、具有相同的出发机场的航班串互换、具有相同的出发与到达机场的航班串互换。GRASP算法的不足表现为三个方面:

(1)GRASP算法提出领域解的构造可以通过7种操作完成,有3种操作可以合并;

(2)RCL表的长度不容易确定,而且把领域解插入RCL表时进行排序操作,导致时间效率较差;

(3)GRASP算法中只有一个单一选择的方向,就是向着成本更小的方向发展,但这样容易陷入局部最优解陷阱。

4 贪婪模拟退火算法

4.1 新算法领域解的构造

本文模型以飞机路线作为基础,因此优化求解的过程实质上就是构造出新的飞机路线去替代上一个解中具有相同飞机号的飞机路线。为了保证飞机路线的产生过程不违背(2)、(4)、(5)式,新飞机路线的产生同样按照GRASP算法提出的操作。经分析GRASP算法中航班环的前缀、中缀和后缀操作可以合并为航班环的插入操作。这样7种操作简化为5种操作,这5种操作相当于领域解的构造,产生新的飞机路线。对于新产生的飞机路线,通过对航班ETD(预计出发时间)与ETA(预计到达时间)进行重排从而保证满足约束(3)。重新排的方法是:

(1)以某一飞机的就绪时间作为该飞机实际飞行路线中首航班的ETD;

(2)首航班的ETA=首航班ETD+(首航班的STA-首航班的STD),STA是计划到达时间,STD是计划出发时间;

(3)后续航班ETD=前一个航班的ETA+该飞机的过站时间;

(4)后续航班的ETA=该航班的ETD+(该航班的STA-该航班的STD)。

由于任意两条飞机路线通过5种操作构造的领域解的数量很多,一般情况下会达到10多个。如果航班计划中的飞机路线的数量很多,则可以产生的领域解的数量极为庞大,因此从领域解构造新的执行解需要特殊的处理。

4.2 领域解备选池

一个执行解就是一个航班恢复方案。从一个航班恢复方案中任意选取两个飞机路线产生领域解,用领域解去替代执行解中相应的具有相同飞机号的飞机路线,这样就构造出新的执行解。但是从原执行解中任意选取的一对飞机路线可以产生的领域解很多。为了使算法确实可行,在每一对飞机路线产生的领域解需要对其进行评价选择出最优的领域解,如果这个领域解比产生它们的两个飞机路线的延误总成本小,则将其放入一个称为成本降低解备选池中,如果这个领域解比产生它们的两条飞机路线的延误总成本大,则将其放入一个称为成本增加解备选池。成本降低解备选池和成本增加解备选池统称为领域解备选池。与原GRASP算法相比,新算法取消了RCL链表,改为领域解备选池。通过这种筛选将极大控制领域解的数量,并提高了算法的收敛性。

4.3 新算法执行解的构造

通过对所有的任意两个飞机路线的两两组合,可以得到成本降低解备选池与成本增加解备选池中的领域解,再对其进行选择构造执行解。选择时采用随机选择方法,具体的选择方法如下:

(1)为了保证(6)式的满足,在算法中对于超过宵禁的飞机路线需要赋予充分大的延误成本。在选择时首先应根据当前执行解是否存在超宵禁的飞机路线,如果存在,优先选择替换超宵禁的飞机路线的领域解,通过这种方法,在有限次数的迭代过程中就可以实现将不可行的执行解转化为可行的执行解。

(2)如果执行解中不存在超宵禁的飞机路线并且成本降低解备选池不空,就在成本降低解备选池随机选择一个领域解。

(3)如果执行解中不存在超宵禁的飞机路线并且成本降低解备选池为空,说明此时从当前的执行解已经不能找到使目标函数值下降的方向。为了避免得到的执行解是一个局部最优解,按照模拟退火算法的思路,可以允许执行解暂时向不好的方向发展。于是可以在成本增加解备选池中随机选择一个领域解。由于使执行解成本增加的方向总是存在的,且领域解数量众多。每次进行选择时,先判断成本增加解备选池中满足(7)式的领域解的数量与备选池中领域解的比例,如果大于5%,从中随机选择一个领域解;反之则算法结束。

其中Δ为领域解增加的延误成本;Kt为当前的温度值;random(0,1)为0-1间一个均匀随机数。

当选择出领域解后,就可以对执行解进行改造得到新的执行解进行下一次迭代过程。如果没有选出满足各种条件的领域解,则自动退出算法。由于不正常航班恢复是一个实效性很强的工作,因此在算法中设置了时间控制函数,当算法运行的时间达到了必须完成的时间,将强制退出算法。算法的总体流程图如图2。

5 实例分析

某一航空公司某一天的航班计划由30架飞机,149个航班构成,总的旅客人数为13109人。在尚未开始执行时有五架飞机发生故障,另外空管告知航空公司有两个机场由于特殊原因(军事演习)需要关闭,一个航班由于流控而延误。上述案例是该航空公司在运行时遇到的较严重的不正常航班情况,其中一个基地机场ZSPD被关闭两个小时,受影响的航班总数占当天航班总数的25%。参考航空公司运营经验,每个旅客延误1分钟的成本为1元,取消航班按延误8小时计算延误成本,流不平衡的惩罚系数为100000。分别应用贪婪随机模拟退火算法和GRASP算法在P4 2.6GHZ,512M内存的台式机上对上述案例进行求解,结果如表1所示。

由表1可知贪婪随机模拟退火算法和GRASP算法的运行时间均不超过1分钟,满足航空公司实时决策的时间要求。新算法得到的恢复方案中取消航班数为2,而GRASP算法为6,这主要是因为GRASP算法为了满足流平衡约束,不得不取消更多的航班环。同时贪婪随机模拟退火算法得到的恢复方案中延误航班数量略有减少,而且结构也更优,其中短时间延误(1小时以内)的航班数占总延误航班数的54%,中等时间延误(2~3小时)的航班数占39%,长时间延误(4小时及以上的航班数)的航班数占7%;而GRASP算法分别为17%、70%和13%。延误总成本方面,贪婪随机模拟退火算法得到的恢复方案更少,比GRASP算法节约了26%。GRASP算法取消的航班数较多,而延误情况又没有得到改善,陷入了局部最优解。因此贪婪随机模拟退火算法有效避免了陷入局部最优解的陷阱。

6 结论

针对不正常航班恢复问题,本文对原不正常航班恢复优化模型进行适当改进,并结合GRASP和模拟退火算法设计了一种新算法。新算法用领域解备选池(包括成本增加解备选池和成本降低解备选池)替换GRASP算法中的RCL链表以提高算法的时间效率,在此基础上新算法还融合了模拟退火算法的思想,有效地降低了陷入局部最优解的概率。算法的不足主要表现为:模型对于目标函数的设定没有能包含不正常航班恢复问题的全部成本问题,如调机成本,更换机型的成本,这些都是模型与算法下一步改进的方向。

参 考 文 献:

[1]Etschmaier M M, Mathaisei D F X. Airline scheduling: an overview[J]. Transportation Science, 1985, (2): 127-138.

[2]Teodorovic D, Guberinic S. Optimal dispatching strategy on an airline network after a schedule perturbation[J]. European Journal of Operational Research, 1984, (15): 178-182.

[3]Teodorovic D. Airline operations research[M]. New York: Gordon and Breach Science Publishers, 1988. 256-300.

[4]Cao J, Kanafani A. Real-time decision support for integration of airline flight cancellations and delays, part I: mathematical formulations[J]. Transportation Planning and Technology, 1997, (20): 183-199.

[5]Teodorovic D, Stojkovic G. Model to reduced airline schedule disturbances[J]. Journal of Transportation Engineering, 1995, (4): 324-331.

[6]Thengvall B G. Models and solution techniques for the aircraft schedule recovery problem[D]. Austin: The University of Texas, 1999.

[7]姚韵.航空公司不正常航班管理和调度算法研究[D].南京:南京航空航天大学,2006.

[8]Yan S, Young H. A decision support framework for multi-fleet routing and multi-stop flight scheduling[J].Transportation Research, Part A: Policy and Planning, 1996, (30): 379-398.

[9]Yan S, Tu Y. Multi-fleet routing and multi-stop flight scheduling for schedule perturbation[J]. European Journal of Operational Research, 1997, (103): 155-169.

[10]Michael F A, Jonathan F B. A grasp for aircraft routing in response to grounding and delays[J]. Journal of Combinatorial Optimization, 1997, (5): 211-228.