多蟻群協(xié)同進化的滑行道調度優(yōu)化

馮興杰，杜姍姍

（中國民航大學 計算機科學與技術學院，天津300300）

0 引 言

國內外許多學者對滑行道調度問題進行了研究，文獻［1，2］都嘗試用遺傳算法解決本問題；文獻 ［3］提出了一種新的調度策略，建立了對應的模型，并采用floyd算法為每個航班提供多條無障礙的理想路徑；文獻 ［4］應用A＊算法對航班滑行軌跡進行了預測；文獻 ［5］采用了蟻群算法解決本文問題。然而這些方法都沒有考慮航班間的調度優(yōu)先級順序。

本文提出了運用多蟻群協(xié)同進化的思想解決滑行道調度問題。對每個航班的滑行調度都生成一個種群，利用蟻群算法善于解決智能尋徑等問題的特點，在種群內部用來搜索指定端點的滑行路徑，并對滑行路徑進行沖突檢測與解決，保證滑行的安全性；利用合作型協(xié)同進化算法解決航班的調度優(yōu)先級順序，各種群之間協(xié)同進化，形成一個協(xié)同的滑行調度計劃。實驗結果表明，該算法具有顯著的優(yōu)勢。

1 問題及模型

1.1 問 題

滑行道調度［6－8］問 題 （aircraft taxi scheduling problem，ATP）是保證航班沒有滑行沖突的條件下，根據航班既定的滑行起點和終點、開始滑行時間、進離場類型和航班類型，確定最優(yōu)滑行路徑以及航班到達每個節(jié)點的時間，使總滑行時間最少。

機場滑行道布局抽象化為一個網絡圖G ＝（V，E），其中，V 代表滑行道與停機位以及跑道的交點、滑行道和滑行道的交叉點；E 代表滑行道、跑道以及脫離道，如圖1 所示。A ＝｛1，…，n｝代表航班的集合，其中，Aarr∈A 表示進港航班；Adep∈A 表示離港航班。R＝｛R1，R2，…，Ri…，Rn｝表示所有航班滑行路徑，其中，Ri＝｛ui1，ui2，ui3，…，uiki｝表示航班i滑行路徑。

圖1 機場網絡

飛機滑行時可能遇到3種類型沖突［9］，分別為交叉沖突、超越沖突、對頭沖突。

1.2 模 型

定義變量如下：

A：航班數(shù)；ziju∈ ｛0，1｝，表示當航班i在航班j 之前到達節(jié)點u時，ziju＝1，反之，ziju＝0；tiu為航班i到達節(jié)點u的實際時間；下標uik1表示航班i的滑行起點；下標uiki表示航班i的滑行終點，dsep表示航班間安全滑行距離。本文航班i的滑行時間是指航班從機器開始發(fā)動到機器關閉的時間。目標函數(shù)為

為使調度更加公平和合理，本文在模型中引入了航班的出發(fā)延誤時間，即離港航班在停機坪的等待時間。其中，tid為第i個航班出發(fā)時的延誤時間，k1和k2表示權值系數(shù)。

約束條件

其中，式 （2）表示序列約束，當節(jié)點u 是航班i 和航班j的公共節(jié)點時，只能按順序先后經過，不能同時到達；式（3）表示交叉沖突約束，航班i和航班j 在到達u 的時間必須滿足最小安全間隔dsep；式 （4）表示超越沖突約束，先到達節(jié)點u的航班必須先到達節(jié)點v；式 （5）表示對頭沖突約束，到達節(jié)點u 的航班必須先到達節(jié)點v；式 （6）表示進港航班i在預計到港時間EATi著陸，并立即脫離跑道的時間；式 （7）表示航班i從停機坪的推出時間OBTi，這個時間也就是離港航班的開始滑行時間；式 （8）表示航班必須在預計目標離港時間TTDi到達跑道入口準備起飛。

2 基于蟻群算法的滑行道優(yōu)化調度算法

蟻群算法，是一種有效的啟發(fā)式仿生優(yōu)化算法。該算法具有正反饋性、強啟發(fā)性、協(xié)調性以及并行性，很善于處理滑行調度這種復雜的路徑尋優(yōu)問題。

本文蟻群算法分為兩個部分。首先，根據協(xié)同進化算法解決航班的調度優(yōu)先級順序；然后在各種群間根據協(xié)同進化的思想，共同進化搜索出協(xié)同調度的優(yōu)化方案。

2.1 機場網絡的數(shù)據結構

在基于蟻群算法的滑行道調度尋優(yōu)設計時，首先需要定義數(shù)據結構。數(shù)據結構分為節(jié)點結構和邊結構，其中節(jié)點的存儲采用鄰接表結構。在節(jié)點的存儲數(shù)據結構中，引入了航班號flightList鏈表和時間timeList鏈表，分別用于記錄經過節(jié)點的航班和時間。

2.2 轉移策略

螞蟻k在搜索滑行路徑時，由當前節(jié)點選擇下一個未被訪問的可行節(jié)點時，其轉移策略是輪盤賭，概率按式（9）所示，在可行節(jié)點集合C中選擇下一個節(jié)點 （i，j）

其中，τ（i，j，r）和η（i，j，r）分別表示將要訪問節(jié)點（i，j，r）的信息素信息和啟發(fā)信息；α和β分別表示路徑上的信息量對以后選擇路徑的影響程度和啟發(fā)式信息的重要程度。

在滑行道優(yōu)化調度時，機場網絡的存儲在鄰接表中，所以通過鄰接表的查詢很快找到下一個可行節(jié)點，減少路徑規(guī)劃時搜索的范圍。

2.3 信息素更新

螞蟻在搜索路徑時，當出現(xiàn)不可行滑行路徑，就對當前經過的路徑節(jié)點信息素進行一定的揮發(fā)，避免螞蟻再次搜索不可行路徑。

為避免算法在搜索過程中陷入局部最優(yōu)，本文引自文獻 ［10］的動態(tài)信息素更新策略，對信息素進行局部更新和全局更新。

（1）信息素的局部更新：螞蟻k 每經過節(jié)點（i，j，r），都用式 （10）對邊（i，j，r）進行信息素更新

其中，ε∈ （0，1）為信息素的局部蒸發(fā)率，τ0為信息素的初始值。

（2）信息素的全局動態(tài)更新：當?shù)淮魏螅檬剑?1）對滑行時間最短的路徑進行信息素的更新

其中，ρ∈ （0，1）表示信息素的全局蒸發(fā)率；dm表示當前滑行時間最小值；dl表示當前迭代的滑行時間最小值。

在開始迭代時，dm和dl的差距可能很大，通過式 （12）可以大幅度地增強最短滑行時間上的信息素濃度，吸引更多的螞蟻選擇這個路徑，使dm和dl的差距逐步縮小，當Δτij變?yōu)?時，本次迭代的具有最短滑行時間的路徑只進行信息素揮發(fā)，避免了因信息素的過分加強而造成算法陷入局部最優(yōu)。

2.4 適應值函數(shù)

螞蟻k在迭代第t次時的適應函數(shù)如下

式中：T1（t）和T2（t）——螞蟻k第t次迭代時的滑行時間和出發(fā)延誤時間；k1和k2——滑行時間和延誤時間的權值。

2.5 基于兩階段鎖的沖突解決算法

航班滑行過程實質是對資源的預約過程。在機場網絡有限的資源中，滑行道、停機位、脫離道、跑道等待點、各網絡節(jié)點都視為資源，航班相當于事物，因此在某一時段內，所有航班的滑行過程，相當于對共享資源的調度分配問題。

航班間的沖突實質是資源的沖突，當航班申請對節(jié)點資源的占用時，就是對該節(jié)點資源加S鎖，當多個航班申請時，按照優(yōu)先級的高低逐個進行加S鎖，優(yōu)先級高的航班j若加鎖成功，則航班j 就對該節(jié)點的時間窗［ETj，LTj］加鎖；優(yōu)先級低的航班i也申請已經被鎖住的該時間段時，加鎖失敗，則航班i只能向前回溯，當修改其中的一部分時，就要在滿足約束的條件下進行反推，并同時修改相關的部分，否則，會導致不可預料的錯誤，最后將其占用資源的時間順延至［ETj，LTj］之外的安全時刻。這樣可以保證調度的每個航班都是安全的，沒有沖突的，更符合實際的操作規(guī)則。

交叉沖突檢測與解決算法如下：

超越沖突和對頭沖突的解決方法是，讓先經過公共邊（互逆邊）一側端點的航班，也先經過另一端點；然后調用上述算法確定經過節(jié)點k的具體時間點。

3 多蟻群協(xié)同優(yōu)化的滑行道調度

3.1 滑行道調度順序問題

由于在給定時間內，滑行道調度通常要涉及調度多個航班，它們之間是相互影響的，其中一個航班的滑行時間短，不能代表全局滑行時間最短。因此，航班之間的調度順序，對總調度結果是有很大影響的。而在前人的研究中卻很少涉及航班調度優(yōu)先級順序的研究和大面積延誤下的隨機調度優(yōu)化。為此，本文在采用協(xié)同進化算法，來規(guī)劃航班的調度順序，用蟻群算法優(yōu)化滑行路徑。

3.2 多蟻群協(xié)同進化算法

借鑒協(xié)同進化的思想，采用分而治之的策略。將復雜的多個航班協(xié)同路徑規(guī)劃度問題分解為多個單航班路徑規(guī)劃問題，通過單個航班規(guī)劃之間的迭代求解以及多航班之間協(xié)同約束的處理，實現(xiàn)對多個航班的協(xié)同調度，從整體上解決調度順序問題。

在滑行道調度時，將每個航班調度對應一個蟻群，所有蟻群構成一個協(xié)同體。在每次迭代時，各蟻群的進化順序是隨機的，各蟻群均采用協(xié)同進化算法進行路徑搜索。在求解蟻群k 的最優(yōu)解時，將蟻群k 的每個個體與所有完成進化蟻群的最優(yōu)個體作為整體解，并進行綜合評價，保存歷史最優(yōu)解，經過不斷迭代，從而找出最優(yōu)解。

算法描述：

（1）構造各初始蟻群及其初始信息素，迭代次數(shù)j＝0。每個航班的滑行路徑由n只螞蟻進行搜索。令總最小滑行時間time＝＋∞，已經完成進化的蟻群個數(shù)為Num。

（2）令Num＝0，初始化各蟻群搜索環(huán)境。

（3）隨機選擇一個沒有進化的種群Bi進行進化。

（4）將已完成進化種群B1，B2…Bi－1，Bi＋1…Bj的最優(yōu)個體經過節(jié)點的時間進行標記，將其占有的時間段加鎖。

（5）對Bi進行蟻群路徑搜索算法，其個體適應度值取決于當前已進化蟻群的最優(yōu)個體形成的新環(huán)境，記錄Bi的最優(yōu)個體。

（6）Num＋＋，若還有沒進化的蟻群，則轉 （3）；否則，判斷是否達到最大迭代次數(shù)，若沒有，更新time值，使其記錄歷史最優(yōu)值，j＋＋，轉 （2），否則，轉 （7）。

（7）輸出最終調度順序和滑行路徑。

算法流程，如圖2所示。

圖2 算法流程

4 實 驗

為驗證本文算法的有效性，機場以圖1所示簡單虛擬機場為例，機場有3條跑道，停機坪位于滑行道網絡的中心，并且多個停機坪進口和出口。航班數(shù)據以文獻 ［11］的8個航班實例進行實驗驗證。

實驗時，各參數(shù)確定如下：種群大小為N＝30，迭代次數(shù)為M＝200，α＝1，β＝3。航班間的安全距離dsep＝200m。

本文在運行實驗10次后，取接近均值的一個結果，實驗結果對比如表1所示。飛機的調度順序為：1－＞8－＞6－＞3－＞7－＞2－＞4－＞5。為了說明本文算法的有效性，與基于先來先服務調度順序的普通蟻群算法 （即，給定調度順序）進行了比較。給定蟻群算法的調度順序為：7－＞8－＞2－＞1－＞4－＞3－＞6－＞5。雖然給定蟻群算法都能成功解決沖突，但存在4處沖突，從而致使航班在這些位置進行延誤等待；而本文算法出現(xiàn)了2次沖突，分別在節(jié)點N23和N17處，較成功的選擇其它路徑，避開了沖突，最佳滑行路徑時間表示在理想沒有沖突的條件下的滑行時間，結果見表1。

表1 滑行結果對比

結果表明，給定順序蟻群算法的總滑行距離為9500m，而基于本文算法的滑行距離為8500m，雖然本文算法的出發(fā)等待時間與普通蟻群算法相當，但滑行距離縮短了1000m，滑行時間也減少了215s，驗證了本文算法的有效性。

航班的滑行調度就是確定每個航班的滑行路徑和經過每個節(jié)點的時刻，下面給出了所有航班的優(yōu)化調度結果。

5 結束語

本文針對滑行道調度優(yōu)化問題提出了基于合作型的協(xié)同多蟻群調度優(yōu)化算法。該算法將協(xié)同進化的思想引入蟻群調度算法，協(xié)同各個蟻群間的相互影響，并解決了調度優(yōu)化時受調度順序影響的問題。仿真結果表明，本文算法較給定順序的蟻群算法，有效縮短了滑行時間和滑行距離，獲得了更優(yōu)的調度方案，驗證了本文算法的有效性。但是本文沒有考慮航班的機型、優(yōu)先級，以及航班滑行速度的變化等因素，接下來研究的方向是考慮這些因素，使研究更符合實際情況。

［1］DONG Tiansheng，PENG Jian.Airport taxi scheduling optimization strategy for based on genetic algorithm ［J］.Journal of Computer Applications，2010，3 （2）：482－485 （in Chinese）.［蕫天圣，彭艦.基于遺傳算法的機場滑行調度優(yōu)化策略 ［J］.計算機應用，2010，3 （2）：482－485.］

［2］LIU Zhaoming，GE Hongwei，QIAN Feng.Airport scheduling optimization algorithm based on genetic algorithm ［J］.Journal of East China University of Science and Technology（Natural Science Edition），2008，34 （3）：392－398 （in Chinese）.［劉兆明，葛宏偉，錢峰.基于遺傳算法的機場調度優(yōu)化算法 ［J］.華東理工大學學報 （自然科學版），2008，34（3）：392－398.］

［3］MOU Deyi，LIU Jinfeng.The scheduling strategy model for airport taxiway based on ideal glide path ［J］.Journal of Dalian Jiaotong University，2011，32 （6）：41－45 （in Chinese）.［牟德一，劉金鳳.基于理想滑行路徑的機場滑行道調度策略模型［J］.大連交通大學學報，2011，32 （6）：41－45.］

［4］LI Nan，ZHAO Qing，XU Xiaohao.Research on taxing optimization for aircraft based on improved A＊ algorithm ［J］.Computer Simulation，2012，29 （7）：88－92 （in Chinese）.［李楠，趙擎，徐肖豪.基于A＊算法的機場滑行路徑優(yōu)化研究 ［J］.計算機仿真，2012，29 （7）：88－92.］

［5］DING Jianli，LI Xiaoli，LI Quanfu.Optimal scheduling model for hub airport taxi based on improved ant colony collaborative algorithm ［J］.Journal of Computer Applications，2010，30（4）：1000－1003 （in Chinese）.［丁建立，李曉麗，李全福.基于改進蟻群協(xié)同算法的樞紐機場場面滑行道優(yōu)化調度模型［J］.計算機應用，2010，30 （4）：1000－1003.］

［6］Clare GL，Richards AG.Optimization of taxiway routing and runway scheduling ［J］.IEEE Transactions on Intelligent Transportation Systems，2011，12 （4）：1000－1013.

［7］Wei B，Centarti F，Schmitt F，et al.Route－based detection of conflicting ATC clearances on airports［J］.arXiv preprint ar－Xiv：1304.6494，2013.

［8］Clare GL，Richards AG.Optimization of taxiway routing and runway scheduling ［J］.IEEE Transactions on Intelligent Transportation Systems，2011，12 （4）：1000－1013.

［9］ZHONG Yuming.Evaluation system study for airport ground running simulation ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2009 （in Chinese）. ［鐘育鳴.機場地面運行仿真評估系統(tǒng)研究 ［D］.南京：南京航空航天大學，2009.］

［10］WANG Peidong.Improved ant colony algorithm and its application in path planning problem ［D］.Qingdao：Ocean University of China，2012 （in Chinese）. ［王沛棟.改進蟻群算法及在路徑規(guī)劃問題的應用研究 ［D］.青島：中國海洋大學，2012.］

［11］Roling PC，Visser HG.Optimal airport surface traffic planning using mixed－integer linear programming ［J］.International Journal of Aerospace Engineering，2008 （1）：11.