蟻群算法在機隊指派問題中的應用

［摘要］ 隨著近10年來我國航空運輸業的壯大和市場需求的持續增長，借助于計算機輔助完成機隊指派任務已經成為一種必然的趨勢。然而由于國外航空公司的運營模式與我國的不同，因此設計一個適合國內航空運輸特點的排程算法，以協助管理者解決日益復雜的機隊指派問題，兼具實際意義與理論價值。

本文將蟻群算法應用到我國航空公司的機隊指派問題中，提出了單一機種前提下的求解模型，并以提高營運績效為目的，求出最小的機隊數目和各單機的巡航路線，最后通過一個實際算例驗證了該模型對于我國航空公司現行的機隊指派問題具有良好的適用性。

［關鍵詞］ 機隊指派； 蟻群算法； 機隊數目最小化

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2011 . 13. 048

［中圖分類號］F224.3；TP18 ［文獻標識碼］A ［文章編號］1673 - 0194（2011）13- 0079- 02

１引言

隨著經濟全球化發展，面對我國航空運輸業的壯大和市場需求的持續增長，如何提高營運績效，從而提升市場競爭力，獲得更高的市場占有率，已成為航空公司規劃發展的重要課題。現實中的機隊指派問題往往涉及大量的需求點（航班）和候選點（飛機），很難得到最優解，而現代啟發式算法（Ｍｅｔａ Ｈｅｕｒｉｓｔｉｃ Ａｌｇｏｒｉｔｈｍ）能夠在多項式時間內找到滿足實際要求的解。

本文將經典的蟻群算法（Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ， ＡＣＡ）模型應用于我國航空公司的機隊指派問題中，在單一機種的前提下，求出最小的機隊數目，并求得各單機的巡航路線。本文研究的目的是使今后航空公司在處理機隊指派問題時，避免依賴相關作業人員的主觀判斷，設計一個能夠協調上述作業流程并適合國內航空運輸特點的排程算法，以協助管理者解決日漸復雜的機隊指派問題，兼具實際意義與理論價值。

２基本理論

意大利學者Ｍ． Ｄｏｒｉｇｏ于１９９１年首次提出了蟻群算法，并成功地用于求解旅行商問題（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ， ＴＳＰ）。ＴＳＰ 問題描述為：假設有ｎ個城市，要求找到一條遍歷所有城市且每個城市只訪問一次的路線，使得總的路線距離最短。

第一步：參數初始化。令循環次數Ｎｃ ＝ ０，設置最大循環次數Ｎｃmａｘ，將ｍ只螞蟻置于ｎ個城市上，使得每只螞蟻都能從任意一個城市出發。令有向圖上每條邊（ｉ，ｊ）的初始化信息量τｉｊ（ｔ） ＝ ｃｏｎｓｔ，其中ｃｏｎｓｔ表示常數，并且初始時刻Δτｉｊ（０）＝０。

第二步：循環次數Ｎｃ ＝ Ｎｃ ＋ １。

第三步：城市的初始禁忌表ｔａｂｕｋ ＝ １。

第四步：螞蟻數目ｋ ＝ ｋ ＋ １。

第六步：修改禁忌表指針，對于螞蟻己經訪問過的城市就被記錄在禁忌表里，并且不允許螞蟻訪問禁忌表里的城市，直到所有的城市都被訪問完。

第七步：若集合Ｃ中城市未遍歷完，即ｋ≤ｍ，則跳轉到第四步； 否則執行第八步。

第八步：當螞蟻遍歷完所有的城市，它將在其經過的每條路徑上留下信息素。公式（３）表示第ｋ個螞蟻訪問過路段（ｉ，ｊ）后釋放的信息素，其中Ｑ為一個常數，表示螞蟻釋放的信息素總量，它在一定程度上影響著算法的收斂速度；Ｌｋ表示搜索到本輪最短路徑的螞蟻ｋ所走的路徑總長度。根據公式（４）和公式（５）更新每條路徑上的信息素，其中（１ － ρ）表示信息素揮發后的殘留系數。

３模型設計

３．１概念定義

在運力嚴重緊張時，機隊指派工作的基本目標就是用最少的飛機承擔起盡可能多的航班任務。本著這個目標，本文采用一些更加合理的方法，設計出能夠求解機隊指派任務的蟻群算法（Ｆｌｅｅｔ Ａｓｓｉｇｎｍｅｎｔ Ｔａｓｋ ｓｏｌｖｅｄ ｂｙ Ａｎｔ Ａｌｇｏｒｉｔｈｍ， ＦＡＴ＿ＡＡ）。具體創新如下：

（１） 重新定義了城市的概念，把待排航班時刻表中的每一個航班抽象成一個城市。

（２） 改造了螞蟻的初始狀態，它們不是放置在隨機任選的城市。

（３） 重點對城市之間的距離進行了改造，用ｄｉｊ表示第ｉ個航班到第ｊ個航班的距離，并定義該距離是一個向量，一般情況下ｄｉｊ≠ｄｊｉ。為了滿足航班站銜接要求，并且要保證同一架飛機所執行的下一航班的起飛時間晚于前一航班的到港時間，設定公式（６）：

ｄｉｊ ＝ １００，第ｉ個航班和第ｊ個航班是同一個航班；１０，第ｉ個航班的降落機場和第ｊ個航班的起飛機場不相同， 或第ｉ個航班的降落時間晚于第ｊ個航班的起飛時間；１，第ｉ個航班的降落機場和第ｊ個航班的起飛機場相同， 并且第ｉ個航班的降落時間早于第ｊ個航班的起飛時間。 （６）

３．２算法流程

以集合Ｃ表示未被訪問的城市集合，ｃｉ表示城市ｉ，ｃｊ表示城市ｊ，因此在ｔ時刻連接城市ｉ，ｊ，殘留信息素的集合可表示為Γ ＝ ｛τｉｊ（ｔ） ｜ ｃｉ，ｃｊ∈Ｃ｝。在初始時刻，各條路徑上的信息素相等，并表示為τｉｊ（０） ＝ ｃｏｎｓｔ。用禁忌表ｔａｂｕｋ（ｋ ＝ １，２，…，ｍ）來記錄螞蟻ｋ當前所走過的城市，剩余的能夠被訪問的城市集合ａｌｌｏｗｅｄｋ將隨ｔａｂｕｋ的改變作動態調整。

第一步：參數初始化。令循環次數Ｎｃ ＝ ０，設置最大循環次數Ｎｃｍａｘ，將ｍ只螞蟻置在需要被最早執行的ｍ個航班（城市）上，使得每只螞蟻必須從這ｍ個城市出發。令有向圖上每條邊（ｉ，ｊ）的初始化信息量τｉｊ（ｔ） ＝ ｃｏｎｓｔ，其中ｃｏｎｓｔ表示常數，并且初始時刻Δτｉｊ（０） ＝ ０。

第二步：循環次數Ｎｃ ＝ Ｎｃ ＋ １。

第三步：城市的初始禁忌表ｔａｂｕｋ ＝ １。

第四步：螞蟻數目ｋ ＝ ｋ ＋ １。

第五步：螞蟻個體根據狀態轉移概率公式（１）計算的概率選擇城市ｊ并前進，ｊ∈｛Ｃ － ｔａｂｕｋ｝。

第六步：修改禁忌表指針，將螞蟻移動到新的城市，并把該城市放入禁忌表中。這樣螞蟻就找到了一條遍歷所有城市且每個城市只訪問一次的路線。

第七步：若集合Ｃ中城市未遍歷完，即ｋ≤ｍ，則跳轉到第四步，否則執行第八步。

第八步：當螞蟻遍歷完所有的城市，將會在其經過的每條路徑上留下信息素。用公式（２）表示啟發函數，它是由創新公式（６）決定的；公式（３）表示第ｋ個螞蟻訪問過路段（ｉ，ｊ）后釋放的信息素；公式（４）和公式（５）表示更新每條路徑上的信息素，其中（1 - ρ）表示信息素揮發后的殘留系數。

第九步：若滿足循環次數Ｎｃ≥Ｎｃｍａｘ，則循環結束并輸出程序計算結果；否則清空禁忌表并跳轉到第二步。

４實際算例及結論

本文選取的樣本來自中國國際航空股份有限公司（Ａｉｒ Ｃｈｉｎａ Ｌｉｍｉｔｅｄ）于２０１０年４月份的航班時刻表，并從中選取了屬于６個不同機場的４０個航班來進行機隊指派任務。選取４０個航班的原因是，完成這４０個航班的飛行任務，可以有４０！種排程方法，共８．１５９ × １０４７種，如果只由人工而不用計算機輔助，勢必將依賴相關作業人員的主觀判斷，并且工作質量無法保證。因此，如果ＦＡＴ＿ＡＡ算法能在可以接受的時間范圍內，以盡可能少的飛機數目完成這４０個航班的排程任務，則足以證明算法的適用性和有效性。

將１ ０００次實驗的明細結果記錄于表１中，螞蟻遍歷完４０個城市（航班）的路徑平均值的最好解為１２５．３，發生在α ＝ ２， β ＝ ９中；最小使用飛機數的平均值ＭｉｎＡＮ的最好解為９．６，分別發生在α ＝ ３，β ＝ ８中。對比１０組路徑平均值的最小值和最大值曲線，可以確定α∈［４，５］且β∈［７，１０］時，路徑平均值最短，平均飛機使用數最少，ＦＡＴ＿ＡＡ算法的綜合求解性能很好。

因此我們選取參數α ＝ ５，β ＝ １０，ρ ＝ ０．9５，Ｑ ＝ １００， Ｎｃｍａｘ ＝ ５０，在可接受的計算時間內，將４０個航班分配給９架飛機執行，并能求得各單機的巡航路線，這個實驗結果是令人滿意的，證明了ＦＡＴ＿ＡＡ算法對于求解機隊指派任務確實高效可行。

采用計算機輔助機隊指派已成為我國民航運輸業發展的必然趨勢，因此研究求解機隊指派問題的算法有著非常現實的應用背景。將ＦＡＴ＿ＡＡ算法用于機隊指派問題，不但可以給出合理的單機巡航路線，而且盡可能地減少了飛機使用架數，在較短的時間內求出了滿意解。實驗表明，產生的指派方案確實符合實際管理的需要，對于降低管理人員的勞動強度，節省作業時間具有較高的實用價值，為航空公司進行機隊指派作業提供了一個良好的理論依據。

主要參考文獻

［１］ 于海波．飛機排班算法的研究與實現［Ｄ］． 南京：南京航空航天大學，２００７．

［２］ 孫宏，杜文． 航空公司飛機排班問題的排序模型及算法［Ｊ］． 系統工程理論方法應用，２００２，１１（３）：２４４－２４７．

［３］ 田文馨． 基于剩余裝載能力的蟻群算法在逆向物流ＶＲＰＳＤＰ問題中的應用研究［Ｄ］． 上海：上海財經大學，２００６．

［４］ 段海濱． 蟻群算法原理及其應用［Ｍ］． 北京：科學出版社，２００５．

［５］ 孫宏，杜文． 飛機排班數學規劃模型［Ｊ］． 交通運輸工程學報，２００４，４（３）：１１７－１２０．

［６］ 鄭蕓，王錦彪，王元崑． 螞蟻算法在民航飛機排班問題中的應用［Ｊ］． 計算機工程，２００５，３１（ｚ１）：７－９．

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文