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

李星宇，徐衍霏，魯亮，付澤昊，馮健鎧

（中國民航大學計算機科學與技術學院，天津 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)衡量了航班恢復策略的質量或成本，目標是尋找最小成本的策略。

2.2 初始解構造

下面介紹一些關于初始解構造時所需要用到的參數：

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

輸入：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步：

將初始可行解輸出。

3 計算結果分析

為了驗證該算法的可行性，本節結合了航空公司的實際情況進行了分析。航班信息使用了國內某航空公司的某天航班計劃，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 使用大規模鄰域搜索算法前后結果比較

4 結論

本文針對飛機延誤或停場的情況下進行不正常航班的恢復，將航空公司的損失降到最小，使用大規模鄰域搜索算法得出航班的初始可行解，后逐次迭代，將結果趨于一個最接近最小成本的值，其對應的航線即為最后得出的可行解。

圖2 調機后的甘特圖

不正常航班恢復對于中國民航具有重要意義。首先，對于旅客而言，不正常航班恢復將減少旅行不便和不確定性，使旅客按照計劃安排行程，減少延誤所產生的影響。其次，對航空公司而言，不正常航班恢復將幫助航空公司減少虧損，提高收益。總體而言，正常航班的恢復對于中國民航來說，意味著經濟的復蘇、旅客的出行方便以及航空公司的盈利。