飞机路线恢复问题的两阶段随机规划方法研究

朱 博，朱金福，吴薇薇

(南京航空航天大学 民航学院，江苏 南京 211100)



飞机路线恢复问题的两阶段随机规划方法研究

朱 博，朱金福，吴薇薇

(南京航空航天大学 民航学院，江苏 南京 211100)

针对飞机故障修复时间的不确定性，建立了飞机路线恢复的两阶段随机优化模型:第一阶段模型为飞机资源指派模型，以延误和取消成本之和最小为目标函数；第二阶段补偿模型根据飞机故障修复时间的随机情景，以航班时间重排恢复策略的期望成本最小为目标函数。针对随机模型的结构，设计随机启发式算法。算例结果表明，采用随机模型和算法可以有效地提高不正常航班恢复方案的可行性，比确定型模型节约5.8%左右的恢复成本。

航班计划运行；飞机路线恢复；两阶段随机模型；贪婪模拟算法

航空公司的航班计划是在假设其能正常实施的前提下制定的，然而实际运行中，航空运输系统会面临各种不确定因素的扰动，使得航班无法按原计划执行，大大增加了航空公司的运行成本，给旅客带来极大不便，降低了航空运输系统的运行效率。对不正常航班恢复的研究至今已有约60年的历史，其中飞机故障造成短缺情况下的飞机路线恢复问题(aircraft rerouting problem, ARP)是研究的重点之一。TEODOROVIC等建立了受扰航班网络，对飞机故障时的路线恢复问题进行了研究，设计分支定界算法求解模型，是对扰动问题的开创性研究之一[1]。YAN等在动态网络计划扰动模型的基础上，利用网络流算法、拉格朗日松弛和次梯度法进行求解[2]。ARGÜELLO等采用贪婪随机自适应搜索算法(GRASP)对飞机路线进行重排，目标函数是航班收益损失和旅客延误损失最小[3]。THENGVALL等在飞机短缺的恢复模型中加入与原计划偏离的惩罚成本，在线性规划松弛未得到整数解的情况下用启发式算法得到整数解[4]。ANDERSSON等建立了带边约束的混合整数多商品流模型，利用Dantzig-Wolfe分解方法将其转化为集合划分模型[5]。赵秀丽等构建了以延误成本最小或延误时间最短为目标函数的飞机路线恢复模型，采用启发式方法并调用匈牙利算法对其求解[6]。唐小卫等在文献[3]的基础上，设计了贪婪模拟退火(greedy simulated annealing，GSA)算法，对飞机路线恢复问题进行了研究[7]。VOS等建立了动态模型框架，使用了平行时空网络来追踪飞机的状态，该框架依赖于飞机选择算法和一个线性规划模型[8]。

尽管国内外对飞机路线恢复的研究已经取得了不错的成果，但这些研究成果却未能在实际中很好地应用，这是由于：①假设飞机故障的情形是确定的，如飞机故障修复时间在决策前是已知的，而在实际运行中，这个值常常是很难预测的；②确定型飞机路线恢复研究给出的恢复方案在执行过程中缺乏鲁棒性，可能随着干扰因素的随机变化而变得不可行。因此，研究不正常航班恢复问题的随机优化理论和方法非常必要。不确定优化在航空运输规划与管理的一些领域已有一定的研究，如航线网络的设计和优化[9]、航班计划的制定等[10-11];而在航班计划运行层面，目前仅有一些利用仿真软件进行延误控制的研究[12]，并未考虑扰动因素的随机性。

1 问题的描述和模型的建立

1.1 问题描述

以两架飞机在一天的简单航班计划为例，给出了一个典型的飞机路线和故障修复时间示意图，如图1所示。圆角矩形表示航班，其中冒号前的数字表示航班号，冒号后的字母表示起降机场。灰色区域表示飞机A2在07:30时刻发现故障，预计故障修复时间为13:15。航空公司签派员可有多种恢复方案：取消航班4和航班5；直接将飞机A2预计执行的航班4～航班7全部顺延；在08:00交换飞机A1和A2的航班任务等。这是一个典型的优化问题，恢复方案在制定时假设故障修复时间为已知。

图1 飞机路线和故障修复时间示意图

然而，上述故障修复时间只是机务维修人员给出的期望值，该期望值很少与实际修复时间相同，可能导致其制定的恢复方案不优甚至不可行。例如，当签派员在7:30时将航班4延误至13:15，但13:15时发现飞机A2并没有恢复使用，此时会引发更多的延误和取消；还可能是飞机A2早于13:15修复完毕，那么可以指定和使用比当前更好的恢复方案。随着扰动信息频繁地更新，不断重新优化会是一个非常费时的过程。若能制定一个鲁棒恢复方案，当随机的恢复时间确定后，该方案只需进行简单的调整便可。

1.2 飞机路线恢复的随机规划模型

在确定型ARP研究中，资源指派模型可以准确简洁地描述问题，是最为常见的模型之一，该模型参考了文献[3]中的恢复模型，其中的隐含工作是可行的飞机路线已经生成。模型中的记号定义如下：①集合。F为航班集合，下标为i；K为可用飞机集合，下标为k；A为机场集合，下标为a；P为可行的飞机路线集合，下标为j。②参数。当航班i包含在路径j中时，aij等于1，否则等于0；当路径j在机场a终止时，bja等于1，否则等于0；ci为取消航班i的成本；ha表示恢复期结束时，为执行正常航班计划机场a需要的飞机架数；dkj为将飞机k指派给路径j的延误成本。③决策变量。当飞机k指派给路径j时，xkj等于1，否则等于0；航班i取消时，yi等于1，否则等于0。则建立ARP的第一阶段资源指派模型为：

(1)

(2)

(3)

(4)

(5)

(6)

式(1)为目标函数，要求航班延误成本和取消成本之和最小；式(2)为航班覆盖约束，对任一航班来说，其要么被取消，要么被指派给一个航班路径；式(3)为飞机流平衡约束，为了保证航班的正常运行，要求恢复期结束后各机场的飞机数满足一定数量；式(4)规定了一架飞机只能指派给一条可行的路径；式(5)和式(6)为变量非负约束。

该确定型模型有一个隐含的工作，即在假设飞机故障修复时间确定的情况下生成可行的飞机路线。然而，在实际运行中飞机故障修复时间是很难确定的，许多飞机可靠性和维修性的研究也证明了这一点[13]。因此，引入随机故障修复时间的概念，建立了两阶段的航班恢复随机优化模型。两阶段补偿模型的意义在于选择确定一种决策，使得当前的决策成本和以后补偿的成本期望值最小。对航班恢复问题来说，在优化模型中加入由随机性引起的期望调整成本；期望成本可通过建立补偿模型求解得到，反映了第一阶段恢复方案可能发生的变化，从而选择确定稳健性、可行性高的恢复方案。第一阶段模型即为上述ARP的确定型资源指派模型；第二阶段补偿模型是针对飞机故障修复的随机情景，对第一阶段的可行恢复方案进行调整,其采用的策略为不改变其飞机路线，单纯地重新安排航班时刻。这保证了补偿模型的可行性，其简单的线性形式也确保了求解的速度。第二阶段补偿模型也可以包括取消航班、交换飞机等较复杂的恢复策略，但并不改变模型的本质。带补偿的两阶段随机ARP模型形式为：

RP=minW=min(Z+Q(x,y))

(7)

(8)

(9)

随机模型的目标函数由两部分组成，第一部分为式(1)，第二部分Q(x,y)为第一阶段恢复方案在执行过程中进行调整补偿决策的期望成本；x和y分别为决策变量xkj和yi的简化表达形式；式(8)为式(2)～式(4)的抽象形式；式(9)为模型的非负0-1约束。

1.3 补偿模型

图2给出了图1例子在第一阶段模型中得到的一个恢复方案示意图，其采用的恢复方案是A1和A2交换飞机路线，并延误航班1～航班3。显然，恢复方案制订是以灰色的故障修复时间期望值为初始条件。然而实际运行中，A2的故障修复时间会是一个随机变量，取值在ΔT范围内。若A2的最终故障修复时间为14:00，则该恢复方案中航班1～航班3 需依次顺延；若航班3预计降落时间超出了机场AAA的宵禁开始时间，则该航班或被取消，或延误到宵禁时间结束，这两种方案都会造成很大的成本损失。这些情况会在第二阶段补偿模型的目标函数中以风险成本的形式表示。

确定型ARP模型的求解十分复杂。对两阶段随机规划模型，第一阶段的每一个可行解都对应着一系列的补偿模型需要求解，这就要求补偿模型的建立和求解尽量简单。令T表示飞机故障修复时间随机变量组成的向量，其包含了可被视为连续变量的受扰动飞机的恢复时间、被视为常量的未受扰动飞机的可用时间。则补偿模型的目标函数可用Q(x,y)= ∫q(x,y,T)dT表示。该目标函数是非线性且连续随机变量的概率分布函数，不易获得，因此可以不失准确度的情况下将飞机恢复时间进行离散化处理。每架受扰飞机随机变量的离散点组合可以构成一个有界的情景集Ω，令ω∈Ω表示一种情景，Pr(ω)为ω的概率，则第一阶段可行恢复方案的期望补偿为：

图2 飞机路线恢复和随机故障修复时间示意图

(10)

(12)

(13)

(14)

(15)

(18)

(19)

2 求解算法

尽管确定型ARP模型的求解已经非常复杂，对其算法的研究还是取得了许多成果。无论是精确算法如列生成，还是启发式算法如GRASP、贪婪模拟退火算法GSA，都可以在较短的时间内给出满意的解。将ARP问题由确定型拓展为随机型，问题规模的增加会使得求解更加困难。若第二阶段模型是线性的，且随机情景数量有限，则模型总可以转化为确定型的等价形式。但是，问题的规模也会随之变得更大。与一般的长期计划问题不同，对运行阶段的恢复优化来说，求解的速度是决策者关注的重点。忽略随机规划模型结构的通用算法将会降低效率，为了有效地求解两阶段随机模型，笔者根据随机模型的结构，结合GSA和简单的贪婪时间调整策略，设计了随机算法的求解框架。

对于第一阶段模型，决策变量x和y可以使用GSA算法进行求解。文献[7]给出了该算法的3个基本步骤：①通过顺延受扰飞机路线构建初始可行解；②对受扰飞机路线对进行5种操作，构建邻域解。受扰飞机路线对由两条飞机路线构成，为了保护未受扰的飞机路线免受不必要的调整，受扰飞机路线对中至少要有一条受扰飞机路线。对每个受扰飞机路线对的5种操作包括：航班环插入、航班串插入路线尾部、航班串交换、为航班串交换、航班环取消。③从受限候选表(包含成本下降的邻域解)和反向受限候选表(包含成本上升的邻域解)中选择若干邻域解替代当前解的相应部分。

当第一阶段的解传入第二阶段模型中，后者将按照情景数量退化为若干个易解的线性优化补偿模型。在补偿模型中飞机路线上的航班是固定不变的，因此对恢复方案的唯一调整就是对航班时刻表的重排；在保证其可行且满足MTT要求的基础上，贪婪地将航班时间紧凑调整。如果时间重排的策略无法得出可行解，唯一的可能就是宵禁约束无法满足，对该情况有两种解决方案：一是取消违反该约束的航班，二是延误航班直到宵禁结束。违反宵禁约束的成本以参数φi表示。因此，对每个情景ω∈Ω可得到q(x,y,ω),由于情景间互相独立，Q(x,y)可根据式(10)计算得到。

3 算例分析

表1所示为某航空公司原计划飞机路线，该算例共有6架飞机，原计划执行航班23个。假设航班延误单位成本ρi为20元/min；取消航班造成的成本等于航班延误8 h带来的成本，即9 600元；飞机路线超宵禁的成本φi为10 000元。国内所有机场的宵禁时间窗为每天[02:00,06:00]，国际机场如VVNB暂不考虑宵禁。飞机D在当前时刻11:40发现临时故障，机务人员对故障类型和严重程度进行判断，给出故障修复时间的期望值为320 min，即D在17:00可投入使用；根据历史统计信息，得出离散的故障修复时间的概率分布，如表2所示。

表1 原计划飞机路线

表2 飞机D故障修复时间的概率分布

在求解EV中，飞机D的故障修复时间为常量320min，即D到17:00可投入使用。用GSM算法从步骤①～步骤⑥求解EV模型，设置算法终止条件为计算时间达到5min或生成300个执行解。表3列出了该确定型模型的解，总延误成本为EV=Z=15 900元。确定解的期望补偿成本为Q=5 928元，表示当确定解实施时由于随机性引起的调整成本。因此，确定解的随机期望成本为EEV=W=Z+Q=21 828元。对WS模型使用类似的求解方法，每个随机飞机修复时间的离散值被视为常量输入第一阶段模型；进行优化并根据表2的概率计算出期望值后，得到WS=16 007元，表示优化前若能得到随机变量确定值时决策的期望目标值。

对两阶段随机模型RP进行求解，结束条件设置为计算时间达到10min或得到300个执行解。随机恢复方案同样在表3中列出，延误成本Z=16 300元，第二阶段补偿模型的成本为Q=4 257元，所以随机模型的目标函数值RP=W=Z+Q=20 557元。

若不考虑飞机恢复时间的不确定性，则确定型模型的恢复方案延误成本(15 900元)比随机模型中的恢复方案(16 300元)小。但是，确定型模型方案中的飞机D会执行航班F24，该航班预计在凌晨02:00降落在ZSPD，F24有50%的概率会由于违反宵禁约束而被取消或长时间延误，从而引起更多的运行成本和旅客损失。因此，在考虑对不确定性进行补偿的情况下，随机恢复方案的成本(20 557元)比确定解的恢复方案成本(21 828元)少；随机模型解中，大部分飞机在当天降落停场机场前有一定的缓冲时间，可以吸收不确定性带来的变化，所以恢复方案更为鲁棒和灵活。定义完美信息的期望成本(expectedvalueofperfectinformation，EVPI)EVPI=RP-WS，表示随机模型中不确定性的影响。定义随机解价值(valueofstochasticsolution，VSS)VSS=EEV-RP，表示确定解的随机期望成本与随机解的目标函数值之差。在该算例中，EVPI=RP-WS=20 557-16 007=4 550元，可见不确定性给恢复方案带来了许多额外的成本。对比确定解情景分析的期望值与两阶段随机模型的目标函数值，得到VSS=EEV-RP=21 828-20 557=1 271元。随机模型得到的解比确定模型的解降低约5.8%的成本。

表3 两种模型的恢复方案对比

4 结论

飞机临时故障导致的运力资源短缺是造成航班不正常的主要扰动因素之一。针对飞机故障修复时间的不确定性，在确定型航班恢复研究的基础上，建立了两阶段的随机航班恢复模型。该模型提供了在飞机故障修复时间不确定的情况下做出恢复方案成本的估计，在本质上通过对补偿问题的评估增强了已有恢复方案的可行性。由于模型的复杂性和对计算时间的要求，设计了随机贪婪模拟退火算法，结合传统的启发式算法框架和简单的贪婪补偿方法，有效地对飞机故障的随机恢复问题进行求解。通过算例测试，体现了航班恢复问题中考虑随机因素的重要性，随机解价值的计算也体现了准确信息的重要性和随机规划模型的现实意义。

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

[2] YAN S, YANG D H. A decision support framework for handling schedule perturbation[J]. Transportation Research Part B Methodological,1996,30(6):405-419.

[3] ARGÜELLO M F, BARD J F, YU G. A GRASP for aircraft routing in response to groundings and delays[J]. Journal of Combinatorial Optimization,1997,1(3):211-228.

[4] THENGVALL B G, BARD J F, YU G. Balancing user preferences for aircraft schedule recovery during irregular operations[J]. IIE Transaction on Operations Engineering,2000,32(3):181-193.

[5] ANDERSSON T, VRBRAND P. The flight perturbation problem[J]. Transportation Planning and Technology,2004,27(2):91-117.

[6] 赵秀丽,朱金福,郭梅.不正常航班延误调度模型及算法[J].系统工程理论与实践,2008,28(4):129-134.

[7] 唐小卫,高强,朱金福.不正常航班恢复模型的贪婪模拟退火算法研究[J].预测,2010,29(1):66-70.

[8] VOS H W M, SANTOS B F, OMONDI T. Aircraft schedule recovery problem: a dynamic modeling framework for daily operations[J]. Transportation Research Procedia,2015(10):931-940.

[9] 葛伟,朱金福,吴薇薇,等.基于无容量限制的P：枢纽众位问题的随机优化[J].系统工程理论与实践,2013,33(10):2674-2678.

[10] SCHAEFER A J, JOHNSON E L, KLEYWEGT A J, et al.Airline crew scheduling under uncertainty[J]. Transportation Science.2005,39(3):340-348.

[11] YEN J W, BIRGE J R. A stochastic programming approach to the airline crew scheduling problem[J]. Transportation Science,2006,40(1):3-14.

[12] ROSENBERGER J M,SCHAEFER A J, GOLDSMAN D, et al. A stochastic model of airline operations[J]. Transportation Science,2002,36(4):357-377.

[13] SOHN S Y, YOON K B, CHANG I S. Random effects model for the reliability management of modules of a fighter aircraft[J]. Reliability Engineering and System Safety,2006,91(4):433-437.

[14] BIRGE J R. The value of the stochastic solution in stochastic linear programs with fixed recourse[J]. Mathematical Programming,1982,24(1):314-325.Two-stage Stochastic Programming in Aircraft Routing Recovery Problem

ZHU Bo:Doctorial Candidate; College of Civil Aviation ,Nanjing University of Aeronautics and Astronautics, Nanjing 211106,China.

ZHUBo,ZHUJinfu,WUWeiwei

To deal with the intrinsic uncertainty of the repair time, this paper established a two-stage stochastic flight recovery model. The first stage model is an aircraft resource assignment model, with the objective function of minimizing delay and cancellation cost. Based on stochastic scenes of aircraft restoration time, the second recourse model uses re-timing strategy, with the objective function of minimizing the expectation cost on recourse decision. In accordance with the structure of the stochastic model, a stochastic heuristic algorithm was designed to solve the model. The computational results indicates that the proposed stochastic model and algorithm can effectively improve the feasibility of the recovery solutions, and can save 5.8% operational cost compared with the deterministic model.

flight schedule operation; aircraft routing recovery; two-stage stochastic programming model; greedy simulated annealing algorithm

2095-3852(2016)05-0591-06

A

2016-06-04.

朱博(1987-)，女，江苏镇江人，南京航空航天大学民航学院博士研究生.

国家自然科学基金项目(71171111；71201081)；南京航空航天大学博士学位论文创新与创优基金项目(BCXJ13-14)；江苏省研究生培养创新工程资金项目(CXZZ13_0174).

V355.2 DOI：10.3963/j.issn.2095-3852.2016.05.016