不正常航班恢復(fù)模型的貪婪模擬退火算法研究

摘 要:為解決不正常航班恢復(fù)對航空公司帶來的嚴(yán)重影響，研究了不正常航班恢復(fù)模型及其優(yōu)化算法，對現(xiàn)有不正常航班恢復(fù)優(yōu)化模型提出適當(dāng)改進，重點設(shè)計了一種貪婪模擬退火算法。算法融合了GRASP和模擬退火算法的特點，提高了領(lǐng)域解的選擇效率并且降低了陷入局部最優(yōu)解的概率。實例證明這種算法可以處理大規(guī)模的不正常航班恢復(fù)問題，并且能夠達到時間代價與結(jié)果質(zhì)量的均衡。

關(guān)鍵詞:不正常航班恢復(fù);領(lǐng)域解;GRASP;模擬退火算法

中圖分類號:F560 文獻標(biāo)識碼:A 文章編號:1003-5192(2010)01-0066-05

Research on Greedy Simulated Annealing Algorithm of

Irregular Flight Schedule Recovery Model

TANG Xiao-wei， GAO Qiang， ZHU Jin-fu

(College of Civil Aviation， Nanjing University of Aeronautics Astronautics， Nanjing 210016， China)

Abstract:Irregular flight schedule recovery is of great importance to the civil aviation industry. The model and optimization algorithm of irregular flight schedule recovery is researched in this Article. First proper improvement is made to the original model， and a new type of greedy randomized simulated annealing algorithm is designed. The new algorithm integrating the characteristics of simulated annealing algorithm and greedy randomized adaptive search procedure improves the efficiency of neighborhood selection and reduce the probability of falling into local optimal solution. Example proves that the algorithm is able to solve the problem of large-scale irregular flight schedule recovery， with the time cost suitable to the outcome quality. Key words:irregular flight schedule recovery; neighborhood; greedy randomized adaptive search procedure; simulated annealing algorithm

1 引言

不正常航班是指由于天氣、機械故障、流量控制等原因，造成航班延誤、備降或取消。據(jù)統(tǒng)計分析，我國2005年由于不正常航班引起的各類經(jīng)濟損失已經(jīng)超過30億元，同時造成巨大的社會影響。面對日益突出的不正常航班問題，社會各方面呼吁航空公司盡快采取有效解決措施。不正常航班的恢復(fù)首先是飛機計劃恢復(fù)，第二階段是機組恢復(fù)，第三階段是旅客中轉(zhuǎn)銜接恢復(fù)。關(guān)于飛機計劃恢復(fù)的決策對航空公司的收益影響最大，因此這一步也是最重要的。本文討論的不正常航班恢復(fù)指飛機計劃恢復(fù)。

航空公司為提高市場競爭力和最大化利用飛機資源，對航班計劃(包括飛機計劃和機組計劃)的優(yōu)化進行了較多的研究，航班計劃基本上沒有為應(yīng)對各種意外的變化留下足夠的松弛時間(Slack Time)[1]。因為飛機資源的備份成本極高，沒有一家航空公司愿意專門為應(yīng)付航班計劃變化而讓一架飛機空閑待命。這是造成航班不正常情況下運力調(diào)配困難的主要原因之一。此外，航班計劃的運作環(huán)境是不確定的，除了考慮飛機可用性、機組可行性和維修約束之外，機場跑道條件、高原地區(qū)飛行條件、航線限制等因素都會增加計劃調(diào)整的復(fù)雜性。

刻畫不正常航班恢復(fù)問題的準(zhǔn)確模型和尋找優(yōu)化算法一直是航空運籌學(xué)領(lǐng)域研究的熱點，快速有效的算法對于解決航空公司隨時可能發(fā)生的資源優(yōu)化利用問題將會產(chǎn)生巨大的經(jīng)濟效益。關(guān)于航空公司不正常航班恢復(fù)的研究可追溯到20世紀(jì)60年代。直至20世紀(jì)90年代中期，這方面的研究主要集中于單機型、小規(guī)模延誤的恢復(fù)問題[2~6]。但是單機型模型對于航空公司的作用不是很大，因為很少有航空公司是單一機型的，即使是單機型，同一機型各飛機之間的適航性也存在很大區(qū)別，本質(zhì)上來說也是多機型的。從20世紀(jì)90年代中后期至今，多機型、多經(jīng)停、大規(guī)模延誤的情況逐漸成為研究的重點，相繼出現(xiàn)了資源指派模型和多商品流模型[7~9]。不論是單機型模型還是多機型模型，面臨的一個共同問題就是算法的復(fù)雜性。不正常航班恢復(fù)優(yōu)化問題是一個約束眾多而復(fù)雜的實時網(wǎng)絡(luò)優(yōu)化問題，其解空間隨飛機和航班數(shù)量的增加而呈指數(shù)級增加，是一個多參數(shù)、多約束的NP-hard問題。目前應(yīng)用比較成熟的算法有GRASP算法、時空網(wǎng)絡(luò)算法等[7~9]。GRASP是一種啟發(fā)式算法，應(yīng)用于小規(guī)模問題(10架飛機以內(nèi))效果較好，但求解大規(guī)模問題的效率較低，收斂性較差，較易陷入局部最優(yōu)解;時空網(wǎng)絡(luò)算法試圖從重新構(gòu)造全新的飛機路線來減少延誤時間，這種思路使得問題的求解面臨巨大的困難，當(dāng)問題的規(guī)模達到20架飛機，80個航班以上時，時空網(wǎng)絡(luò)算法需要的計算時間遠遠超過30分鐘，很難達到航空公司實時控制的要求。

本文首先對文獻[10]提出的不正常航班優(yōu)化模型作適當(dāng)改進，重點提出了一種貪婪模擬退火算法。新算法包含GRASP算法中貪婪隨機的思想，并且通過設(shè)計領(lǐng)域解備選池提高了原GRASP算法的收斂性。算法還融合了模擬退火的特點，降低了問題陷入局部最優(yōu)解的概率。

2 不正常航班恢復(fù)優(yōu)化模型

(1)式為目標(biāo)函數(shù)，表達的是旅客總延誤時間由兩部分構(gòu)成，分別是延誤航班的旅客延誤時間和取消航班的旅客延誤時間;(2)式表達的是實際飛行的同一飛機路線上的航班所必須滿足的前后空間銜接關(guān)系，即前一個航班的到達機場必須與后一個航班的出發(fā)機場相同;(3)式表達的是實際飛行的同一飛機路線上的航班所必須滿足的前后時間銜接關(guān)系，即前一個航班的預(yù)計到達時間加過站時間必須少于等于后一個航班的預(yù)計出發(fā)時間;(4)式表達的是實際飛行的飛機路線應(yīng)當(dāng)滿足飛機流平衡，即恢復(fù)計劃在各機場的過夜飛機數(shù)應(yīng)與原計劃各機場的過夜機場數(shù)相同;(5)式表達的是航班滿足覆蓋原則，即原計劃的航班在恢復(fù)計劃中都應(yīng)被包括，要么在實際飛行的飛機路線中，要么在取消的飛機路線中，只能出現(xiàn)一次;(6)式表達的是所有航班的預(yù)計出發(fā)時間不超過出發(fā)機場宵禁時間，預(yù)計到達時間不超過到達機場宵禁時間。

3 原GRASP算法分析

在分析GRASP算法之前，需要先引入四個定義:航班環(huán)、航班串、實際飛行飛機路線、取消飛行飛機路線。

定義1 航班環(huán)，一組首尾相聯(lián)的航班，其中第一個航班的出發(fā)機場與最后一個航班的到達機場相同;

定義2 航班串，一組首尾相聯(lián)的航班，其中第一個航班的出發(fā)機場與最后一個航班的到達機場不同;

定義3 實際飛行飛機路線:以原計劃中的飛機號(4位數(shù)字)作為其后航班運行所使用飛機的飛機路線;

定義4 取消飛行飛機路線:以一個虛擬飛機號(虛擬飛機號以V開頭)作為其后航班運行所使用飛機的飛機路線。虛擬飛機實質(zhì)上不是航空公司所擁有的飛機，只是為了運算所假設(shè)的飛機。該飛機路線所包含的航班將被取消。

GRASP算法包括不斷循環(huán)的三個階段:一是從初始的執(zhí)行解(可行解)進行領(lǐng)域解的構(gòu)造;二是把較好的領(lǐng)域解放入RCL表(Restricted Candidate List，限制性候選列表)中;最后從RCL表中隨機選擇一個領(lǐng)域解來構(gòu)造執(zhí)行解。算法的具體操作都是建立在航班環(huán)與航班串上的，操作共分為7種:航班環(huán)的前綴、航班環(huán)的中綴、航班環(huán)的后綴、航班環(huán)的取消、航班串的尾接、具有相同的出發(fā)機場的航班串互換、具有相同的出發(fā)與到達機場的航班串互換。GRASP算法的不足表現(xiàn)為三個方面:

(1)GRASP算法提出領(lǐng)域解的構(gòu)造可以通過7種操作完成，有3種操作可以合并;

(2)RCL表的長度不容易確定，而且把領(lǐng)域解插入RCL表時進行排序操作，導(dǎo)致時間效率較差;

(3)GRASP算法中只有一個單一選擇的方向，就是向著成本更小的方向發(fā)展，但這樣容易陷入局部最優(yōu)解陷阱。

4 貪婪模擬退火算法

4.1 新算法領(lǐng)域解的構(gòu)造

本文模型以飛機路線作為基礎(chǔ)，因此優(yōu)化求解的過程實質(zhì)上就是構(gòu)造出新的飛機路線去替代上一個解中具有相同飛機號的飛機路線。為了保證飛機路線的產(chǎn)生過程不違背(2)、(4)、(5)式，新飛機路線的產(chǎn)生同樣按照GRASP算法提出的操作。經(jīng)分析GRASP算法中航班環(huán)的前綴、中綴和后綴操作可以合并為航班環(huán)的插入操作。這樣7種操作簡化為5種操作，這5種操作相當(dāng)于領(lǐng)域解的構(gòu)造，產(chǎn)生新的飛機路線。對于新產(chǎn)生的飛機路線，通過對航班ETD(預(yù)計出發(fā)時間)與ETA(預(yù)計到達時間)進行重排從而保證滿足約束(3)。重新排的方法是:

(1)以某一飛機的就緒時間作為該飛機實際飛行路線中首航班的ETD;

(2)首航班的ETA=首航班ETD+(首航班的STA-首航班的STD)，STA是計劃到達時間，STD是計劃出發(fā)時間;

(3)后續(xù)航班ETD=前一個航班的ETA+該飛機的過站時間;

(4)后續(xù)航班的ETA=該航班的ETD+(該航班的STA-該航班的STD)。

由于任意兩條飛機路線通過5種操作構(gòu)造的領(lǐng)域解的數(shù)量很多，一般情況下會達到10多個。如果航班計劃中的飛機路線的數(shù)量很多，則可以產(chǎn)生的領(lǐng)域解的數(shù)量極為龐大，因此從領(lǐng)域解構(gòu)造新的執(zhí)行解需要特殊的處理。

4.2 領(lǐng)域解備選池

一個執(zhí)行解就是一個航班恢復(fù)方案。從一個航班恢復(fù)方案中任意選取兩個飛機路線產(chǎn)生領(lǐng)域解，用領(lǐng)域解去替代執(zhí)行解中相應(yīng)的具有相同飛機號的飛機路線，這樣就構(gòu)造出新的執(zhí)行解。但是從原執(zhí)行解中任意選取的一對飛機路線可以產(chǎn)生的領(lǐng)域解很多。為了使算法確實可行，在每一對飛機路線產(chǎn)生的領(lǐng)域解需要對其進行評價選擇出最優(yōu)的領(lǐng)域解，如果這個領(lǐng)域解比產(chǎn)生它們的兩個飛機路線的延誤總成本小，則將其放入一個稱為成本降低解備選池中，如果這個領(lǐng)域解比產(chǎn)生它們的兩條飛機路線的延誤總成本大，則將其放入一個稱為成本增加解備選池。成本降低解備選池和成本增加解備選池統(tǒng)稱為領(lǐng)域解備選池。與原GRASP算法相比，新算法取消了RCL鏈表，改為領(lǐng)域解備選池。通過這種篩選將極大控制領(lǐng)域解的數(shù)量，并提高了算法的收斂性。

4.3 新算法執(zhí)行解的構(gòu)造

通過對所有的任意兩個飛機路線的兩兩組合，可以得到成本降低解備選池與成本增加解備選池中的領(lǐng)域解，再對其進行選擇構(gòu)造執(zhí)行解。選擇時采用隨機選擇方法，具體的選擇方法如下:

(1)為了保證(6)式的滿足，在算法中對于超過宵禁的飛機路線需要賦予充分大的延誤成本。在選擇時首先應(yīng)根據(jù)當(dāng)前執(zhí)行解是否存在超宵禁的飛機路線，如果存在，優(yōu)先選擇替換超宵禁的飛機路線的領(lǐng)域解，通過這種方法，在有限次數(shù)的迭代過程中就可以實現(xiàn)將不可行的執(zhí)行解轉(zhuǎn)化為可行的執(zhí)行解。

(2)如果執(zhí)行解中不存在超宵禁的飛機路線并且成本降低解備選池不空，就在成本降低解備選池隨機選擇一個領(lǐng)域解。

(3)如果執(zhí)行解中不存在超宵禁的飛機路線并且成本降低解備選池為空，說明此時從當(dāng)前的執(zhí)行解已經(jīng)不能找到使目標(biāo)函數(shù)值下降的方向。為了避免得到的執(zhí)行解是一個局部最優(yōu)解，按照模擬退火算法的思路，可以允許執(zhí)行解暫時向不好的方向發(fā)展。于是可以在成本增加解備選池中隨機選擇一個領(lǐng)域解。由于使執(zhí)行解成本增加的方向總是存在的，且領(lǐng)域解數(shù)量眾多。每次進行選擇時，先判斷成本增加解備選池中滿足(7)式的領(lǐng)域解的數(shù)量與備選池中領(lǐng)域解的比例，如果大于5%，從中隨機選擇一個領(lǐng)域解;反之則算法結(jié)束。

其中Δ為領(lǐng)域解增加的延誤成本;Kt為當(dāng)前的溫度值;random(0，1)為0-1間一個均勻隨機數(shù)。

當(dāng)選擇出領(lǐng)域解后，就可以對執(zhí)行解進行改造得到新的執(zhí)行解進行下一次迭代過程。如果沒有選出滿足各種條件的領(lǐng)域解，則自動退出算法。由于不正常航班恢復(fù)是一個實效性很強的工作，因此在算法中設(shè)置了時間控制函數(shù)，當(dāng)算法運行的時間達到了必須完成的時間，將強制退出算法。算法的總體流程圖如圖2。

5 實例分析

某一航空公司某一天的航班計劃由30架飛機，149個航班構(gòu)成，總的旅客人數(shù)為13109人。在尚未開始執(zhí)行時有五架飛機發(fā)生故障，另外空管告知航空公司有兩個機場由于特殊原因(軍事演習(xí))需要關(guān)閉，一個航班由于流控而延誤。上述案例是該航空公司在運行時遇到的較嚴(yán)重的不正常航班情況，其中一個基地機場ZSPD被關(guān)閉兩個小時，受影響的航班總數(shù)占當(dāng)天航班總數(shù)的25%。參考航空公司運營經(jīng)驗，每個旅客延誤1分鐘的成本為1元，取消航班按延誤8小時計算延誤成本，流不平衡的懲罰系數(shù)為100000。分別應(yīng)用貪婪隨機模擬退火算法和GRASP算法在P4 2.6GHZ，512M內(nèi)存的臺式機上對上述案例進行求解，結(jié)果如表1所示。

由表1可知貪婪隨機模擬退火算法和GRASP算法的運行時間均不超過1分鐘，滿足航空公司實時決策的時間要求。新算法得到的恢復(fù)方案中取消航班數(shù)為2，而GRASP算法為6，這主要是因為GRASP算法為了滿足流平衡約束，不得不取消更多的航班環(huán)。同時貪婪隨機模擬退火算法得到的恢復(fù)方案中延誤航班數(shù)量略有減少，而且結(jié)構(gòu)也更優(yōu)，其中短時間延誤(1小時以內(nèi))的航班數(shù)占總延誤航班數(shù)的54%，中等時間延誤(2~3小時)的航班數(shù)占39%，長時間延誤(4小時及以上的航班數(shù))的航班數(shù)占7%;而GRASP算法分別為17%、70%和13%。延誤總成本方面，貪婪隨機模擬退火算法得到的恢復(fù)方案更少，比GRASP算法節(jié)約了26%。GRASP算法取消的航班數(shù)較多，而延誤情況又沒有得到改善，陷入了局部最優(yōu)解。因此貪婪隨機模擬退火算法有效避免了陷入局部最優(yōu)解的陷阱。

6 結(jié)論

針對不正常航班恢復(fù)問題，本文對原不正常航班恢復(fù)優(yōu)化模型進行適當(dāng)改進，并結(jié)合GRASP和模擬退火算法設(shè)計了一種新算法。新算法用領(lǐng)域解備選池(包括成本增加解備選池和成本降低解備選池)替換GRASP算法中的RCL鏈表以提高算法的時間效率，在此基礎(chǔ)上新算法還融合了模擬退火算法的思想，有效地降低了陷入局部最優(yōu)解的概率。算法的不足主要表現(xiàn)為:模型對于目標(biāo)函數(shù)的設(shè)定沒有能包含不正常航班恢復(fù)問題的全部成本問題，如調(diào)機成本，更換機型的成本，這些都是模型與算法下一步改進的方向。

參 考 文 獻:

[1]Etschmaier M M， Mathaisei D F X. Airline scheduling: an overview[J]. Transportation Science， 1985， (2): 127-138.

[2]Teodorovic D， Guberinic S. Optimal dispatching strategy on an airline network after a schedule perturbation[J]. European Journal of Operational Research， 1984， (15): 178-182.

[3]Teodorovic D. Airline operations research[M]. New York: Gordon and Breach Science Publishers， 1988. 256-300.

[4]Cao J， Kanafani A. Real-time decision support for integration of airline flight cancellations and delays， part I: mathematical formulations[J]. Transportation Planning and Technology， 1997， (20): 183-199.

[5]Teodorovic D， Stojkovic G. Model to reduced airline schedule disturbances[J]. Journal of Transportation Engineering， 1995， (4): 324-331.

[6]Thengvall B G. Models and solution techniques for the aircraft schedule recovery problem[D]. Austin: The University of Texas， 1999.

[7]姚韻.航空公司不正常航班管理和調(diào)度算法研究[D].南京:南京航空航天大學(xué)，2006.

[8]Yan S， Young H. A decision support framework for multi-fleet routing and multi-stop flight scheduling[J].Transportation Research， Part A: Policy and Planning， 1996， (30): 379-398.

[9]Yan S， Tu Y. Multi-fleet routing and multi-stop flight scheduling for schedule perturbation[J]. European Journal of Operational Research， 1997， (103): 155-169.

[10]Michael F A， Jonathan F B. A grasp for aircraft routing in response to grounding and delays[J]. Journal of Combinatorial Optimization， 1997， (5): 211-228.