基于均衡更新蟻群算法的飛機(jī)排序調(diào)度

李媛禎，楊 群，段 汐

(南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

0 引言

隨著航空運輸業(yè)的飛速發(fā)展，空中交通日趨繁忙，空中交通管制(Air Traffic Control，ATC)的重要性愈加突出。飛機(jī)排序調(diào)度問題(Aircraft Arrival Sequencing and Scheduling，ASS)研究在空中交通繁忙的機(jī)場終端區(qū)，如何在保證飛機(jī)安全飛行間隔的前提下，有效地優(yōu)化到港飛機(jī)著陸序和著陸時間，達(dá)到使飛機(jī)總延誤最小、提高系統(tǒng)容量、增加飛行安全性等目標(biāo)［1-2］。它是空中交通管制的一個關(guān)鍵問題。飛機(jī)排序調(diào)度中，到港飛機(jī)到達(dá)機(jī)場終端區(qū)以后，按照預(yù)定的進(jìn)港路線飛行并著陸，n 架到港飛機(jī)的著陸次序可以有n!種排列，其組合優(yōu)化是NP-難解問題。蟻群算法是一種能行之有效地解決組合優(yōu)化問題的智能進(jìn)化算法，本文擬采用一種基于均衡更新的蟻群算法處理飛機(jī)排序調(diào)度問題。

1 相關(guān)工作

隨著我國經(jīng)濟(jì)迅速發(fā)展，航空運輸量持續(xù)增加，合理有序地調(diào)度到港飛機(jī)的順序是目前空中交通管制急需解決的問題。近年來，國內(nèi)外學(xué)者已有許多相關(guān)研究，提出了許多解決飛機(jī)排序調(diào)度問題的方法［6-9］。傳統(tǒng)飛機(jī)排序調(diào)度采用先到先服務(wù)(First Come First Service，F(xiàn)CFS)的調(diào)度算法［4］，這種方法基于航空管制員人工經(jīng)驗進(jìn)行，在滿足一定約束條件的前提下對飛機(jī)著陸序可以進(jìn)行調(diào)整，保持大部分飛機(jī)之間的相對位置，最終確定著陸時間。雖然算法簡單易行，但造成的飛機(jī)延誤時間較大，不能很好地滿足空中交通流量管制需求［16-17］。Hu 等［2-3，5］使用改進(jìn)的遺傳算法處理飛機(jī)排序調(diào)度問題，取得一定效果，但算法模型中未考慮實際旅客數(shù)量，沒有區(qū)別對待不同載客量的飛機(jī)，忽略了不同載客量的飛機(jī)延誤所帶來的不同影響。Zhao［7］等將貪婪隨機(jī)自適應(yīng)搜索和蟻群算法相結(jié)合，處理非正常航班的再次調(diào)度問題，結(jié)合后算法能較好地發(fā)揮蟻群算法的正反饋特點，且具有較高魯棒性，但該特殊情況并非當(dāng)前空中交通管制的重要方面。Wang［14］采用Pareto 優(yōu)化方法，構(gòu)建一個數(shù)學(xué)模型，實現(xiàn)加權(quán)航班延誤時間與延誤時間數(shù)量之間的平衡，然后靈活地選擇解決方案，從而達(dá)到優(yōu)化飛機(jī)著陸序列的目的，然而未考慮到實際情況中搭載旅客數(shù)因素，這會造成旅客機(jī)場滯留的情況。

針對以上不足，本文提出一種信息素均衡更新的蟻群算法處理飛機(jī)排序調(diào)度問題:在安排飛機(jī)著陸序時，增加飛機(jī)實際載客量因素，對搭載旅客數(shù)量較多的飛機(jī)給予優(yōu)先著陸概率，盡可能避免該到港飛機(jī)即將搭載的離港旅客滯留;同時，盡量保障飛機(jī)按照預(yù)期時間著陸，如已延誤，則盡量縮短延誤時間，減輕了管制員的負(fù)擔(dān)，也提高飛行安全性。另一方面，對蟻群算法信息素局部堆積導(dǎo)致容易陷入局部最優(yōu)解的缺陷，則改進(jìn)信息素更新模式，使用均衡更新方法更新信息素，以求生成更優(yōu)的到港飛機(jī)序列。

2 均衡更新蟻群算法

蟻群算法(Ant Colony Optimization，ACO)由意大利學(xué)者M(jìn)arco Dorigo 于1992 年的博士論文中提出，最初應(yīng)用于旅行商問題［11］。近年來，蟻群算法因其獨特的正反饋機(jī)制和離散分布式特性，被眾多學(xué)者應(yīng)用于作業(yè)調(diào)度、車輛路徑、網(wǎng)絡(luò)路由、信息檢索等方面［12］。飛機(jī)排序調(diào)度問題屬于NP-難解問題，可以通過轉(zhuǎn)化為作業(yè)調(diào)度問題或者旅行商問題來方便地求解［13］。

本文針對現(xiàn)有算法［1-10］的不足之處，提出一種均衡更新蟻群算法:

1)從旅客的實際利益出發(fā)，為提高航空運輸服務(wù)質(zhì)量，安排飛機(jī)著陸序時增加飛機(jī)實際載客量因素，使載客量大的飛機(jī)具有更早著陸的概率。

2)考慮到管制員負(fù)擔(dān)較重會影響飛行安全性，盡可能減少飛機(jī)延誤，減輕管制員的負(fù)擔(dān)。

以上2 方面體現(xiàn)在均衡更新蟻群算法的轉(zhuǎn)移概率和目標(biāo)函數(shù)中，在轉(zhuǎn)移概率中本文增加了相應(yīng)的啟發(fā)式信息，目標(biāo)函數(shù)的計算考慮了旅客數(shù)和延誤信息。

3)考慮到蟻群算法中信息素局部堆積，容易造成算法陷入局部最優(yōu)解，改進(jìn)蟻群算法的信息素更新過程，使用信息素均衡更新的方式，避免信息素局部堆積，使得算法能在解空間中更加充分地搜索，提高了算法的全局搜索能力，從而生成更優(yōu)的解。

均衡更新蟻群算法流程如圖1 所示。

圖1 均衡更新蟻群算法流程圖

在均衡更新蟻群算法中，每只螞蟻根據(jù)路徑上的信息素和啟發(fā)式信息計算轉(zhuǎn)移概率，選擇下一節(jié)點，即下一架到港飛機(jī)，并將此節(jié)點加入該螞蟻所維護(hù)的禁忌表(禁忌表存放已遍歷的節(jié)點)中，直到遍歷完所有節(jié)點，此時可認(rèn)為生成一個可行解。計算并比較本次迭代中所有螞蟻生成的解對應(yīng)的目標(biāo)函數(shù)值，選擇其中最優(yōu)解作為當(dāng)前迭代的最優(yōu)解，并和迭代至今的全局最優(yōu)解做比較，較優(yōu)者為新的全局最優(yōu)解。最后，每只螞蟻根據(jù)全局最優(yōu)解和自己構(gòu)建的可行解之間的差異對信息素做均衡更新。

1.飛機(jī)排序調(diào)度模型。

在本文中，飛機(jī)排序調(diào)度模型如下，其目標(biāo)是針對當(dāng)T 時間內(nèi)有n(n ＞0)架飛機(jī)待著陸時，在滿足最小安全時間間隔限制基礎(chǔ)上，安排合理的飛機(jī)著陸序列，使得含有飛機(jī)延誤時間和延誤旅客數(shù)參數(shù)的目標(biāo)函數(shù)最小化。

定義1 G=(V，E)表示飛機(jī)排序調(diào)度模型，其中，V 表示待著陸飛機(jī)的節(jié)點集合，E 表示著陸飛機(jī)之間的先后關(guān)系的邊集合。

其中，與模型有關(guān)的符號如下:

Sij:對于任意2 架連續(xù)到港飛機(jī)，較先著陸的飛機(jī)i 為前機(jī)，緊鄰到港的飛機(jī)j 為后機(jī)，Sij表示前機(jī)i和后機(jī)j 之間的最小安全時間間隔。

Ai:飛機(jī)i 的實際著陸時間。

Ei:飛機(jī)i 的預(yù)期著陸時間。

Pi:飛機(jī)i 實際搭載的旅客數(shù)。

Iij:指示飛機(jī)i 和飛機(jī)j 之間的先后關(guān)系，i 為前機(jī)、j 為后機(jī)時為1，其余為0。

c:可容忍的飛機(jī)最大延誤時間，為常量。

2.算法約束條件。

均衡更新蟻群算法求解時，模型和算法必須符合如下約束條件:

1)對于任意2 架到港飛機(jī)，或者i 為前機(jī)，或者j為前機(jī)，或者i 和j 之間不存在連續(xù)序列關(guān)系，即:

2)任意一架到港飛機(jī)i 實際延誤時間不得超過可容忍的最大延誤時間，即:

3)連續(xù)2 架飛機(jī)著陸時，若i 為前機(jī)，j 為后機(jī)，則需滿足最小安全時間間隔:

4)任意2 架飛機(jī)i、j，到港過程中都必須滿足最小安全時間間隔:

3.算法轉(zhuǎn)移概率。

蟻群算法模擬自然界中螞蟻種群行為，在算法中存在由一定個數(shù)的人工螞蟻構(gòu)成的搜索群體，每只螞蟻逐步遍歷節(jié)點直至生成單個解，螞蟻每到達(dá)一個節(jié)點，都會計算轉(zhuǎn)移到當(dāng)前節(jié)點鄰域中節(jié)點的概率，概率性地選擇下一節(jié)點，并將選擇后的節(jié)點加入該螞蟻維護(hù)的禁忌表中。轉(zhuǎn)移概率計算方式如下:

其中:

τij:代表節(jié)點i 到節(jié)點j 上的信息素;

α:代表信息素的影響力因子;

β:代表安全時間間隔啟發(fā)式信息的影響力因子;

γ:代表旅客數(shù)啟發(fā)式信息的影響力因子;

θ:代表延誤時間啟發(fā)式信息的影響力因子;

本文中，螞蟻選擇下一架著陸飛機(jī)時，綜合考慮了信息素、安全時間間隔、搭載旅客數(shù)以及飛機(jī)延誤時間的影響，充分發(fā)揮了蟻群算法的正反饋特性，保證飛機(jī)降落的安全性，盡可能為絕大多數(shù)旅客提供高質(zhì)量的航空運輸服務(wù)，且減少飛機(jī)延誤的可能也從一定程度減輕管制員的工作負(fù)荷。

4.算法目標(biāo)函數(shù)。

根據(jù)上述描述，本文利用提出的算法，在給定時間T 內(nèi)，利用蟻群算法中螞蟻的遍歷，安排飛機(jī)著陸序，使以下目標(biāo)函數(shù)值最小:

該目標(biāo)函數(shù)既考慮了飛機(jī)延誤時間因素，也考慮了每架飛機(jī)實際載客量的因素，目的是得到使所有乘客延誤總時間最小的飛機(jī)著陸序列，以便提供高質(zhì)量的民航運輸服務(wù)。

5.信息素均衡更新機(jī)制。

螞蟻利用轉(zhuǎn)移概率逐步構(gòu)建出一個完整的可行解。首先，計算目標(biāo)函數(shù)，即式(6)，并比較所有結(jié)果取其中最優(yōu)者作為當(dāng)前迭代最優(yōu)解，也即局部最優(yōu)解。然后，與迭代至今為止得到的最優(yōu)解，即全局最優(yōu)解做比較，其中較優(yōu)者作為新的全局最優(yōu)解。完成以上步驟后，用如下方法更新信息素:

1)根據(jù)全局最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值計算信息素增量，其中，fglobal_best是全局最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值，Q 是一個常量:

2)各個螞蟻根據(jù)各自所構(gòu)造的解和全局最優(yōu)解之間的差異來均衡更新信息素，避免信息素局部堆積，增強(qiáng)算法全局搜索能力。更新規(guī)則如下:

其中，ρ1是均衡更新信息素蒸發(fā)率，fk是螞蟻k 所構(gòu)造解對應(yīng)的目標(biāo)函數(shù)值。

3)采用得到最優(yōu)解的螞蟻，更新與之相關(guān)聯(lián)的路徑上的信息素，強(qiáng)化全局最優(yōu)路徑的影響。更新規(guī)則如下，其中，ρ2是全局更新信息素蒸發(fā)率:

總之，上述方法從2 個方面提高算法的效率、優(yōu)化算法得到的解。一是利用當(dāng)前迭代的可行解和全局最優(yōu)解之間的差異均衡地更新信息素，該方式既體現(xiàn)了蟻群算法利用已有搜索信息探索未知解空間的正反饋能力，又有效地避免了信息素局部堆積可能導(dǎo)致的陷入局部最優(yōu)解問題。二是采用得到全局最優(yōu)解的螞蟻更新相關(guān)路徑，進(jìn)一步強(qiáng)化全局最優(yōu)解的影響力，使得搜索朝著最優(yōu)解存在的空間移動。

3 實驗與結(jié)果

本文利用VC ++實現(xiàn)提出的算法，并與先到先服務(wù)(FCFS)算法以及文獻(xiàn)［14］中側(cè)重飛機(jī)延誤時間和延誤架次的蟻群算法求解的結(jié)果比較，評估均衡更新蟻群算法對飛機(jī)排序調(diào)度模型的求解結(jié)果，其中，文獻(xiàn)［14］實驗的目的主要是評價航空公司每天在飛機(jī)延誤數(shù)量與平均時延，以驗證其算法的有效性。限于篇幅，實驗數(shù)據(jù)取國內(nèi)某樞紐機(jī)場30 分鐘內(nèi)預(yù)期到港飛機(jī)信息，共計22 架飛機(jī)，實例具體數(shù)據(jù)見表1。

表1 預(yù)期到港飛機(jī)信息

利用表1 數(shù)據(jù)，分別取前5、10、16、22 架待著陸飛機(jī)數(shù)據(jù)進(jìn)行對比實驗(即n=5，10，16，22)，并取10次實驗結(jié)果的平均值。本文算法參數(shù)設(shè)置為:迭代總次數(shù)NCMAX=100;螞蟻總數(shù)M=20;信息素影響力因子α=1;安全時間間隔啟發(fā)式信息影響力因子β=2;旅客數(shù)啟發(fā)式信息影響力因子γ=2;延誤時間啟發(fā)式信息影響力因子θ=3;均衡更新信息素蒸發(fā)率ρ1=0.05;全局更新信息素蒸發(fā)率ρ2=0.1;常數(shù)Q=10n;a=70;b=0.2;c=1200。實驗結(jié)果如表2，其中，列2～列4 分別為各算法求解n 架飛機(jī)排序后著陸的總用時，列5 表示本文算法運行耗時，列6、列7分別表示采用本文所提出的算法計算得到的n 架飛機(jī)排序后著陸總用時相對于FCFS、文獻(xiàn)［14］所得的總用時降低的比率，其計算方法是:(被比較算法總用時-本文算法總用時)/被比較算法總用時。

由表2 可見，本文均衡更新蟻群算法求解飛機(jī)排序調(diào)度問題能取得優(yōu)于先到先服務(wù)算法和文獻(xiàn)［14］算法的解，優(yōu)化后的飛機(jī)著陸序列完成時間比先到先服務(wù)算法最多可降低12.9%，比文獻(xiàn)［14］降低4.7%。從上述實驗數(shù)據(jù)還可以看出，本文算法計算得到的飛機(jī)著陸總用時與其他算法相比較，其降低的程度與待排序飛機(jī)數(shù)目沒有直接關(guān)聯(lián)，這是因為飛機(jī)之間的安全時間間隔占著陸總用時的絕大部分，而安全時間間隔由前后機(jī)機(jī)型決定，與飛機(jī)數(shù)量無關(guān)。另外，

表2 不同算法實驗結(jié)果

本文算法和文獻(xiàn)［14］算法均考慮到延誤時間對排序結(jié)果的影響，因此可以通過適當(dāng)調(diào)整飛機(jī)順序來減少延誤發(fā)生，但本文算法還考慮到飛機(jī)實際搭載旅客數(shù)，優(yōu)化時兼顧大部分旅客的航程正常進(jìn)行，能從一定程度上避免到港飛機(jī)延誤帶來的離港旅客滯留，為來往旅客提供更好的服務(wù);而文獻(xiàn)［14］算法求解時傾向于減少飛機(jī)調(diào)換順序的次數(shù)，優(yōu)化過程不如本文算法靈活，效果也較本文算法差。本文算法還具有計算用時少的特點，因此可以為實時在線自動化空中交通管制提供支持。

總之，本文算法求解結(jié)果優(yōu)于傳統(tǒng)先到先服務(wù)算法和文獻(xiàn)［14］算法，同時能加入飛機(jī)服務(wù)對象——旅客的切身利益因素，盡量保證為大部分旅客提供準(zhǔn)點、高效的服務(wù)，較好地優(yōu)化飛機(jī)著陸次序和時間，達(dá)到飛機(jī)延誤時間最小化，有效提高系統(tǒng)容量。

4 結(jié)束語

中國民航運量位居世界第二［15］，如何在現(xiàn)有空域結(jié)構(gòu)下優(yōu)化飛機(jī)著陸順序，提高運行效率，并且減少延誤時間是一個重要的研究內(nèi)容。飛機(jī)排序調(diào)度問題屬于NP-難解問題，蟻群算法是一種能有效處理NP-難解問題的啟發(fā)式算法。本文針對飛機(jī)排序調(diào)度問題，提出一種均衡更新蟻群算法，實現(xiàn)多約束優(yōu)化。由于傳統(tǒng)蟻群算法存在因信息素局部堆積導(dǎo)致易陷入局部最優(yōu)解的不足，本文利用螞蟻當(dāng)前迭代計算所得可行解與全局最優(yōu)解之間的差異，均衡地更新信息素，既保留計算所積累的經(jīng)驗，發(fā)揮蟻群算法的正反饋作用，又有利于探索更優(yōu)解。實驗結(jié)果表明，針對飛機(jī)排序調(diào)度問題，本文算法優(yōu)于對比算法，優(yōu)化后的排序可使飛機(jī)著陸序列完成時間減少12.9%，同時還兼顧了大部分旅客的時間，且計算用時較短，能為空中交通管制員實時在線協(xié)調(diào)管理提供支撐。

［1］Zhan Zhi-hui，Zhang Jun，Li Yun，et al.An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem［J］.IEEE Transactions on Intelligent Transportation Systems，2010，11(2):399-412.

［2］Hu Xiao-bing，Di Paolo E.Binary-representation-based genetic algorithm for aircraft arrival sequencing and scheduling［J］.IEEE Transactions on Intelligent Transportation Systems，2008，9(2):301-310.

［3］Hu Xiao-bing，Chen Wen-hua.Genetic algorithm based on receding horizon control for arrival sequencing and scheduling［J］.Engineering Applications of Artificial Intelligence，2005，18(5):633-642.

［4］Robinson J E，Davis T J，Isaacson D R.Fuzzy reasoningbased sequencing of arrival aircraft in the terminal area［C］// AIAA Guidance，Navigation and Control Conference.1997:1-11.

［5］Hu Xiao-bing，Di Paolo E A.A ripple-spreading genetic algorithm for the aircraft sequencing problem［J］.Evolutionary Computation，2011，19(1):77-106.

［6］Psaraftis H N.A dynamic programming approach for sequencing groups of identical jobs［J］.Operations Research，1980，28(6):1347-1359.

［7］Zhao Xiuli，Guo Yanchi.Study on GRAPS-ACO algorithm for irregular flight rescheduling［C］// IEEE 2012 International Conference on Computer Science ＆ Service System(CSSS).2012:266-269.

［8］劉洪，楊紅雨，彭莉娟.基于分組的進(jìn)近航班著陸調(diào)度算法研究［J］.電子科技大學(xué)學(xué)報，2013，42(4):615-620.

［9］趙嶷飛，朱瀟，王紅勇.終端區(qū)飛機(jī)排序的人工蜂群算法［J］.科學(xué)技術(shù)與工程，2013，13(31):9258-9262.

［10］馮興杰，孟欣.基于免疫粒子群優(yōu)化算法的航班著陸調(diào)度研究［J］.計算機(jī)工程，2012，38(13):273-279.

［11］Dorigo M.Optimization，Learning and Nature Algorithms［D］.Milan:Dipartmento di Elettronica，Politecnico di Milano，1992.

［12］Dorigo M，Birattari M，Stutzle T.Ant colony optimization［J］.Computational Intelligence Magazine，IEEE，2006，1(4):28-39.

［13］Bencheikh G，Boukachour J，Alaoui A E H.Improved ant colony algorithm to solve the aircraft landing problem［J］.International Journal of Computer Theory and Engineering，2011，3(2):224-233.

［14］Wang Shi-dong，Zhang Yue，Zhang Zhi-hai，et al.Multiobjectives optimization on flights landing sequence at busy airport［J］.Journal of Transportation Systems Engineering and Information Technology，2012，12(4):135-142.

［15］于劍，王文濤，李航.對中國航空公司中歐市場運量的影響分析［J］.中國民航大學(xué)學(xué)報，2011，29(1):42-45.

［16］Cao Song，Sun Fuchun，Hu Laihong，et al.Departure aircraft sequence optimization using EDA［J］.Journal of Tsinghua University Science and Technology，2012，52(1):66-71.

［17］許軍海，何長青，王昭.機(jī)場終端區(qū)飛機(jī)排序的遺傳算法［J］.信息系統(tǒng)工程，2013(10):132-134.