基于改進匈牙利算法的航班延誤調度模型

林楠通 王泳欣 吳國濤 賴建蓉 葉雪琪

摘 要：文章構建了以延誤成本最小或延誤時間最短為目標函數的航班恢復模型，航空公司可以根據需要選擇不同的目標函數；細分了延誤成本，并且對匈牙利算法進行改進，加入了遺傳算法對模型進行求解，給出了算法的運行步驟，并以實例說明了模型和算法的可行性。

關鍵詞：匈牙利算法；延誤成本；延誤時間

中圖分類號：F562

文獻標識碼：A

在對航班延誤進行調度時，航空公司總是把所有處于延誤之后的備用飛機或者是已經完成飛行任務的飛機都作為調度對象，將這些飛機重新指派給航班。在本文中，我們以航班延誤時間最短或延誤成本最低作為主要目標，得出的兩種最優解是相對的，其中以延誤成本最低為目標得出的方案延誤時間不是最短，因此得出來的方案需要由運控人員根據現實情況選擇。

在本文中，我們針對航空公司的需要，按原計劃出發時間對延誤的航班進行排序，改進匈牙利算法，求出飛機調整的最優解。

一、延誤成本的定義

在航班延誤發生之時，旅客和航空公司無疑是航班延誤的受害者，因此延誤成本在定義時需要分開計算。

1.航空公司的經濟損失

經過查詢文獻，我們可以發現航空公司的經濟損失分為延誤航班的運營成本、取消航班的盈利損失和調運飛機成本。

其中延誤航班的運營成本和航班機型以及質量有關系，對于不同的機型，其延誤成本為：C_fd=at，其中，a為飛機每小時延誤的運營成本。延誤航班的盈利損失與航班航班客座率s、航空公司的平均票價a和最大載客人數m密切相關。則延誤航班的經濟損失：C_f=msa。而調運飛機成本由航油價格和兩機場之間的距離決定。

2.乘客的經濟損失

查詢文獻可得航班延誤造成的乘客損失為：C_m=α_psmt。其中α_p為航班單位時間每名旅客的平均延誤經濟損失，t由航班計劃起飛時刻T和航班恢復時間R決定。

二、延誤航班調度問題的數學模型建立

由于飛機指派問題的約束條件很多，還有一部分是柔性約束，決策人員不希望算法僅能給出一個解，而是希望得到多個備選方案，由簽派人員決定最終執行方案。

根據上述對航班延誤經濟損失的理解，查詢文獻可得針對航班延誤經濟損失降到最低的目標函數為：

三、模型的求解

我們根據上述模型，采用某航空公司航班的基本數據，利用經典的匈牙利指派步驟，對航班延誤恢復調度模型進行了擬合，用MATLAB分別得出兩個目標函數下的求解結果，其中以延誤時間最小化為目標函數的延誤成本為86710元，以延誤成本最小化為目標函數的延誤成本為69171元。

以上兩種方案的成本差是17539元，這里也證明了匈牙利算法在不同目標情況下得到的解并非最優，航空公司可以根據自身的需要選擇相應的目標函數，在實際發生的航班延誤基礎上，得出相應的優化解決方案。

由于遺傳算法能尋找到一種合適的解，因此在求解上述模型時，為了提高求解的效率和直觀地得出解決方案，本文在經典的匈牙利算法上加入了遺傳算法，得到以下的算法步驟：

步驟2：處理約束條件；

步驟3：判斷飛機數和航班數是否平衡，并進行匈牙利指派，平衡輸出最優指派序列；非平衡輸出最優指派序列和取消航班序列；

步驟4：設置W=x₁，x₂，...，x_n對最優指派序列進行編碼；

步驟5：遺傳算法的初始輸入為隨機交換某鄰域編碼的次序；

步驟6：首先輪盤賭方法進行選擇操作，接著使用均勻交叉方法進行交叉操作，最后使用隨機擾動法進行變異操作；

步驟7：復雜性分析，檢驗分析混合優化算法的復雜度不超過經典匈牙利算法的時間復雜度。

構建以上遺傳算法與匈牙利算法的混合優化算法后，我們需通過實例進行驗證。本文我們選取了某航空公司在某一天的航班延誤調度，初始飛機編號為1～10號，進行匈牙利指派后，飛機的編碼順序為2，3，1，5，7，9，10，4，8，6；接著我們按照上述的算法步驟，隨機交換初始飛機編號鄰域編碼的次序，即以2，1，3，5，7，9，10，4，8，6作為遺傳算法的初始輸入，最終得到的染色體編碼依舊為2，3，1，5，7，9，10，4，8，6。我們可以得出該算法收斂于匈牙利算法的指派。

四、結語

在本文中，我們對經典的匈牙利算法進行了改進，由于篇幅受限，經典的匈牙利算法的步驟并未給出，但數據真實可靠；但在調度的過程中當我們隨機交換初始飛機編號次序時仍然能夠輸出指派結果。因此，我們采取了遺傳算法和匈牙利算法進行混合優化，得出的調度模型會更加高效。

參考文獻：

[1]李 雄，劉光才，顏明池，等.航班延誤引發的航空公司及旅客經濟損失[J].系統工程，2007（12）.

[2]趙秀麗.航空公司不正常航班恢復模型及算法研究[D].南京：南京航空航天大學，2010.

[3]楊秀云，王全良，何建寶.航班延誤問題的研究動態、演化趨勢及啟示[J].經濟經緯，2013（4）.

[4]邢有洪，李曉津.航空公司航班延誤損失分析[J].會計之友（中旬刊），2010（2）.

[5]呂宗平，胡 欣，丁建立.航班延誤預警指標體系與預警量級構建[J].航空計算技術，2010（1）.

[6]榮 耀，王建東.基于關鍵飛行資源的航班延誤波及DAG模型的研究[J].小型微型計算機系統，2009（11）.

[7]呂曉杰，王 紅.大型樞紐機場大面積航班延誤預警方法研究[J].計算機工程與設計，2009（19）.

[8]劉艷紅，高 林，李耀華.基于經濟損失的航班延誤恢復模型研究[J].中國民航大學學報，2011（1）.