基于改进的GRASP算法的飞机优化恢复研究

乐美龙，王婷婷，吴聪聪

(上海海事大学科学研究院，上海201206)

中国民航局的民航行业发展统计公报中披露，2011年，我国各航空公司计划航班235.3万班，正常执行181.5万班，航班正常率为77.2%.其中，主要航空公司计划航班201.8万班，正常执行157.2万班，航班正常率为77.9%;中小航空公司计划航班33.5万班，正常执行24.4万班，航班正常率为72.7%.航班的不正常带来的损失十分巨大，据美国航空协会统计，不正常航班每年给美国航空业造成约100亿美元损失.

文献［1］对近30年航空恢复优化的文献进行了整理，指出航空恢复问题共分为4大类:飞机、机组、乘客、综合恢复，并分别进行了概述.文献［2］中依据优先配对原则，进行了航班与机组的同时优化.文献［3］中提出了同时考虑飞机和乘客的模型，用“航班环”的概念代替“航班”来建立该模型，通过优化器求解，给出不同类型的解决方案.文献［4］中提出了一种结合时间窗的优化模型，来重新规划受到地面等待和延迟情况下的飞机航线.文献［5］中运用了一种决策支持工具(decision support tool for airlines schdule ercovery，DSTAR)来解决航空公司遇到突发事件时的恢复问题.文献［6］中提出了关于航班重新排班和调整飞机航线的模型，采用一种选择启发式算法来选出需要调整航线的飞机.文献［7］中提出了一种大规模邻域搜索的启发式算法来解决飞机和乘客的恢复问题.文献［8］中结合了各种资源的平衡来建立模型，运用循环启发式算法来求解，另外针对不同措施进行了偏好研究，给出了不同的计算结果.文献［9］中运用了一种贪婪随机适值搜索过程(greedy randomized adaptive search procedure，GRASP)来重新规划受到地面等待和延误的航线，但该算法尚存在一些不足之处，文中将在以下章节进行详细说明.

1 飞机恢复问题描述

飞机故障、机组人员病假、极端天气、流量控制等突发事件，都会造成航班不正常执行，此时，必须尽快恢复航班计划，以减少航空公司的损失.一般来说，航空恢复问题主要包括飞机恢复、机组恢复及乘客恢复.其中飞机是航空公司日常运行中成本最高的部分.因此，当原航班计划被扰动时，首先考虑飞机的恢复［10］.进行飞机恢复时，可以采取的措施包括运用备用飞机、飞机调用、飞机互换、飞机超时限飞行等。一般用航班取消和延迟的成本衡量飞机航线安排的成本［11］.

2 数学模型

以下是飞机恢复数学模型，该模型考虑了航班的取消和延迟，从而对可用飞机可进行指派，目标是使取消和延迟航班的总成本最小.

参数:Sf为航班f的计划起飞时间;trf为航班f的航行时间;tc为航班间的连接时间;Cf为航班f的取消成本;Df为航班f延迟1 min的成本.

变量:xkf={0，1}，当航班f用飞机k飞时为1，否则为0;zf={0，1}，航班f取消时为1，否则为0;tdf为航班f的实际起飞时间;taf为航班f的实际到达时间.

目标函数:

约束条件:

模型中，目标函数(1)中的第1部分为取消航班成本，第2部分为航班延迟成本;约束条件(2)表示对于每条航线，均指派不多于一架飞机;约束条件(3)保证对于每架飞机，只指派到不多于一条航线;约束条件(4)表示对于每个航班，要么取消，要么由一架飞机飞;约束条件(5)表示每个航班若不取消，其到达时间为起飞时间与飞行时间之和;约束条件(6)表示每条航线的后一个航班起飞时间为上一个航班到达时间与连接时间之和;约束条件(7)保证航班实际出发时间不早于计划起飞时间.

3 算法

3.1 传统的GRASP算法

传统的GRASP的步骤为:① 构造初始方案;②随机选择两条航线组成航线对，进行一系列的航班互换等操作，共7种方式，依次为航班环尾接、航班环续前、航班环插入中间、航班串的尾接、首尾机场相同的航班串互换、出发机场相同的航线尾航班串互换、航班环的取消，按照这几种方式构造邻域解，并把成本减小的邻域放到候选表中;③在候选表中随机选择一个邻域解构造可行解［9］.该方法被证明可以有效进行初始解的邻域搜索，最终可以得到接近最优的解.

航班串代表有2个或2个以上的航班组成的一条航线(图1).

“奉献清洁能源，打造绿色企业”，这是中国石化一直以来的倡导。在每年的公众开放日，年轻的讲解员们借助智能机器人、小视频，让大家能深刻地了解油气及石化产品从生产、加工到使用的一整套环节，也深刻地了解到了中国石化为老百姓平时的节能减排，环境保护方面做出的突出贡献。这种近距离的接触，不仅展示了企业的社会责任、技术革新，而且感染了前去参观的老百姓，让他们更深地体会到应该节约能源、绿色生活。

图1 航班串Fig.1 Flight route

航班环代表首尾为同一机场的航班串(图2).

图2 航班环Fig.2 Flight circle

算法不足之处在于:①将任意两条航线作为航线对产生邻域解，这其中包括了两条均未受扰的航线，既不符合航空公司尽量不脱离原航班计划的实际情况，又增加了算法运行时间;②选择航线对时，将两条所经机场毫不相关的航线组对，也增加了算法运行时间;③邻域产生后，算法将明显不符合实际不情况的邻域也进行评价，如违反宵禁政策、原航班顺序颠倒等，降低了算法效率;④ 只将成本降低的邻域放入备选池，会容易陷入局部最优.

3.2 改进的GRASP算法

3.2.1 邻域解的构造

文中的模型与算法研究是以航班串的形式展开，因此算法的初始解由一系列的航班串组成.对比传统的GRASP算法的不足之处①，在实际情况中，航空公司倾向于选择脱离原航班计划较小的恢复方案.因此在构造邻域前，设计的算法是选择一条受扰航线作为航线对中的第1条航线，后续展开的航班操作也是围绕受扰航线展开的.

选择航线对中的第2条航线时，若某条航线所经过的机场不包括第1条航线的任意航班，则该航线不被选择为第2条航线.两条航线产生后组成航线对，对该航线对进行GRASP算法的航班操作.按照这样的方式产生初始解的邻域.

3.2.2 邻域验证机制

由GRASP算法的航班操作方法产生一系列的航线对，这些航线对中有些不符合实际情况，可以提前排除，不对其进行评价.这里违反的情况包括两种:宵禁和原航班顺序颠倒.

3.2.3 邻域解的备选池

每种恢复方案对应算法的一个执行解，对执行解验证通过后，将航线对应到飞机，即得到新的执行解，并再度验证评价，以此类推.每组航线对对应的邻域解有很多，算法将所有邻域解进行评价，如果这个邻域解比原航线对的总成本(包括取消与延误成本)小，则将其放入备选池中.在这种方式的基础上，将总成本增大的放入附加备选池.将这两种备选池统称为邻域解的备选池.这种筛选可以控制邻域解的数量，并提高算法的收敛性.

3.2.4 执行解的选取

得到邻域解的备选池后，需要从中选取执行解，本算法采用随机选取的方式，并基于以下原则:①若基础备选池不为空，则在其中随机选取邻域解作为执行解;②若基础备选池为空，即当前解不存在目标成本降低的邻域解，则转向附加备选池，允许执行解暂时变坏，因此在附加备选池中随机选取一个解.但由于执行解的目标成本增加的情况总是存在，且邻域解数量较多.因此，设定了模拟退火方法的判定方式，即判断附加备选池中满足式(8)的邻域解的数量与备选池中邻域解的比例，若大于5%，则从中随机选取一个解;反之算法结束.

式中:Δ表示增加的成本;Kt表示当前温度;random(0，1)指0 至1 的一个均匀随机数［12］.

选取出执行解后即可进行改造，所得到的执行解作为下一次迭代的初始解.为了满足航班恢复的时效性，算法设置了时间限制.算法流程如图3.

图3 改进的GRASP算法步骤Fig.3 Procedure of the improved GRASP

4 算例分析

文中对所提出的模型，运用小规模的算例进行计算，将计算结果与简单顺延方式进行比较.这里指出，简单的顺延方式即飞机在原航班出发时间的基础上加上被延误的时间作为该航班的出发时间.当航班违反宵禁时即取消该航班及其后续航班.计算中其中涉及的假设包括:①允许飞机的调换;②航班延迟成本为每分钟100元;③ 航班间平均连接时间为60分钟;④ 航班取消成本按照特定公式(取消成本=乘客数×机票均值)来计算.

以某航空公司某天737-800机队的部分数据进行计算，数据涉及到20架飞机，109个航班，8126个乘客.其中时间表示方式按照6:00为0，以后的时间按分钟数依次累加，例如130指8:10.突发事件以及相关数据如表1，其中直接或间接受到飞机故障影响的航班有9个，受到机场关闭影响的航班有9个，受到影响的航班共占8.26%.

表1 突发事件Table 1 The disruptions

采用 C#语言对原 GRASP算法、改进后的GRASP算法及Gurobi求解器分别进行程序设计，在个人笔记本电脑(Duo CPU@2 GHz，1 GB RAM)上运行，分别对该问题进行求解，所得结果与简单的顺延结果的比较情况如表2.

表2 计算结果对比Table 2 Comparison of different results

由表2可以看出，两种GRASP搜索算法与Gurobi求解器均可以在较短时间内得出航班恢复方案.其中原GRASP算法搜索出的可行解取消航班数为4个，而改进后的算法为2个，且改进后的算法延迟航班数也较少.其中，原GRASP算法所得方案1h以内延迟航班数占总延迟航班数的64.71%，而改进后的算法这一数据为71.43%，因此优化方案的结构更好.同时，改进后算法比原算法总成本减少了8.99%，计算时间少了36%，因此更适合解决较大规模的问题.另外，运用改进的GRASP算法与求解器得出的方案相同，但明显的是，算法的计算时间较求解器节省70%以上，虽然计算时间均在1 min之内，但计算更大规模数据时，算法的优势将体现出来.

5 结论

文中针对航空公司飞机恢复要求，建立了数学模型.之后，运用Gurobi优化软件与改进前后的GRASP算法进行算例求解，得到了恢复方案.运用改进后的GRASP算法，明显减少了求解时间，提高了运算效率.文中采用的数据来自于上海某航空公司.实例计算表明:采用优化软件进行模型求解可以得出比顺延更好的简单实时恢复方案，GRASP算法的运用可以减少求解时间，而运用改进后的GRASP算法还可以将求解效率进一步提高.

但是，文中算法尚存在一些不足之处.对于模型，文中只考虑了飞机的恢复，未考虑机组人员和乘客的恢复.对于算法，文中虽然在运行时间上将GRASP进行了改进，提高了求解效率，但没有考虑机型交换方式.另外，文中只解决当日飞机的恢复，没有处理多日内的恢复问题.以上均为以后进一步的研究方向.

References)

［1］ Le Meilong，Wu Congcong，Zhan Chenxu，et al.30 years′march of mathematical programming:a classification and literature review［C］∥International Conference on Transportation and Mechanical，and Electrical Engineering.Changchun China:［s.n.］，2011:36-41.

［2］Le Meilong，Sun Lihong.Optimal airline crew recovery considering flight time constraint and paring rule［C］∥2011 International Conference on Transportation and Mechanical＆ Electrical Engineering.Changchun China:［s.n.］，2011:78-84.

［3］Jafari N，Zegordi H.Simultaneous recovery model for aircraft and passengers［J］.Journal of the Franklin Institute，2011，348(7):1638-1655.

［4］Bard J F，Yu G，Arguello M F.Optimizing aircraft routings in response to groundings and delays［J］.IIE Transactions，2001，33:931-947.

［5］Abdelghny K F，Abdelghany A F，Ekollu G.An integrated decision support tool for airlines schedule recovery during irregular operations［J］.European Journal of Operational Research，2008，185(2):825-848.

［6］Rossenberger J M，Johnson E L，Nemhauser G L.Rerouting aircraft for airline recovery ［J］.Transportation Science，2003，37(4):408-421.

［7］ Bisaillon S，Cordeau J F，Laporte G，et al.A large neighborhood search heuristic for the aircraft and passenger recovery problem［J］.Operation Research，2011，9:139-157.

［8］Thengvall B G，Bard J F，Yu G.Balancing user preferences for aircraft schedule recovery during irregular operations［J］.IIE Transactions，2000，32:181-193.

［9］Arguello M F，Bard J F，Yu G.A GRASP for aircraft routing in response to groundings and delays［J］.Journal of Combinatorial Optimization，1997，5:211-228.

［10］Clausen J，Larsen A，Larsen J，et al.Disruption management in the airline industry:concepts，models and methods［J］.Computers＆ Operations Research，2010，37(5):809-821.

［11］Kohl N，Larsen A，Larsen J，et al.Airline disruption management:perspectives，experiences and outlook［J］.Journal of Air Transport Management，2007，13(3):149-162.

［12］唐小卫，高强，朱金福.不正常航班恢复模型的贪婪模拟退火算法研究［J］.预测，2010(1):66-70.Tang Xiaowei，Gao Qiang，Zhu Jinfu.Research on greedy simulated annealing algorithm of irregular flight schedule recovery model［J］.Forecasting，2010(1):66-70.(in Chinese)