基于航班延誤的機(jī)場(chǎng)調(diào)度調(diào)整優(yōu)化研究

楊 歡，龐明寶，陳 靜

（河北工業(yè)大學(xué) 土木工程學(xué)院，天津 300401）

基于航班延誤的機(jī)場(chǎng)調(diào)度調(diào)整優(yōu)化研究

楊 歡，龐明寶，陳 靜

（河北工業(yè)大學(xué) 土木工程學(xué)院，天津 300401）

研究航班延誤所引起的機(jī)場(chǎng)航班調(diào)整優(yōu)化問題．在對(duì)航班延誤所引起的多方?jīng)Q策主體分析的基礎(chǔ)上，建立了包括乘客損失、機(jī)場(chǎng)運(yùn)營(yíng)成本增加、航空公司經(jīng)濟(jì)損失在內(nèi)的加權(quán)和最小化的機(jī)場(chǎng)航班優(yōu)化調(diào)整模型，采用遺傳算法優(yōu)化求解．具體機(jī)場(chǎng)的仿真實(shí)驗(yàn)表明該方法能快速實(shí)現(xiàn)航班調(diào)度動(dòng)態(tài)更新，調(diào)整的方案能兼顧到乘客、機(jī)場(chǎng)和航空公司各方利益，使機(jī)場(chǎng)具有較好的綜合服務(wù)水平，證明了該思想與方法的正確性與可行性．

智能運(yùn)輸系統(tǒng)；機(jī)場(chǎng)航班調(diào)度；航班延誤；遺傳算法；多主體決策

航班延誤這一世界性問題已成我國(guó)各大機(jī)場(chǎng)的普遍現(xiàn)象[1-4]．造成延誤的原因有多種，但主要是在空中交通擁擠基本約束前提下由于天氣原因、空域管制等不確定性因素所造成的[5-6]，且這些對(duì)民用航空管理部門、機(jī)場(chǎng)等均為無法預(yù)知的突發(fā)事件．而一旦延誤不僅對(duì)當(dāng)前也會(huì)給后續(xù)（當(dāng)天和很多天后）運(yùn)行的航班、乘客等造成影響和損失，如何在已知航班延誤信息的情況下盡快的調(diào)整后續(xù)機(jī)場(chǎng)航班計(jì)劃以便使航班運(yùn)營(yíng)恢復(fù)正常且使影響和損失最小化成為空中管制部門、機(jī)場(chǎng)、航空公司和乘客所關(guān)心的問題[6-11]．在理論研究方面，主要集中于從航空公司角度的航班延誤后恢復(fù)問題，具體通過建立航空公司追求經(jīng)濟(jì)損失最小化相關(guān)模型，并予以優(yōu)化處理得到新的調(diào)度方案[9-11]，而在經(jīng)濟(jì)損失計(jì)算方面，部分研究?jī)H考慮航空公司的損失，部分研究將可能對(duì)旅客的賠償計(jì)算在內(nèi)．顯然這些是在具體航管部門、機(jī)場(chǎng)大調(diào)度實(shí)現(xiàn)優(yōu)化前提下的具體航空公司調(diào)度優(yōu)化，沒有考慮到其它航空公司及其乘客的利益，不涉及機(jī)場(chǎng)可能增加的成本等，且航空公司對(duì)旅客的賠償與乘客的損失不是一個(gè)完全等同的概念．而從機(jī)場(chǎng)、航管部門角度研究航班延誤后機(jī)場(chǎng)調(diào)度較少，如胡明華以我國(guó)空域的基本情況和空中交通流量的相關(guān)特點(diǎn)為基礎(chǔ)[5]，提出多元受限的地面等待問題．這些為從機(jī)場(chǎng)、航管部門角度對(duì)可能造成的航班延誤后調(diào)整優(yōu)化調(diào)整提供基礎(chǔ)，但這些研究都是針對(duì)某一類特定情況的，沒有結(jié)合具體機(jī)場(chǎng)進(jìn)出港航班表進(jìn)行模型的建立及其相關(guān)優(yōu)化計(jì)算，不能實(shí)現(xiàn)航班延誤后快速的動(dòng)態(tài)更新；在計(jì)算目標(biāo)函數(shù)方面，僅考慮到航空公司和旅客損失兩個(gè)方面，且同等看待，沒有考慮到機(jī)場(chǎng)運(yùn)營(yíng)成本增加部分．實(shí)際上由于民用航空管理系統(tǒng)環(huán)境的不確定性以及動(dòng)態(tài)實(shí)時(shí)性，在出現(xiàn)航班延誤時(shí)，必須迅速的對(duì)后續(xù)航班進(jìn)行動(dòng)態(tài)調(diào)整才能滿足實(shí)際的基本需要，而科學(xué)公平合理的優(yōu)化調(diào)整才能滿足包括航空公司、機(jī)場(chǎng)、旅客等多方利益主體的需要，才能最大限度的提高民航服務(wù)水平和取得社會(huì)效益最大化；而在目標(biāo)函數(shù)值優(yōu)化計(jì)算方面，不僅需要考慮到航空公司、旅客兩方面損失，還需要考慮到機(jī)場(chǎng)可能增加的成本，且在不同條件下，三方權(quán)重可能有所差別，如旅客權(quán)重有所加大以體現(xiàn)公用基礎(chǔ)行業(yè)特點(diǎn)．基于此，考慮到問題的復(fù)雜性，本文從機(jī)場(chǎng)、航管部門角度，嘗試建立單一機(jī)場(chǎng)的包括乘客損失、機(jī)場(chǎng)運(yùn)營(yíng)成本增加、航空公司經(jīng)濟(jì)損失在內(nèi)的加權(quán)和最小化的航班延誤機(jī)場(chǎng)調(diào)度快速動(dòng)態(tài)調(diào)整優(yōu)化模型，通過算例來驗(yàn)證該思想方法的正確性．

1 機(jī)場(chǎng)調(diào)度動(dòng)態(tài)調(diào)整模型

在航班延誤情況下機(jī)場(chǎng)調(diào)度動(dòng)態(tài)調(diào)整必須考慮到航空公司損失、旅客損失和機(jī)場(chǎng)成本增加3個(gè)方面，且以機(jī)場(chǎng)航班調(diào)度仿真模型為基礎(chǔ)平臺(tái)．模型中變量表示為：F為航班的集合，J為管制區(qū)集合，T為航班可行的起飛時(shí)間段集合；角標(biāo)中 i為航班下標(biāo)，j為管制區(qū)下標(biāo)，t為時(shí)間下標(biāo)，本模型中 1m in為一個(gè)離散化步長(zhǎng)，k 為飛機(jī)下標(biāo)．DTi為航班 i預(yù)計(jì)起飛時(shí)間，為最大延誤時(shí)間為 t時(shí)刻管制區(qū) j的容量，Ds t 為 t時(shí)刻機(jī)場(chǎng)的起飛容量，As t 為 t時(shí)刻機(jī)場(chǎng)的降落容量，vi為航班 i實(shí)際載客人數(shù)，pi為航班 i的票價(jià)，Et為等待在機(jī)場(chǎng)上空準(zhǔn)備降落的飛機(jī)數(shù)，Vt為等待在機(jī)場(chǎng)起飛的飛機(jī)數(shù)，ti為航班 i的實(shí)際起飛時(shí)間，為相鄰兩架航班最小起降時(shí)間間隔．w1、w2、w3分別為航班動(dòng)態(tài)調(diào)整時(shí)決策者對(duì)旅客，機(jī)場(chǎng)，航空公司的權(quán)重，即偏重程度，gk為飛機(jī) k 單位時(shí)間的延誤成本，S 為每位旅客單位時(shí)間的損失成本，ci為取消航班i的成本 （按照延誤 8 h的延誤成本計(jì)算取消成本），Hi為每位旅客單位時(shí)間的恢復(fù)成本 （包括賠償費(fèi)、安置費(fèi)、轉(zhuǎn)簽費(fèi)）等．

gk為條件變量，用于確定不同型號(hào)飛機(jī)的單位時(shí)間損失成本，本研究具體定義為

以一個(gè)機(jī)場(chǎng)為例，其優(yōu)化模型表示為

模型中目標(biāo)函數(shù)即式 (1) 表示追求加權(quán)總成本費(fèi)用最小化，其中第 1 項(xiàng)、第 2 項(xiàng)為乘客費(fèi)用，分別表示旅客失望溢出成本和旅客延誤損失，第3項(xiàng)為機(jī)場(chǎng)負(fù)擔(dān)的恢復(fù)成本，即機(jī)場(chǎng)增加的成本，第4項(xiàng)、第5項(xiàng)分別表示航空公司的延誤成本和取消成本．

約束中式 (2) 表示航班 i實(shí)際起降時(shí)間不能早于計(jì)劃起降時(shí)間；式 (3) 為航班延誤時(shí)間不能超過飛機(jī)最長(zhǎng)延誤時(shí)間；式 (5) 是 t時(shí)刻等待起飛的飛機(jī)數(shù)量不能超過 t時(shí)刻機(jī)場(chǎng)跑道的起飛容量；式 (6) 是 t時(shí)刻等待降落的飛機(jī)數(shù)量不能超過 t時(shí)刻機(jī)場(chǎng)跑道的降落容量；式 (7) 是 t時(shí)刻起飛的飛機(jī)數(shù)量不能超過管制區(qū)的容量；式 (8) 為 0-1 變量約束．式 (4) 為對(duì)相鄰兩架飛機(jī)起（降） 時(shí)間間隔約束，按照民航具體規(guī)定標(biāo)準(zhǔn)為：前機(jī)為大型機(jī)時(shí)，后機(jī)為大型機(jī)、中型機(jī)、小型機(jī)的時(shí)間間隔最低標(biāo)準(zhǔn)分別為 1.5m in 、2m in 、2.5min ；前機(jī)為中型機(jī)時(shí)，后機(jī)為大型機(jī)、中型機(jī)、小型機(jī)的時(shí)間間隔最低標(biāo)準(zhǔn)分別為 1m in 、1m in 、1.5min ；前機(jī)為小型機(jī)時(shí)，時(shí)間間隔最低標(biāo)準(zhǔn)分別為 1m in ．

式 (10) 表明本優(yōu)化模型是建立在機(jī)場(chǎng)運(yùn)營(yíng)調(diào)度仿真模型基礎(chǔ)上．

2 模型的優(yōu)化求解

考慮到模型中決策變量為 0-1 變量，本研究采用浮點(diǎn)遺傳算法進(jìn)行優(yōu)化求解，具體步驟為：

1）設(shè)定遺傳算法的各參數(shù)：群體規(guī)模 MN 、最大迭代次數(shù) NN 、交叉概率 JPc、變異概率 JPm、代溝 G等．定義適應(yīng)度函數(shù)為

其中MMM為非常大的數(shù)．

2）隨機(jī)產(chǎn)生 MN 組可行的航班調(diào)整方案，其中編碼采用二進(jìn)制，決策變量作為染色體，為 1值編碼為1，否則為 0．同時(shí)設(shè)置迭代計(jì)數(shù)器．

3）在第 n代，計(jì)算每一個(gè)個(gè)體（即航班調(diào)整方案）的適應(yīng)度．

4）若 n＞=NN ，選擇最優(yōu)個(gè)體為最佳航班調(diào)整方案，輸出．否則轉(zhuǎn)向 5）．

5） 選擇最 優(yōu) Noverlap=MN × 1 G 個(gè) 個(gè)體直接 進(jìn)入下一 代．同時(shí) 按照遺傳 算法復(fù) 制、交叉 和變異規(guī) 則，產(chǎn)生下一代其余 MN Noverlap個(gè)個(gè)體，即新一組可行的航班數(shù)．

6）令 n=n+1 ，轉(zhuǎn)向 3）．

3 實(shí)驗(yàn)分析

為說明問題，本文以呼和浩特機(jī)場(chǎng)某一天航班調(diào)度為例進(jìn)行分析．該機(jī)場(chǎng)正常航班時(shí)刻表見表1（僅列出部分航班）．假定每位乘客單位時(shí)間的延誤成本 S 為 2 元/min ，每位乘客單位時(shí)間的恢復(fù)成本 Hi為 2 元/min ．

假設(shè)該天早晨 7:20 呼和浩特機(jī)場(chǎng)下霧，導(dǎo)致航班延誤，預(yù)計(jì)在上午 9:00 恢復(fù)正常，可以正常起飛；上午 8:00 接到臨時(shí)通知，10:20 的GS6485 航班飛機(jī)由于起飛時(shí)出現(xiàn)故障，晚點(diǎn) 30m in到達(dá)呼和浩特機(jī)場(chǎng)；該天 12:30 到 15:30 進(jìn)行空中管制，不允許進(jìn)行飛機(jī)的起降．對(duì)于延誤航班，該機(jī)場(chǎng)盡可能在當(dāng)天 24:00之前全部起飛，不取消航班，不影響明天航班的正常運(yùn)行．

取 w1w2w3=1 1 1 ，按照 1、2 的方法確定后續(xù)航班新的時(shí)刻表，其中遺傳算法求解時(shí)群體規(guī)模MN=40，代溝 G=0.9 ，交叉概率 JPc=0.7 ，變異概率 JPm=0.05 ，最大迭代次數(shù) NN=600 ．具體目標(biāo)函數(shù)均值及其每代最優(yōu)值變化見圖1，可以看出迭代到第 100 代時(shí)，開始收斂，達(dá)到最優(yōu)，這表明本方法快速更新后續(xù)航班的可行性．優(yōu)化后的航班時(shí)刻表（方案 1）見表1，其中旅客損失、機(jī)場(chǎng)成本增加和航空公司損失分別為 3 509.23 、1 191.43 、5 716.95 萬元，總目標(biāo)函數(shù)值為 10 417.61 萬元，顯然在各種成本費(fèi)用中航空公司損失最大，其次為旅客損失，而對(duì)機(jī)場(chǎng)等損失最?。?/p>

圖1 600 代目標(biāo)函數(shù)最優(yōu)值、均值的變化Fig.1 Changesof thebestobjective function valueand the averageobjective function valuebefore the600th generation

為對(duì)優(yōu)化方案進(jìn)行比較，本研究按照現(xiàn)有航班延誤后調(diào)度更新方案（方案2）進(jìn)行調(diào)整，該方案為在不影響其他正常航班起降的情況下，對(duì)已有延誤航班進(jìn)行插空安排，調(diào)整后的航班時(shí)刻表略，其中一些航班找不到合適的插空位置，造成航班長(zhǎng)時(shí)間延誤，使得乘客大規(guī)模的滯留在機(jī)場(chǎng)．方案1和2具體造成的部分航班延誤時(shí)間比較和成本比較見表2和表3．可以看出：采用本研究方法優(yōu)化后方案的總延誤時(shí)間小于根據(jù)經(jīng)驗(yàn)插空安排的未優(yōu)化方案的總延誤時(shí)間，總成本費(fèi)用 10 417.61 萬元也小于依據(jù)經(jīng)驗(yàn)方案的 10 657.52 萬元．雖然依據(jù)經(jīng)驗(yàn)調(diào)整的航班時(shí)刻表能保證正常航班的起降，但大大延長(zhǎng)了延誤航班上乘客的等待時(shí)間，造成大批乘客在機(jī)場(chǎng)滯留和航空公司航班的大調(diào)整，而本優(yōu)化方案雖然會(huì)影響很多正常航班的起降時(shí)間，但在乘客損失、機(jī)場(chǎng)成本增加和航空公司損失以及合計(jì)方面均優(yōu)于傳統(tǒng)方案．且一些出現(xiàn)較短延誤的航班，延誤時(shí)間較短，大部分乘客可能在承受的范圍內(nèi)；對(duì)航空公司而言，小的延誤可能在飛行途中趕回，即使不能趕回也對(duì)其可能的后續(xù)航班影響較小，這進(jìn)一步證明了本研究方法的有效性．

為進(jìn)一步說明優(yōu)化更新機(jī)場(chǎng)航班延誤時(shí)對(duì)各個(gè)主體利益的偏重，本研究對(duì)乘客、機(jī)場(chǎng)和航空公司利益取不同權(quán)重值時(shí)各項(xiàng)成本、總成本、加權(quán)總成本和歸一化后的總成本進(jìn)行實(shí)驗(yàn)比較，具體見表4．可以看出：三者的不同偏好，目標(biāo)函數(shù)值會(huì)產(chǎn)生較大差異．由于當(dāng)航班出現(xiàn)延誤時(shí)，航空公司承擔(dān)絕大部分的損失成本（包括乘客損失有可能由航空公司承擔(dān)），其次是旅客和機(jī)場(chǎng)；而從整體航空調(diào)度而言社會(huì)效益最大化是優(yōu)先目標(biāo)，其次是航空公司的經(jīng)濟(jì)利益，而對(duì)機(jī)場(chǎng)等航空管理機(jī)構(gòu)而言，由于其損失較小，而以其較小損失取得其它主體利益最大化是其應(yīng)追求的，所以以優(yōu)先偏重乘客利益，再偏重于航空公司利益，而最不偏重機(jī)場(chǎng)利益的方案為較佳選擇．

表2 經(jīng)驗(yàn)方案與優(yōu)化方案造成的部分航班延誤時(shí)間比較 m inTab.2 Comparison of delay time in partial flightsbetween normalupdating projectand optim ized project

表3 經(jīng)驗(yàn)方案與優(yōu)化方案各部分成本比較 萬元Tab.3 Comparison of the partial costbetween normalupdating projectand optim ized project

表4 不同偏好的優(yōu)化方案各項(xiàng)成本比較 萬元Tab.4 Costcomparison among optim ized projectsw ith the different favors

4 總結(jié)

在對(duì)航班延誤所引起的多方?jīng)Q策主體分析的基礎(chǔ)上，建立了包括乘客、機(jī)場(chǎng)和航空公司在內(nèi)的加權(quán)和最小化的機(jī)場(chǎng)航班優(yōu)化調(diào)整模型，具體機(jī)場(chǎng)的仿真實(shí)驗(yàn)證明了該思想與方法的正確性與可行性．該方法僅是機(jī)場(chǎng)航班延誤優(yōu)化調(diào)度的初始研究，僅限于單一機(jī)場(chǎng)，而進(jìn)行多個(gè)機(jī)場(chǎng)航班延誤后的動(dòng)態(tài)調(diào)度優(yōu)化研究，并將其推廣到具體機(jī)場(chǎng)運(yùn)營(yíng)調(diào)度中將是下一步工作內(nèi)容．

[1] 李雄，劉光才，顏明池，等．航班延誤引發(fā)的航空公司及旅客經(jīng)濟(jì)損失 [J]．系統(tǒng)工程，2007，25（12）：20-23．

[2]Teodorovic D，StojkovicG．Modelto reducedairlinescheduledisturbances[J]．Journalof Transportation Engineering，1995，121（4）：324-331．

[3]Goran Stojkovic，F(xiàn)rancoisSoumis，JacquesDesrosiers．Anoptim izationmodel fora real-time flightscheduling problem[J]．Transportation Research PartA，2002，36（9）：779-788．

[4]Lan S，Clarke JP，BarnhartC．Planning for robustairlineoperations:optimizing aircraft routingsand flightdeparture times tom inim ize passenger disruptions[J]．Transportation Science，2006，40（1）：15-28．

[5] 胡明華．空中交通流量管理理論與方法 [M]．北京：科學(xué)出版社，2010．

[6] 馬輝，林晨．航班調(diào)度應(yīng)急管理研究 [J]．中國(guó)民航學(xué)院學(xué)報(bào)，2005，23（5）：1-4．

[7] 白鳳，朱金福，高強(qiáng)．基于列生成法的不正常航班調(diào)度 [J]．系統(tǒng)工程理論與實(shí)踐，2010，30（11）： 2036-2045．

[8] 高強(qiáng)，嚴(yán)俊，陸宏蘭．不正常航班旅客流恢復(fù)方法 [J]．科學(xué)技術(shù)與工程，2011，11（27）：1-4．

[9] 趙秀麗，朱金福，郭梅．不正常航班延誤調(diào)度模型計(jì)算 [J]．系統(tǒng)工程理論與實(shí)踐，2008，28（4）：2-4．

[10] 解天榮．基于延誤成本的進(jìn)港航班調(diào)度優(yōu)化研究 [D]．北京：北京交通大學(xué)，2008．

[11] 文優(yōu)梅．基于遺傳算法的航班進(jìn)離港優(yōu)化調(diào)度算法研究 [D]．長(zhǎng)沙：中南大學(xué)，2010．

[責(zé)任編輯 楊 屹]

Optim ization of updating forairportscheduling based on flightdelays

YANG Huan，PANGM ing-bao，CHEN Jing
(Schoolof CivilEngineering,HebeiUniversity of Technology,Tianjin 300401,China)

Theoptim ization ofupdating airportscheduling upon flightdelayswasstudied.Based on themulti-agentanalysis arising by flightdelays,amodelof optim ized updating scheduling for airport flightwas established tom inim ize the weightsum,which includes the lossofpassengers,the increasing operation costofairport,and the lossofairline corporations.Genetic algorithm wasadopted in theoptim ization course forsolution.Thesimulation resultof theconcreteairport indicates that the goalof dynamic updating rapidly flightscheduling is realized,the interestsof passengers,airport,and airline corporations are taken into account,and the airporthas a better synthetic service level by choosing themethod. And it thus proves the feasibility of themethod.

intelligent transportation system(ITS);airport flightscheduling;flightdelays;genetic algorithm(GA); multi-agentdecision

1007-2373(2014)05-0101-05

F562；V355

A

10.14081/j.cnki.hgdxb.2014.05.020

2013-11-09

河北省自然科學(xué)基金（E2011202073）

楊歡（1990-），女（漢族），碩士生．通訊作者：龐明寶（1966-），男（漢族），教授，博士．