基于大邻域搜索算法的不正常航班恢复策略
2023-12-07李星宇徐衍霏鲁亮付泽昊冯健铠
李星宇，徐衍霏，鲁亮，付泽昊，冯健铠
（中国民航大学计算机科学与技术学院，天津 300300)
0 引言
随着我国经济水平的快速发展，交通运输业也发展迅速，无数民营航空公司与国营航空公司纷纷进入中国民航大家庭。但是随着航空公司收益的不断增加，各大航空公司之间的竞争也越来越激烈。实际中一些不可抗拒的因素如自然灾害或者一些突发事件都会导致出现不正常航班，造成很多影响，因此各大航空公司对于不正常航班问题也愈发重视，不正常航班不仅会影响旅客满意度，影响航空公司的声誉，也会在信息时代带来舆论影响。
关于不正常航班恢复问题，国内外专家学者进行了很多的相关研究。在国内，朱金福等[1]在2010年提出了退火算法，并将其运用在贪心自适应搜索算法的求解器当中，使用邻域备选池取代RCL链表。张力菠等人[2]对现在的不正常航班恢复模型和算法进行了总结，并且将飞机摆渡策略在原有基础之上提出了并行的贪心自适应搜索算法。彭安娜[3]基于列生成和多标签算法,设计了飞机临时故障情况下的飞机和机组一体化恢复问题的求解算法。2022年，罗军、江林林[4]使用了改进的匈牙利算法，对不正常航班延误成本进行研究。在国外，Teodorovic等人[5]1984年率先研究了航空时刻表的恢复。Aktürk 等人[6]首次将巡航速度调整明确引入航班恢复模型，为便于求解通过二次圆锥曲线对模型进行重构。Jitamitra Desai等人[7]研究了同时解决飞机和乘客时间表恢复问题的综合航空公司服务恢复问题，最小化飞机恢复和运营成本、乘客行程延误成本和乘客行程取消成本。 Karichery Sureshan等人[8]在2022年提出了副本评估方法，依靠反复求解定义在时间—空间网络上的每个飞行器的ARP 线性规划松弛,并根据得到的解评估需要添加到网络中的副本，以便于进行航班恢复。
对于不正常航班的恢复问题，国内外的研究人员都有所研究，但是国内对不正常航班恢复问题的研究起步较晚，在规模与结构上尚且不够成熟，寻求更加方便快捷的求解方法仍然是我国乃至国际民航业亟待发展的一大课题。
1 问题描述与建模
1.1 问题描述
在飞机受到干扰的情况下，飞机无法执行之前所安排好的飞行计划，此时航空公司应在尽快的时间内对于受影响的不正常航班进行恢复。本文考虑了飞机路径恢复问题(Aircraft route Recovery Problem,ARP)，在恢复期开始时利用其他的飞机调配来执行不正常航班的路径，达到旅客的行程要求。在这个过程中，不仅要将受影响的航班尽快恢复，还要让其他航班收到的影响达到最小，且综合成本尽可能低。
当某个飞机出现故障或者出现了其他紧急情况时便无法执行之前的飞行计划。若所等待的时间不长，则称之为飞机延误；如若等待时间很长，甚至近期都无法起飞，则称之为飞机停场。
在恢复时间内对于飞机的调度问题还要受到以下条件的约束：
1) 一个航班要么只被执行一次，要么就要被取消；
2) 调整后的航班其实际的出港时间不允许早于其原计划的出港时间；
3) 在调整之后可得新飞行路径，在新的飞行路径上面的航班其前后两个航班都要满足后续航班的实际出港时间在前序航班的实际进港时间之后，并且不得超出最小过站时间；
4) 任何一架飞机的延误时间不允许超出最大延误时间限制；
5) 最后一班进港航班不得在宵禁时间之后进港；
6) 在恢复时间结束后，任何机场都应该满足各机型飞机符合其第二天执行航班计划的要求，以保证后续的航班可以正常执行。
1.2 最小成本模型构造
1) 参数
不正常航班的调度策略具有三种：飞机交换，延误以及取消。建立航班恢复模型符号说明如下所示：
索引：
集合：
参数：
2) 数学模型
下标变量
决策变量
xr：1 表示飞机已经执行飞机路径r,r∈R；0 表示飞机并未执行的飞机路径r，r∈R。
yf：1表示航班f被取消，f∈F；0表示航班f未被取消，f∈F。
3) 数学公式
目标函数：
约束条件：
目标函数(1)为了保证不正常航班的恢复成本最小；约束(2)为了保证飞机的平衡性，在恢复结束之后，一定数目某一机型的航班能够回到之前指定的机场，以保证第二天的飞行任务可以顺利进行；约束(3)要求一架飞机在一定的时间内只能执行一条飞行路径，从而保证了资源的有限性。约束(4)要求每一个航班的最大延误时间不允许超过延误时间限制；约束(5)和(6)要求决策变量必须是0-1 变量，不允许利用其他数值。
2 解决方法
2.1 大规模邻域搜索算法的定义
根据在航班恢复策略中的应用，可以给大规模邻域搜索算法进行如下定义：大规模邻域搜索算法是一种用于解决航班恢复问题的优化算法，其基本思想是通过在解空间中搜索相邻的解来逐步改进当前解的质量，以找到一个最优或接近最优的航班恢复策略。
具体步骤如下：
1) 根据初始解构造算法获得航班恢复问题的一个初始可行解，记为(xr,yf)。
2) 根据当前解(xr,yf)和定义的邻域N(xr,yf) 在邻域中查找一个新解(xr′,yf′)，满足：(xr′,yf′) = arg min(xr″,yf″)∈N(xr,yf)c(xr″,yf″);
3) 如果c(xr′,yf′) 4) 输出(xr,yf)。 在航班恢复问题中，(xr,yf)表示航班恢复策略的状态，其中xr是已恢复的航班，yf是未恢复的航班。邻域N(xr,yf)定义了如何生成当前解的相邻解，通常通过对航班恢复策略进行小范围的调整或交换来生成新解。函数c(xr,yf)衡量了航班恢复策略的质量或成本，目标是寻找最小成本的策略。 下面介绍一些关于初始解构造时所需要用到的参数： 初始解构造算法流程如下： 输入：PD（延误飞机集合），PC（停场飞机集合），S0（初始航班序列） 输出:（构建的初始解） 第1步: PD= 输入的延误飞机集合 PC= 输入的停场飞机集合 第2步： 如果PD为空，则转到第8步。 否则，转到第6步。 否则，取任意p0∈PD，令PD=PD-p0，且rc=空集，转到第3步。 第3步： 令off(f0,1)=avat(p0), 对于任意f0,j≠f0,1且f0,j∈S0，off(f0,j)= max{std(f0,j),off(f0,j-1)+gr(p0)} 。 第4步： 如果存在 (f0,j)∈S0，且off(f0,j)-std(f0,j)>M，则转到第5步。 否则，转到第6步。 第5步： 在航班串 S0中找到一个航班环fc={f0,a,f0,a+1,...,f0,b},并且满足a 第6步： 如果S0=fc={f0,a,f0,a+1,...,f0,n},off(f0,n)+dur(f0,n)>cf(arr(f0,n))的航班，则转到第7步，否则令RC=RC∪rc。 第7步： 在航班串S0中找到一个航班环fc={f0,a,f0,a+1,...,f0,b},并且满足a 第8步： 如果PC= 空集，则转到第11 步，否则取任意p0∈pc,PC=PC-{p0},转到第9步。 第9步： 如果S0={f0,1,f0,2,...,f0,n} 中有满足dep(f0,1)=arr(f0,n)的航班，则令RC=RC⋃S0，否则在中寻找一个最小的航班环fc={f0,1,f0,2,...,f0,b}，b 第10步： 在飞机集合P中寻找飞机p_i∈P和其对应的航班串Si={fi,1,fi,2,...,fi,p}arr(f0,p)=arr(f0,b),S0⋃{f0,j+1,f0,j+2,...,f0,n}，转到第8步。 第11步： 将初始可行解输出。 为了验证该算法的可行性，本节结合了航空公司的实际情况进行了分析。航班信息使用了国内某航空公司的某天航班计划，5架飞机在11个机场之间执行的22个航班，具体航班信息表见表1。 表1 航班信息表 表2 大规模邻域搜索算法求解 图1 调机前的甘特图 假设此时1 号飞机在7：20 时因为某些突发情况无法从77号机场起飞，此时最好的解决办法是取消1号飞机的所有航班(1934，1945，1911，1908) ，但是若直接对这些航班进行取消的话需要较高的成本，所以为了降低成本，可以根据初始解生成算法的原理来取消一部分航班。 首先根据初始解构造算法，可以确定停场飞机是1 号，此时需要找到1 号飞机最大的一个航班环作为取消路径，显然是1934，1945，1911，1908号航班，但是取消四路航班成本巨大，此时就需要进行取消航班和正常航班的路径对匹配，并进行迭代，经过迭代后发现取消1934、1908号航班是最优解。 表3给出了使用大规模邻域搜索算法和直接取消航班的成本比较，直接进行航班取消所需成本为58 000元，而使用大规模邻域搜索算法则需要成本为50 513.6元，比直接取消成本减少7 486.4元。 表3 使用大规模邻域搜索算法前后结果比较 本文针对飞机延误或停场的情况下进行不正常航班的恢复，将航空公司的损失降到最小，使用大规模邻域搜索算法得出航班的初始可行解，后逐次迭代，将结果趋于一个最接近最小成本的值，其对应的航线即为最后得出的可行解。 图2 调机后的甘特图 不正常航班恢复对于中国民航具有重要意义。首先，对于旅客而言，不正常航班恢复将减少旅行不便和不确定性，使旅客按照计划安排行程，减少延误所产生的影响。其次，对航空公司而言，不正常航班恢复将帮助航空公司减少亏损，提高收益。总体而言，正常航班的恢复对于中国民航来说，意味着经济的复苏、旅客的出行方便以及航空公司的盈利。2.2 初始解构造
3 计算结果分析
4 结论
