基于改進(jìn)人工蜂群算法的航班延誤調(diào)度研究

許環(huán)球

摘 要：航班延誤是航空公司經(jīng)濟(jì)損失的重要組成部分，分析航空公司經(jīng)濟(jì)損失的主要構(gòu)成，構(gòu)建出以航班延誤的經(jīng)濟(jì)損失為基礎(chǔ)的航班延誤恢復(fù)調(diào)度模型，是降低經(jīng)濟(jì)損失的重要方法。針對(duì)調(diào)度方案的離散性，采用改進(jìn)的人工蜂群算法，得出最優(yōu)調(diào)度方案。通過(guò)實(shí)例分析，改進(jìn)的人工蜂群算法可以有效、準(zhǔn)確地選擇調(diào)度方案，且此算法的收斂速度優(yōu)于傳統(tǒng)的人工蜂群算法。

關(guān)鍵詞：航班延誤；經(jīng)濟(jì)損失；改進(jìn)人工蜂群算法；調(diào)度方案

中圖分類(lèi)號(hào)：V355 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

引言

人工蜂群算法是由土耳其學(xué)者Karaboga于2005年提出，其思想是啟發(fā)于蜂群通過(guò)個(gè)體分工和信息交流，相互協(xié)作完成采蜜任務(wù)[1]。與經(jīng)典的優(yōu)化方法如遺傳算法、差分進(jìn)化算法和粒子群優(yōu)化算法相比較，人工蜂群算法的求解質(zhì)量相對(duì)較好。針對(duì)延誤航班的重新調(diào)度恢復(fù)這一情況的離散特點(diǎn)，利用改進(jìn)的人工蜂群算法，能夠避免傳統(tǒng)人工算法求解離散問(wèn)題時(shí)的冗余[2]。

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

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

1 直接損失

1.1 航空公司經(jīng)濟(jì)損失的構(gòu)成

1.1.1 延誤航班的運(yùn)營(yíng)成本

航班的運(yùn)營(yíng)成本包括停場(chǎng)費(fèi)、起降費(fèi)、旅客服務(wù)費(fèi)及相應(yīng)的地面等待成本，它隨著飛機(jī)起飛質(zhì)量增大而增高。根據(jù)國(guó)際民航組織的標(biāo)準(zhǔn)，可將飛機(jī)運(yùn)營(yíng)成本按照尾流強(qiáng)弱分為3類(lèi)。以波音737為例，其每年的固定費(fèi)用為2500萬(wàn)元，平均到每天約為7萬(wàn)元[3][4]。因此，各機(jī)型每小時(shí)延誤運(yùn)營(yíng)成本，如表1。

則飛機(jī)航班延誤運(yùn)營(yíng)成本為：Cfd=at，a為飛機(jī)每小時(shí)延誤的運(yùn)營(yíng)成本。

1.1.2 取消航班的損失

取消延誤航班會(huì)造成航空公司的直接經(jīng)濟(jì)損失。取消航班的損失與最大載客數(shù)、客座率和平均票價(jià)正相關(guān)，其關(guān)系如下：

Cf=最大載客數(shù)×客座率×平均票價(jià)

1.1.3 調(diào)機(jī)成本

調(diào)機(jī)是指飛機(jī)由一個(gè)機(jī)場(chǎng)調(diào)往另一機(jī)場(chǎng)，因此其成本由兩機(jī)場(chǎng)間的距離決定。

1.2 旅客經(jīng)濟(jì)損失

針對(duì)旅客乘坐的航班類(lèi)型分類(lèi)，可以分為國(guó)內(nèi)航班旅客和國(guó)際航班旅客，其中每名國(guó)內(nèi)航班旅客平均的延誤經(jīng)濟(jì)損失約為50元/小時(shí)，而每名國(guó)際航班旅客平均的經(jīng)濟(jì)損失約為100元/小時(shí)[5]，可表達(dá)為：

Cm=50t，t為航班延誤的總時(shí)間。

2 航班調(diào)度模型

調(diào)度恢復(fù)是當(dāng)機(jī)場(chǎng)發(fā)生較大規(guī)模延誤后，對(duì)已停駐在該機(jī)場(chǎng)的飛機(jī)和已延誤但后期可到達(dá)該機(jī)場(chǎng)的飛機(jī)重新調(diào)度，從而使得延誤的經(jīng)濟(jì)損失最低[6]。調(diào)度問(wèn)題是指派問(wèn)題的一種，其標(biāo)準(zhǔn)形式如下：設(shè)有n個(gè)航班和n架飛機(jī)，已知第i個(gè)單位完成第j項(xiàng)任務(wù)的成本為Cij，要求一架飛機(jī)和航班之間一一對(duì)應(yīng)的調(diào)度方案，使完成這些任務(wù)的總成本最小[6][7]。

的成本矩陣，第i行各元素表示第j個(gè)單位完成各任務(wù)所需成本，第j列各元素表示第J項(xiàng)任務(wù)由各單位完成所需成本[8]。這樣，問(wèn)題的數(shù)學(xué)模型是：

3 改進(jìn)的人工蜂群算法

改進(jìn)人工蜂群算法是在人工蜂群算法基本原理的基礎(chǔ)上，在食物源編碼時(shí)采用的離散型編碼，同時(shí)在工作蜂和跟隨蜂生成候選食物源時(shí)，為了保持食物源對(duì)應(yīng)的解的可行性提出了一種鄰域移動(dòng)方法。

3.1 蜜源位置編碼

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

3.2 候選蜜源的生成

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

4 算例分析

根據(jù)表2航班數(shù)據(jù)，確定延誤損失矩陣：

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

5 結(jié)束語(yǔ)

本文針對(duì)機(jī)場(chǎng)出現(xiàn)較大規(guī)模延誤后，為使得經(jīng)濟(jì)損失最低進(jìn)行調(diào)度恢復(fù)，并建立航班調(diào)度數(shù)學(xué)模型。在充分考慮到調(diào)度問(wèn)題離散性特點(diǎn)，給出了適當(dāng)?shù)拿墼淳幋a方法，利用鄰域移動(dòng)法生成候選蜜源。通過(guò)算例分析，改進(jìn)的人工蜂群算法具有更好的收斂性，在解決航班調(diào)度等離散指派問(wèn)題時(shí)具有很強(qiáng)的使用價(jià)值。

參考文獻(xiàn)：

[1]秦全德，程適，李麗，等.人工蜂群算法研究綜述[J].智能系統(tǒng)學(xué)報(bào)，2014，9（2）：127-135.

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

[3]中國(guó)民用航空局.2015年民航行業(yè)發(fā)展統(tǒng)計(jì)公報(bào)[M].北京：中國(guó)民航出版社，2015.

[4]朱志禹.論航空公司運(yùn)營(yíng)中的服務(wù)接觸及關(guān)鍵事件管理[J].西南交通大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），2008，10：17-21.

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

[6]馬正平，崔德光.機(jī)場(chǎng)航班延誤優(yōu)化模型[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2004，44（4）：474-477.

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

[8]董鈺.大規(guī)模航班延誤恢復(fù)調(diào)度模型及管理研究[D].大連海事大學(xué)，2009.