基于改進(jìn)匈牙利算法的航班延誤調(diào)度模型

林楠通 王泳欣 吳國(guó)濤 賴(lài)建蓉 葉雪琪

摘 要：文章構(gòu)建了以延誤成本最小或延誤時(shí)間最短為目標(biāo)函數(shù)的航班恢復(fù)模型，航空公司可以根據(jù)需要選擇不同的目標(biāo)函數(shù)；細(xì)分了延誤成本，并且對(duì)匈牙利算法進(jìn)行改進(jìn)，加入了遺傳算法對(duì)模型進(jìn)行求解，給出了算法的運(yùn)行步驟，并以實(shí)例說(shuō)明了模型和算法的可行性。

關(guān)鍵詞：匈牙利算法；延誤成本；延誤時(shí)間

中圖分類(lèi)號(hào)：F562

文獻(xiàn)標(biāo)識(shí)碼：A

在對(duì)航班延誤進(jìn)行調(diào)度時(shí)，航空公司總是把所有處于延誤之后的備用飛機(jī)或者是已經(jīng)完成飛行任務(wù)的飛機(jī)都作為調(diào)度對(duì)象，將這些飛機(jī)重新指派給航班。在本文中，我們以航班延誤時(shí)間最短或延誤成本最低作為主要目標(biāo)，得出的兩種最優(yōu)解是相對(duì)的，其中以延誤成本最低為目標(biāo)得出的方案延誤時(shí)間不是最短，因此得出來(lái)的方案需要由運(yùn)控人員根據(jù)現(xiàn)實(shí)情況選擇。

在本文中，我們針對(duì)航空公司的需要，按原計(jì)劃出發(fā)時(shí)間對(duì)延誤的航班進(jìn)行排序，改進(jìn)匈牙利算法，求出飛機(jī)調(diào)整的最優(yōu)解。

一、延誤成本的定義

在航班延誤發(fā)生之時(shí)，旅客和航空公司無(wú)疑是航班延誤的受害者，因此延誤成本在定義時(shí)需要分開(kāi)計(jì)算。

1.航空公司的經(jīng)濟(jì)損失

經(jīng)過(guò)查詢(xún)文獻(xiàn)，我們可以發(fā)現(xiàn)航空公司的經(jīng)濟(jì)損失分為延誤航班的運(yùn)營(yíng)成本、取消航班的盈利損失和調(diào)運(yùn)飛機(jī)成本。

其中延誤航班的運(yùn)營(yíng)成本和航班機(jī)型以及質(zhì)量有關(guān)系，對(duì)于不同的機(jī)型，其延誤成本為：C_fd=at，其中，a為飛機(jī)每小時(shí)延誤的運(yùn)營(yíng)成本。延誤航班的盈利損失與航班航班客座率s、航空公司的平均票價(jià)a和最大載客人數(shù)m密切相關(guān)。則延誤航班的經(jīng)濟(jì)損失：C_f=msa。而調(diào)運(yùn)飛機(jī)成本由航油價(jià)格和兩機(jī)場(chǎng)之間的距離決定。

2.乘客的經(jīng)濟(jì)損失

查詢(xún)文獻(xiàn)可得航班延誤造成的乘客損失為：C_m=α_psmt。其中α_p為航班單位時(shí)間每名旅客的平均延誤經(jīng)濟(jì)損失，t由航班計(jì)劃起飛時(shí)刻T和航班恢復(fù)時(shí)間R決定。

二、延誤航班調(diào)度問(wèn)題的數(shù)學(xué)模型建立

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

根據(jù)上述對(duì)航班延誤經(jīng)濟(jì)損失的理解，查詢(xún)文獻(xiàn)可得針對(duì)航班延誤經(jīng)濟(jì)損失降到最低的目標(biāo)函數(shù)為：

三、模型的求解

我們根據(jù)上述模型，采用某航空公司航班的基本數(shù)據(jù)，利用經(jīng)典的匈牙利指派步驟，對(duì)航班延誤恢復(fù)調(diào)度模型進(jìn)行了擬合，用MATLAB分別得出兩個(gè)目標(biāo)函數(shù)下的求解結(jié)果，其中以延誤時(shí)間最小化為目標(biāo)函數(shù)的延誤成本為86710元，以延誤成本最小化為目標(biāo)函數(shù)的延誤成本為69171元。

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

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

步驟2：處理約束條件；

步驟3：判斷飛機(jī)數(shù)和航班數(shù)是否平衡，并進(jìn)行匈牙利指派，平衡輸出最優(yōu)指派序列；非平衡輸出最優(yōu)指派序列和取消航班序列；

步驟4：設(shè)置W=x₁，x₂，...，x_n對(duì)最優(yōu)指派序列進(jìn)行編碼；

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

步驟6：首先輪盤(pán)賭方法進(jìn)行選擇操作，接著使用均勻交叉方法進(jìn)行交叉操作，最后使用隨機(jī)擾動(dòng)法進(jìn)行變異操作；

步驟7：復(fù)雜性分析，檢驗(yàn)分析混合優(yōu)化算法的復(fù)雜度不超過(guò)經(jīng)典匈牙利算法的時(shí)間復(fù)雜度。

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

四、結(jié)語(yǔ)

在本文中，我們對(duì)經(jīng)典的匈牙利算法進(jìn)行了改進(jìn)，由于篇幅受限，經(jīng)典的匈牙利算法的步驟并未給出，但數(shù)據(jù)真實(shí)可靠；但在調(diào)度的過(guò)程中當(dāng)我們隨機(jī)交換初始飛機(jī)編號(hào)次序時(shí)仍然能夠輸出指派結(jié)果。因此，我們采取了遺傳算法和匈牙利算法進(jìn)行混合優(yōu)化，得出的調(diào)度模型會(huì)更加高效。

參考文獻(xiàn)：

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

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

[3]楊秀云，王全良，何建寶.航班延誤問(wèn)題的研究動(dòng)態(tài)、演化趨勢(shì)及啟示[J].經(jīng)濟(jì)經(jīng)緯，2013（4）.

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

[5]呂宗平，胡 欣，丁建立.航班延誤預(yù)警指標(biāo)體系與預(yù)警量級(jí)構(gòu)建[J].航空計(jì)算技術(shù)，2010（1）.

[6]榮 耀，王建東.基于關(guān)鍵飛行資源的航班延誤波及DAG模型的研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2009（11）.

[7]呂曉杰，王 紅.大型樞紐機(jī)場(chǎng)大面積航班延誤預(yù)警方法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009（19）.

[8]劉艷紅，高 林，李耀華.基于經(jīng)濟(jì)損失的航班延誤恢復(fù)模型研究[J].中國(guó)民航大學(xué)學(xué)報(bào)，2011（1）.