楊 歡，龐明寶，陳 靜

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

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

楊 歡，龐明寶，陳 靜

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

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

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

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

1 機場調(diào)度動態(tài)調(diào)整模型

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

gk為條件變量，用于確定不同型號飛機的單位時間損失成本，本研究具體定義為

以一個機場為例，其優(yōu)化模型表示為

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

[1] 李雄，劉光才，顏明池，等．航班延誤引發(fā)的航空公司及旅客經(jīng)濟損失 [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]．中國民航學(xué)院學(xué)報，2005，23（5）：1-4．

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

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

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

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

[11] 文優(yōu)梅．基于遺傳算法的航班進離港優(yōu)化調(diào)度算法研究 [D]．長沙：中南大學(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-），男（漢族），教授，博士．