1、不正常航班及其調度問題一、 摘要本文構建了以延誤成本最小最短為目標函數的航班恢復模型，航空公司可以根據 需要選擇不同的目標函數；細分了延誤成本并采納了旅客失望溢出成本和失望溢出率概 念；采用啟發式方法并調用匈牙利算法對模型求解，給出了算法的運行步驟，并與問題 一及問題二的初步分析作比較，說明了模型和算法的可行性.關鍵詞：不正常航班調度；航班延誤；旅客失望溢出成本 ；匈牙利算法二、問題的提出隨著國民經濟的高速發展和航空運輸市場需求量的不斷增長，國內各家航空公司 相應加大了運力的投入。目前，我國空中交通流量分布不均衡，起降架次排名前十位機 場的總起降次數占到全國總起降次數的一半以上，京、滬、穗機場

2、到達終端區和華東部 分區域空中交通容量已基本處于飽和狀態，致使航班延誤不斷增加，給航空運輸企業和 旅客帶來了不小的直接和間接經濟損失。航空公司之間的競爭日益劇烈，如何在不正常 情況下實時地對航班進行調度，對飛機、機組人員進行重新優化指派，對旅客行程進行 優化安排，對增加航空公司利潤和提高競爭力顯得尤為關鍵。本文由航空公司給出的不 正常航班及其調度簡化模型以及部分飛機飛行路線、時間、可交換機型、飛機延誤、機 場關閉等數據，通過個人查找資料以及給出的賠損措施設計合理的航班恢復計劃，使航 空公司在出現不正常的航空問題時，可以及時使對外虧損減到最小。問題一：航班 ZLXY 在13: 00-15: 00

3、以及ZGKL在19: 00-21: 00被迫關閉兩 個小時的情況下，設計一個航班恢復計劃，使得航空公司損失達到最小。問題二：2153飛機14: 35在機場ZSPD過站檢查時發現機務故障，估計飛機當天 不可使用，5145飛機14: 00在機場ZGHA過站檢查時發現機務故障，估計 16: 00可 以使用。試設計一個航班恢復計劃，使得航空公司損失達到最小。問題三：同時考慮機場臨時關閉和發現機務故障的情況下，建立數學模型，給出 一個航班恢復計劃。使得航空公司損失達到最小。三、問題分析由于一架飛機在一天中要執行多個航班，各航班之間存在前后銜接關系，因此，一 個航班的延誤會波及到下游許多其他航班。局部的航

4、班延誤很容易演化為大面積的航班不正常。當不正常情況出現時，運行調度人員會根據航班的計劃時間、飛機的航線、飛 機的維護和保養計劃，以及機組的編排計劃等一系列信息，考慮飛機資源的重新分配， 提出飛機計劃的調整方案，盡量使航空公司的航班能在較短的時間內恢復正常。調度人 員在人工決策時，一般的指導原則是，采用最簡單的調整方案，使得受影響的航班最少。我國航空公司機隊規模小，飛機資源稀缺， 國內航空公司在不正常航班的恢復調整中一般都采取能延誤則延誤，迫不得已再取消的策略，而且通常不會對計劃的恢復設時間限制，只要求調整方案保證在飛行日結束恢復 原計劃的機型配置，盡可能不影響次日計劃的執行。從解決不正常航班問

5、題的過程來看， 計劃的調整主要是進行飛機的調配和機組的調配，飛機的調配是為了重新部署飛機的資 源，使得在未來的某一個時刻，各架飛機能 夠在所要求的時間處于正確的機場位置，滿足更改后航班的需要。本文主要研究飛機的調配。一般來說，解決不正常航班有以下五種策略：(1)、航班順延；(2)、飛機置換;(3)、調飛機；(4)、取消航班；(5)、合并航班。對于題中的問題，我們可以按照給出 的五個方面進行分析。四、條件假設(1)假設每一個機場中沒有空閑或者備份的飛機；(2)延誤成本等于單個延誤事件帶來成本的總和；(3)每個延誤事件帶來的成本是延誤時間的線性函數，即：延誤成本=延誤時間父飛機的單位時間運營成本；

6、(4)假設無論是否發生緊急情況，飛機從一地到另一地所用時間都不會改變；(5)假設航班計劃沒有為應對各種意外的變化留下松弛時間，即機場中飛機的降落于 起飛之間的時間差恒定不變；(6)假設題目中給定的每個旅客延誤一分鐘的成本為一元包含航空公司的地面延誤損 失、空中延誤損失、食宿調機損失和旅客的時間價值損失等的平均值，不包含各種情況 所帶來的隱性成本；(7)機場關閉期間可以正常進行飛機檢修等各項飛前準備工作；(8)飛機發生機務故障檢修成功后即可不必再由準備工作而直接進入正常航行；(9)假設方案盡量不打亂飛機的平衡流；(10)假設ZGKL在19:0021: 00被迫關閉兩個小時；(11)假設兩種飛機的

7、單位時間內運營成本相同。五、符號約定參考文獻【4】的優化處理方案，為了簡化敘述，下面定義一些參數和集合:i是飛機指示；f是航班下標；集合：a：執行航班f的飛機;af :替換航班，的飛機;工：可用飛機的就緒時間集合；T；:最早延誤航班之后的航班原計劃到達時間集合;F :最早延誤航班之后的航班集合；A：最早延誤航班之后可用飛機集合；A：能夠執行，航班任務的機型集合；Am：能夠在m機場維修的機型為，的飛機集合;Z:當天可調用飛機的集合；變量：x：:時間對i到，的航班;yf：取消航班f的標志，為1取消，為0不取消;Pf ：航班f上的旅客失望溢出成本,其中 t=TTj ；Pj =Pf +£ c

8、bxj ,第b三ZPj ： i時刻就緒的飛機執行j時刻的航班及后續航班的延誤成本, 一項是旅客失望溢出成本，第二項是調運可使用飛機的成本;cf ：把航班f指派給可使用飛機的成本;xb： O, 1變量，當天可用飛機b指派給航班f為1,否則為0六、模型建立1、航班順延我們考慮到：航班延誤不僅造成了飛機成本，而且也帶來了隱性損失。因而應結合 各部分，把延誤成本分為兩部分：顯性成本和隱性成本。顯性成本即航班延誤給航空公 司造成的直接經濟損失，其中又包括航班地面延誤成本、空中延誤成本和由于航班延誤 而導致的旅客食宿問題等。隱性成本即航班延誤對航空公司聲譽及形象造成損壞，航班 頻繁延誤使航空公司在旅客面前

9、失去信譽，這是導致高價值商務旅客流失的主要原因。（1）顯性成本計算：由于基本上所有的損失都是付與待機旅客，因此為了簡化問題，參考航空公司運營經驗，每個旅客延誤一分鐘的成本為 1元，取消航班按延誤8小時 計算延誤成本。根據假設，首先計算單個航班延誤帶來的單位時間內的飛機運營成本，然后用這段延誤時間去乘上單位時間內的飛機運營成本，得到單個航班的飛機延誤成本。再把航空公司飛機在該機場延誤時間段的各個飛機的延誤成本相加即得延誤成本總 和。A）單位時間內飛機運營成本計算：p =M父p', （ i標記飛機型號，M為單位時間耗油，p為油價）經查資料計算，飛機的單位時間內運營成本分別約為 300元/分

10、鐘。B）單個航班的飛機延誤成本：P =tMR , （i,R意義同上，t為該機延誤時間段）C）延誤總成本：P =£ P , （ Pi意義與上同）（二）隱性成本計算：由于諸多原因導致航空公司航班不能正常的在規定的航線上 按時航行，這將導致旅客朋友們不能按原計劃到達目的地，這勢必影響到航空公司在旅 客心目中的形象。甚至讓選擇該航空公司的旅客對該航空公司產生失望情緒，導致下一 次消費時放棄選擇該公司的航班而選擇其它公司的航班或者改用其它交通工具隊對公 司造成的損失旅客失望率定義：由于航班延誤使旅客對航空公司信譽失望， 在下一次消費選擇時 不選該公司航班的概率，旅客失望與延誤時間有關。旅客失望

11、溢出成本函數與旅客人數、票價和旅客失望率有關。最大失望溢出成本為 本航班上的所有旅客在下一次消費是都不選擇該公司的航班，此時旅客失望溢出成本 為：乘客人數M平均票價，旅客失望率為1,極度失望，下一次100%不選擇該公司的航 班。旅客失望溢出成本采用公式：P=VMWMU。參考文獻【2】，作者根據專家意見制定了旅客失望溢出率調查表，在候機廳發放調查表1000份，回收有效表 970份，通過曲線擬合，得到旅客失望率計算函數：3： t/u = 1 60 , U是延誤時間t （min）的函數。29綜上所述，航班順延不但造成飛機延誤成本，還涉及旅客失望溢出成本問題。2:飛機置換飛機置換即當某一航班發生延誤時

12、 ，由本機場的飛機來替代延誤飛機執行航班任 務。簡單的說即由該機場i時刻航班由執行j時刻航班的飛機來執行任務，其成本模型 的計算類似于航班順延成本的計算。用數學語言來描述它，即i時刻航班由j時刻航班的飛機來執行，則不存在飛機的等待成本但是旅客航班則延誤了 j - i時間，則長生延誤成本，其中成本包含旅客食宿, 旅客失望溢出成本則Cj = F + P其中F為延誤時間內的為旅客提供食宿費用，P為航班延誤的旅客失望溢出成本。同樣如果飛機置換的過程中機型改變了，則成本中應再加入機型改變成本這一項。3:調飛機調飛機就是從某一機場調配一架飛機到異地執行任務。在業務上考慮到成本的因 素，調集一般以就近為原則

13、，選擇鄰近的異地機場飛機執行任務。其中也涉及到機型是 否改變問題，與飛機置換策略考慮的問題類似。由假設如果飛機出現緊急故障，可以采 用調機策略來解決。飛機由其他機場調運到當前機場的成本決定于兩機場之間的距離和飛機每公里運 營成本兩個因素，飛機每公里運營成本由其中飛機每公里運營成本由機型決定，則調飛機成本Cre表達成數學模型為：Cre=調運距離X機型e每公里運營成本其中每種機型的飛機運營成本和年運輸里程數據都可以搜集到。用各種機型的飛 機的年運營成本分別除以各自的運輸飛行里程，即可得到各種機型的單位里程飛行運營 成本。4:取消航班取消航班及飛機不執行飛行任務，這對旅客造成的影響很大，也會給航空公

14、司帶來 比較大的經濟損失。因此通常盡量少取消航班。但具體到實際問題有時也不得不取消航 班。因此本題取消航班可作為一個基本策略。具體如下：取消航班成本也分為顯性承辦現金賠償和隱性成本顧客失望溢出成本。由題意航空公司取消航班則要給旅客賠償金額按八小時延誤計算。顧客失望溢出成本的計算在航班順延中已經通過調查統計得到。問題一：根據題目中的條件，航班ZLXY在13: 00-15: 00以及ZGKL在19: 00-21: 00被迫關閉兩個小時，由附表中2010年6月20日整天的部分機場和路線飛行路線表知： 在13: 00-15: 00期間于ZLXY機場降落或者起飛的飛機共有兩趟，其情況如下表：航線航班起飛

15、 機場起飛時間降落 機場降落時間2686B738ZSPDF9203ZSPD201006201000.00ZLXY201006201235.00F9282ZLXY201006201410.00ZBAA201006201555.00F9281ZBAA201006201700.00ZLXY201006201840.00F9210ZLXY201006202100.00ZSPD201006202250.005130B738ZLXYF9202ZLXY201006201300.00ZSPD201006201450.00F9183ZSPD201006201550.00ZYTX201006201800.00F9

16、184ZYTX201006201850.00ZSPD201006202050.00F9741ZSPD201006202130.00VTSP201006210210.00根據已知定義，如果考慮調飛機或者置換飛機顯然不僅要求飛機延誤，還要增加 調飛機或者置換飛機的成本，使得航空公司的損失會更大，因此這兩種方案予以舍棄。 只能考慮其他三種方案。由于此種情況比較簡單，因此我們可以對各種情況進行分析。首先從表中我們得知5130航線中B738機型的飛機在13:00時已從機場ZLXY起 飛，再次回到ZLXY的時間為18: 00。即該航線該機跳過了該機場的關閉時間。因此 只考慮表中的2686航線：（a）對于航

17、班順延的方案：F9282航線的B738飛機，它的航班延誤時間為 T1,又由假（5）, F9281、F9210航線只能依次往后延誤，因此它的延誤顯性成本為3F2=v Ni T1 P1i 1（每個人的延誤時間為T1,三個航線的人數依次為 NN2、每個旅客延誤1分鐘的成本為p1 ）隱性成本（旅客失望溢出成本）為 3F3 = 1 ：'：Vi Wi Uii 1（Vi為該機該次的乘客數量，Wi該機該次票價，Ui為失望率，i = l, 2, 3）此公式是在充分調研旅客溢出成本的基礎上給定的2由上文的公式（Ui可得到 Ui ( i = 1 , 2 , 3 )總的調運成本為：P> =P2+&quo

18、t;=91437元（b）再考慮取消航班的情況：依假設（5）如果我們只取消航班，由于取消航班后不需再付出那一部分運營成本, 故而其顯性成本為3P2Ni 心pi -3 TiVip2i 1（Ti、Ni、N2、N3、R的意義與上同，且 不取8X60 = 480分鐘，B738機型每分鐘耗油體積Vi,油價為p2）隱性成本（旅客失望溢出成本）為2P3 = j：ViWiUii i（其中Vi為該機該次的乘客數量，W該機該次票價，Ui為失望率且Ui取i, i = 1 ,2）由假設（5）可知，其它情況均沒有上述兩種情況優良。故而可以確定出在問題一 的情況下不正常航班調度的恢復方案。總的調運成本為：Pb =P2+P3

19、 =ii8679元比較B與R可知：延誤方案可以把不正常航班的損失減少到最小問題二：2i53飛機i4: 35在機場ZSPD過站檢查時發現機務故障，估計飛機當天 不可使用，5i45飛機i4: 00在機場ZGHA過站檢查時發現機務故障，估計 i6: 00可 以使用。根據題目中附表得到這兩趟航班的情況如下：航線航班起飛 機場起飛時間降落 機場降落時間2i53B738RKSIRKSI20i00620i250.00ZSPD201006201435.00ZSPD201006201540.00VMMC201006201820.00VMMC201006201910.00ZSPD201006202140.00ZS

20、PD201006202240.00VVNB201006210200.005i45B738ZSPDZSPD20i00620i2i0.00ZGHA201006201400.00ZGHA201006201455.00ZSPD201006201630.00ZSPD20i00620i730.00ZJHK20i006202025.00ZJHK20i006202i20.00ZSPD20i006202340.00由于飛機出現機務故障后的恢復情況有很多種，下面分航線分問題逐一簡單討論：先考慮航線2153，依表中數據可知該機B738于14: 35在機場ZSPD過站檢查時發現機務故障，這一情況將直接或間接影響到后繼

21、航線的正常運行。因為該機估計當天不可使用，故而航班順延和航班取消有相同的效果 ：(a)航班取消(航班延誤)：同問題一中情況有：由于取消航班后不需再付出那一部 分運營成本，故而其顯性成本為：33P2 =、NiT2Pi -% TiViP2i =4i =4(飛機飛過各航線的時間分別為 Ti、T2、T3,三個航線的人數依次為Ni、N2、N3,每個旅客延誤1分鐘的成本為 R ,且T2取8X 6 0 = 4 8 0分鐘，B 7 3 8機型每分鐘耗油體積Vi ,油價為P2)隱性成本(旅客失望溢出成本)為： 3P3 c vi wi ui i工(其中Vi為該機該次的乘客數量，w該機該次票價，Ui為失望率且5取i

22、, i = 1 ,2 , 3)總成本為P=i7204元(b)飛機置換：由于該航線上的飛機B738發生故障當天i4:35分以后就不能在進 入飛行系統。簡單的考慮的tS,我們只能選擇能夠在i4:35分以后能經過機場ZSPD的飛機且航班較少的飛機進行置換，經過數據整理，符合條件的只有兩架，分別為航線5i40 上的B738和航線上2500上的B767,由于5i40航線的終點為VDPP,考慮到盡量不影 響第二天的航線運營系統，我們予以大膽舍棄。現在考慮2500航線飛機B767:由于該機在i4:35分后第一次到達機場ZSPD的時間為i9:i0分，此時它已經完成了自己所在 航線的任務。那么它可以至少執行兩個

23、航班(ZSPD-VMMC -ZSPD)那么此期間飛機 延誤損失和置換飛機所用的費用為P4,由問題一中飛機延誤成本的計算方法可得P4=i08992元由于時間充足，B767飛機可以有兩種選擇：(i)就此等待第二天原來航線的任務;(2)繼續執行 2153航線的任務。那么總損失在兩種情況下分別為(p4 + 小)、(P4 + 印1 ),R為取消航班ZSPD-VVNB的損失，3 為執行此任務然后返回的損失，其中即1=54675元p2 =44567 元經比較第二種情況下的損失較少，因此排除第一種情況。(c)調飛機：在第(b)種情況中，B767飛機已經完成了原來的計劃，而其他機 種如果調過來使用的話，那么顯然

24、它所需費用至少大于等于( b)種情況，因此我們可 以不予考慮。我們在考慮航線5145,在機場ZGHA于下午14:00-16:00發生機務故障不可使用， 考慮以下幾種情況：(1)航班延誤(航班取消)：計算方法與問題一中相同，可得航空公司的成本損失為： P5=104526元P6=96570元(2)航班置換、航班合并：由于只有知一架飛機到達此機場，因此考慮此種情況是沒 有意義的。由本問題航線2153中調飛機的分析可得，在延誤時間比較少的情況下調飛機是完 全沒有意義的。本文對第二題的求解是基于分析分情況解得的，如果綜合上述各種情況的話，問題 將變得十分的復雜，更加精確的解題方法將在第三題當中予以給出。

25、經過比較上述結果易知，在假設情況下的問題二的分析中航班取消的方案較為優 良。問題三：此問題比較復雜，因此我們根據Jonathan Bard和Gang Yu等提出的時間段優化模型 思路5,將時間段的思想用時間點代替，能夠得到精確的延誤時間；提出時間對概念， 每個時間對是一個航班在本地機場和目的地機場的兩個時間點，一個時間對代表一個航班的起訖點；模型考慮了機型要求，每個用于替換的機型是原機型的子集，即屬于可替 換機型；目標函數是使延誤成本最小化，最終選擇哪個目標函數生成的方案由運控人員 根據需要決定.其中根據符號假設，以延誤成本最少為目標的函數表示如下：min S Z Pj(1)f FF i 旺，

26、j =TjSubject to：(flight cover)工 xf+yf=1,/fwF(2)i.A Z(aircraft cover) J xif <1,Vi = F(3)f于(aircraft type requirement) Z xfbf =1,Vi e Atm, I = A(4)f三Fyf 0,1, bf 0,1(5)式（1）是目標函數，使總的延誤成本最小；式（2）是保證沒一條航線都有航班覆蓋；式（3）是保證每個航班都有飛機執行，否則就取消航班；式（4）是飛機型號的要求，保證需要替換的飛機滿足型號要求；式（5）是整數約束，保證每條航線上要么有航班（取 1）,要么沒有航班（取0）

27、七、模型求解對模型求解的思路是：把所有處于最早延誤航班之后到達或停駐該樞紐機場的飛 機、及其它可使用飛機都作為調度對象，將這些飛機重新指派給航班，使延誤成本最低。 得出所需要的方案.對模型的求解采用啟發式方法搜索置換矩陣，調用匈牙利算法4解決指派問題，匈牙利算法是由匈牙利科學家柯尼格 （Koning）首先提出的，它是求指派問 題的非常有效和簡便的算法.指派問題的最優解具有這樣的性質，若從系數矩陣（Pj）（R）矩陣，那么以新的的一行（歹|）各元素中分別減去該行（歹I）的最小元素，得到新的（Pj）為系數矩陣求得的最優解和用原系數矩陣求得的最優解相同。首先構造延誤時間置Tijt11t21t12t22

28、tmI 12n,i 1,2, ,n; j 1,2, ,m_tm1tm2t mn其中tij表示i時刻航班的飛機執行第j時刻航班的任務所延誤的時間。根據延誤時問置換矩陣Tj計算延誤成本置換矩陣P ,Pl1 Pl2 PinP21 P22P2 nP =：jPml Pm2Pmn _Pj表示i時刻航班的飛機執行第j時刻航班的任務所產生的延誤成本。航班調整算法具體步驟如下：StePl初始化1）建立延誤航班表YW已延誤和即將延誤的航班，字段包括：航班號、飛機型號、后續旅客人數、平均票價、原計劃進出港時間、延誤結束時間），對YW!中按進港時間升序排列；2）建立可用飛機總表BY（在當天機場關閉之前可以恢復使用的延誤飛機，字段包括：飛 機型號、航班號（初始為空）、停駐機場、到達時間、成本（初始為空）、后續旅客數（為 0）；3）建立置換飛機表ZH（從航班信息表中檢索在延誤航班原計劃到達時間之后的所有航班，字段包括：飛機型號、航班號、進、出港時間、票價及旅客數），將ZH8追加到YW表.4）建立機型表AS,表中內容是機型A& （是i時間點出發航班的飛機機型）和它的可置換 機型；SteP2計算調運（ferry）飛機的成本打開YWI,for i =1,打開 BYg,如果 BY-,for j =l ,計算BYft中的調運成本Cf , C