基于改進人工蜂群算法的航班延誤調度研究

許環球

摘 要：航班延誤是航空公司經濟損失的重要組成部分，分析航空公司經濟損失的主要構成，構建出以航班延誤的經濟損失為基礎的航班延誤恢復調度模型，是降低經濟損失的重要方法。針對調度方案的離散性，采用改進的人工蜂群算法，得出最優調度方案。通過實例分析，改進的人工蜂群算法可以有效、準確地選擇調度方案，且此算法的收斂速度優于傳統的人工蜂群算法。

關鍵詞：航班延誤；經濟損失；改進人工蜂群算法；調度方案

中圖分類號：V355 文獻標志碼：A 文章編號：2095-2945（2018）33-0015-03

Abstract： Flight delay is an important part of airline economic loss. This paper analyzes the main components of airline economic loss and constructs a flight delay recovery scheduling model based on the economic loss of flight delay， and it is an important way to reduce economic losses. According to the discreteness of the scheduling scheme， the improved artificial bee colony algorithm is used to obtain the optimal scheduling scheme. Through the example analysis， the improved artificial bee colony algorithm can effectively and accurately select the scheduling scheme， and the convergence speed of this algorithm is better than the traditional artificial bee colony algorithm.

Keywords： flight delay； economic loss； improved artificial bee colony algorithm； scheduling scheme

引言

人工蜂群算法是由土耳其學者Karaboga于2005年提出，其思想是啟發于蜂群通過個體分工和信息交流，相互協作完成采蜜任務[1]。與經典的優化方法如遺傳算法、差分進化算法和粒子群優化算法相比較，人工蜂群算法的求解質量相對較好。針對延誤航班的重新調度恢復這一情況的離散特點，利用改進的人工蜂群算法，能夠避免傳統人工算法求解離散問題時的冗余[2]。

馬正平崔德光針對空中交通日益嚴重的航班延誤，給出了一種機場航班延誤優化模型。模型將機場的到達和出發視為密切相關的兩個過程，考慮了具有連續航程的航班；趙秀麗，朱金福，郭梅構建了以延誤成本最小或延誤時間最短為目標函數的航班恢復模型，航空公司可以根據需要選擇不同的目標函數；李雄，劉光才，顏明池提出了適用于我國的航班延誤經濟損失計算方法，考慮了延誤航班的正常盈利損失，并對我國民航旅客的時聞價值進行了研究； 賀國光針對空運系統日益嚴重的航班延誤，嘗試將貝葉斯方法應用于航班數據分析，重點考慮同一飛機飛行連續航班的情況，借助Netica軟件包，建立貝葉斯網絡模型。

航班延誤造成的損失主要包括：直接損失和間接損失。直接損失是指航班延誤造成的經濟損失，包括航空公司和旅客兩部分。間接損失是指延誤航班延誤造成的航空公司形象信譽方面的損失[3]。本文不考慮這類具有不確定性的間接損失。

1 直接損失

1.1 航空公司經濟損失的構成

1.1.1 延誤航班的運營成本

航班的運營成本包括停場費、起降費、旅客服務費及相應的地面等待成本，它隨著飛機起飛質量增大而增高。根據國際民航組織的標準，可將飛機運營成本按照尾流強弱分為3類。以波音737為例，其每年的固定費用為2500萬元，平均到每天約為7萬元[3][4]。因此，各機型每小時延誤運營成本，如表1。

則飛機航班延誤運營成本為：Cfd=at，a為飛機每小時延誤的運營成本。

1.1.2 取消航班的損失

取消延誤航班會造成航空公司的直接經濟損失。取消航班的損失與最大載客數、客座率和平均票價正相關，其關系如下：

Cf=最大載客數×客座率×平均票價

1.1.3 調機成本

調機是指飛機由一個機場調往另一機場，因此其成本由兩機場間的距離決定。

1.2 旅客經濟損失

針對旅客乘坐的航班類型分類，可以分為國內航班旅客和國際航班旅客，其中每名國內航班旅客平均的延誤經濟損失約為50元/小時，而每名國際航班旅客平均的經濟損失約為100元/小時[5]，可表達為：

Cm=50t，t為航班延誤的總時間。

2 航班調度模型

調度恢復是當機場發生較大規模延誤后，對已停駐在該機場的飛機和已延誤但后期可到達該機場的飛機重新調度，從而使得延誤的經濟損失最低[6]。調度問題是指派問題的一種，其標準形式如下：設有n個航班和n架飛機，已知第i個單位完成第j項任務的成本為Cij，要求一架飛機和航班之間一一對應的調度方案，使完成這些任務的總成本最小[6][7]。

的成本矩陣，第i行各元素表示第j個單位完成各任務所需成本，第j列各元素表示第J項任務由各單位完成所需成本[8]。這樣，問題的數學模型是：

3 改進的人工蜂群算法

改進人工蜂群算法是在人工蜂群算法基本原理的基礎上，在食物源編碼時采用的離散型編碼，同時在工作蜂和跟隨蜂生成候選食物源時，為了保持食物源對應的解的可行性提出了一種鄰域移動方法。

3.1 蜜源位置編碼

根據問題離散型進行編碼，設一個n維問題，任一食物源的位置xi，是一個n維向量，向量的維數對應任務數。食物源的位置編碼為xi=（xi1，xi2，...，xij，...，xin），它代表一種任務指派的方案，每一個xi是1～n自然數的一個排列。其中，xij表示第i個解的第j項任務由xij去完成。

3.2 候選蜜源的生成

本文蜜源的位置xi是離散的表達形式，采用鄰域移動方法來生成候選蜜源。如圖1所示，蜜源i是當前食物源，蜜源k是隨機選取的相鄰蜜源，它們移動前編碼如圖1（a）。隨機選擇的位置d，這里是第二位，箭頭①指向食物源k的第二位“1”箭頭②指向蜜源：的第二位“5”，鄰域移動的過程為：食物源的第二位“5”被蜜源k的第二位，“1”替換，然后再尋找原蜜源中“1”的位置，這里是第五位，箭頭③表示蜜源第五位的“1”為“5”所替換，流程如箭頭①②③的流向所示。

4 算例分析

根據表2航班數據，確定延誤損失矩陣：

分別采用傳統人工蜂群算法和改進人工蜂群算法進行20次仿真，其最優解為5-4、4-7、7-11、9-9，造成的經濟損失是29070元，全局最優解的收斂過程如圖2、圖3所示。

5 結束語

本文針對機場出現較大規模延誤后，為使得經濟損失最低進行調度恢復，并建立航班調度數學模型。在充分考慮到調度問題離散性特點，給出了適當的蜜源編碼方法，利用鄰域移動法生成候選蜜源。通過算例分析，改進的人工蜂群算法具有更好的收斂性，在解決航班調度等離散指派問題時具有很強的使用價值。

參考文獻：

[1]秦全德，程適，李麗，等.人工蜂群算法研究綜述[J].智能系統學報，2014，9（2）：127-135.

[2]孫曉雅，林焰.改進的人工蜂群算法求解任務指派問題[J].微電子學與計算機，2012，29（1）：23-26.

[3]中國民用航空局.2015年民航行業發展統計公報[M].北京：中國民航出版社，2015.

[4]朱志禹.論航空公司運營中的服務接觸及關鍵事件管理[J].西南交通大學學報（社會科學版），2008，10：17-21.

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

[6]馬正平，崔德光.機場航班延誤優化模型[J].清華大學學報（自然科學版），2004，44（4）：474-477.

[7]趙秀麗，朱金福，郭梅.不正常航班延誤調度模型及算法[J].系統工程理論與實踐，2008，4：129-134.

[8]董鈺.大規模航班延誤恢復調度模型及管理研究[D].大連海事大學，2009.