基于大邻域搜索算法的不正常航班恢复策略

摘要：航班由于恶劣的天气、机组人员和飞机维修等原因导致延误或取消时，如果不能妥善处理，将会影响到旅客旅行，并可能损害航空公司的盈亏绩效和声誉，对此，航空公司需要制定应急计划以应对航班故障、维持竞争力和满足旅客需求。文章针对不正常航班的恢复问题建立了最小成本的数学模型，采用大规模邻域搜索的启发式算法求解，并针对国内某航空公司的航班数据进行仿真实验。实验结果表明，采用启发式算法对不正常航班进行一系列的恢复之后不仅可以降低恢复成本，还可以减少对于旅客出行带来的各种不便问题。

关键词： 航班恢复；大规模邻域搜索算法；不正常航班；算法设计；启发式算法

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2023）30-0115-04

开放科学（资源服务）标识码（OSID）

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） 数学模型

下标变量

i，j        节点的下标变量

k 飞机的下标变量

决策变量

xr：1表示飞机已经执行飞机路径r， r ∈ R；0表示飞机并未执行的飞机路径r，r ∈ R。

yf ：1表示航班f被取消，f ∈ F；0表示航班f未被取消，f ∈ F。

3） 数学公式

目标函数：

[minc（xr，yf）=f∈Fp∈Pr∈RF（f）dcrfpxr+cfyf]  （1）

约束条件：

[r∈RS（s）⋂RE（e）xr=hes]  （2）

[r∈RP（p）xr≤1]  （3）

[p∈Pr∈RF（f）dtrfpxr≤M]  （4）

（飞机流0-1型变量） xr={0，1} （5）

（取消流0-1型变量） yf={0，1} （6）

目标函数（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′）< c（ xr ， yf），则将当前解更新为（ xr′， yf′），并返回第2步；否则，转至第4步。

4） 输出（ xr ， yf）。

在航班恢复问题中，（ xr ， yf）表示航班恢复策略的状态，其中xr是已恢复的航班，yf是未恢复的航班。邻域 N（ xr ， yf）定义了如何生成当前解的相邻解，通常通过对航班恢复策略进行小范围的调整或交换来生成新解。函数c（ xr ， yf）衡量了航班恢复策略的质量或成本，目标是寻找最小成本的策略。

2.2 初始解构造

下面介绍一些关于初始解构造时所需要用到的参数：

[fi，j 原计划要被飞机pi所执行的第j个航班，pi∈P， arr（f） 航班f的入港机场，f∈F， dep（f） 航班f的离港机场，f∈F， gr（pi） 飞机pi的最短过站时间，pi∈P， std（f） 航班f计划起飞的时间，f∈F， off（f） 航班f的实际离港时间，f∈F， dur（f） 航班f在空中飞行的时间，f∈F， avaai 飞机pi开始可用的所在机场，pi∈P， avati 飞机pi的开始可用时间，pi∈P， Si 原计划将要执行的飞机pi的航班串， Stpi{fi，1，fi，2，…，fi，n}，pi∈P， cf（s） 机场s的宵禁时间，s∈S， RC 取消的路径集合 ]

初始解构造算法流程如下：

输入：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 < b < j，倘若不存在此种航班环，则寻找一个航班环[fc={f0，a，f0，a+1，...，f0，b}]并且满足a < j < b，令rc = rc ∪fc，S0 = S0 - fc，转到第3步。

第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<b<n，令rc = rc∪fc，S0  = S0  -  fc，转到第3步。

第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<n]，令[RC=RC⋃fc]，[S0=S0-fc]，转到第10步。

第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步：

将初始可行解输出。

3 计算结果分析

为了验证该算法的可行性，本节结合了航空公司的实际情况进行了分析。航班信息使用了国内某航空公司的某天航班计划，5架飞机在11个机场之间执行的22个航班，具体航班信息表见表1。