多蟻群協(xié)同進(jìn)化的滑行道調(diào)度優(yōu)化

馮興杰，杜姍姍

（中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300300）

0 引 言

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

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

1 問(wèn)題及模型

1.1 問(wèn) 題

滑行道調(diào)度［6－8］問(wèn) 題 （aircraft taxi scheduling problem，ATP）是保證航班沒(méi)有滑行沖突的條件下，根據(jù)航班既定的滑行起點(diǎn)和終點(diǎn)、開(kāi)始滑行時(shí)間、進(jìn)離場(chǎng)類(lèi)型和航班類(lèi)型，確定最優(yōu)滑行路徑以及航班到達(dá)每個(gè)節(jié)點(diǎn)的時(shí)間，使總滑行時(shí)間最少。

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

圖1 機(jī)場(chǎng)網(wǎng)絡(luò)

飛機(jī)滑行時(shí)可能遇到3種類(lèi)型沖突［9］，分別為交叉沖突、超越?jīng)_突、對(duì)頭沖突。

1.2 模 型

定義變量如下：

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

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

約束條件

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

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

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

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

2.1 機(jī)場(chǎng)網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)

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

2.2 轉(zhuǎn)移策略

螞蟻k在搜索滑行路徑時(shí)，由當(dāng)前節(jié)點(diǎn)選擇下一個(gè)未被訪(fǎng)問(wèn)的可行節(jié)點(diǎn)時(shí)，其轉(zhuǎn)移策略是輪盤(pán)賭，概率按式（9）所示，在可行節(jié)點(diǎn)集合C中選擇下一個(gè)節(jié)點(diǎn) （i，j）

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

在滑行道優(yōu)化調(diào)度時(shí)，機(jī)場(chǎng)網(wǎng)絡(luò)的存儲(chǔ)在鄰接表中，所以通過(guò)鄰接表的查詢(xún)很快找到下一個(gè)可行節(jié)點(diǎn)，減少路徑規(guī)劃時(shí)搜索的范圍。

2.3 信息素更新

螞蟻在搜索路徑時(shí)，當(dāng)出現(xiàn)不可行滑行路徑，就對(duì)當(dāng)前經(jīng)過(guò)的路徑節(jié)點(diǎn)信息素進(jìn)行一定的揮發(fā)，避免螞蟻再次搜索不可行路徑。

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

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

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

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

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

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

2.4 適應(yīng)值函數(shù)

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

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

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

航班滑行過(guò)程實(shí)質(zhì)是對(duì)資源的預(yù)約過(guò)程。在機(jī)場(chǎng)網(wǎng)絡(luò)有限的資源中，滑行道、停機(jī)位、脫離道、跑道等待點(diǎn)、各網(wǎng)絡(luò)節(jié)點(diǎn)都視為資源，航班相當(dāng)于事物，因此在某一時(shí)段內(nèi)，所有航班的滑行過(guò)程，相當(dāng)于對(duì)共享資源的調(diào)度分配問(wèn)題。

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

交叉沖突檢測(cè)與解決算法如下：

超越?jīng)_突和對(duì)頭沖突的解決方法是，讓先經(jīng)過(guò)公共邊（互逆邊）一側(cè)端點(diǎn)的航班，也先經(jīng)過(guò)另一端點(diǎn)；然后調(diào)用上述算法確定經(jīng)過(guò)節(jié)點(diǎn)k的具體時(shí)間點(diǎn)。

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

3.1 滑行道調(diào)度順序問(wèn)題

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

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

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

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

算法描述：

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

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

（3）隨機(jī)選擇一個(gè)沒(méi)有進(jìn)化的種群Bi進(jìn)行進(jìn)化。

（4）將已完成進(jìn)化種群B1，B2…Bi－1，Bi＋1…Bj的最優(yōu)個(gè)體經(jīng)過(guò)節(jié)點(diǎn)的時(shí)間進(jìn)行標(biāo)記，將其占有的時(shí)間段加鎖。

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

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

（7）輸出最終調(diào)度順序和滑行路徑。

算法流程，如圖2所示。

圖2 算法流程

4 實(shí) 驗(yàn)

為驗(yàn)證本文算法的有效性，機(jī)場(chǎng)以圖1所示簡(jiǎn)單虛擬機(jī)場(chǎng)為例，機(jī)場(chǎng)有3條跑道，停機(jī)坪位于滑行道網(wǎng)絡(luò)的中心，并且多個(gè)停機(jī)坪進(jìn)口和出口。航班數(shù)據(jù)以文獻(xiàn) ［11］的8個(gè)航班實(shí)例進(jìn)行實(shí)驗(yàn)驗(yàn)證。

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

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

表1 滑行結(jié)果對(duì)比

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

航班的滑行調(diào)度就是確定每個(gè)航班的滑行路徑和經(jīng)過(guò)每個(gè)節(jié)點(diǎn)的時(shí)刻，下面給出了所有航班的優(yōu)化調(diào)度結(jié)果。

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

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

［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）.［蕫天圣，彭艦.基于遺傳算法的機(jī)場(chǎng)滑行調(diào)度優(yōu)化策略 ［J］.計(jì)算機(jī)應(yīng)用，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）.［劉兆明，葛宏偉，錢(qián)峰.基于遺傳算法的機(jī)場(chǎng)調(diào)度優(yōu)化算法 ［J］.華東理工大學(xué)學(xué)報(bào) （自然科學(xué)版），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ī)場(chǎng)滑行道調(diào)度策略模型［J］.大連交通大學(xué)學(xué)報(bào)，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íng)＊算法的機(jī)場(chǎng)滑行路徑優(yōu)化研究 ［J］.計(jì)算機(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）.［丁建立，李曉麗，李全福.基于改進(jìn)蟻群協(xié)同算法的樞紐機(jī)場(chǎng)場(chǎng)面滑行道優(yōu)化調(diào)度模型［J］.計(jì)算機(jī)應(yīng)用，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）. ［鐘育鳴.機(jī)場(chǎng)地面運(yùn)行仿真評(píng)估系統(tǒng)研究 ［D］.南京：南京航空航天大學(xué)，2009.］

［10］WANG Peidong.Improved ant colony algorithm and its application in path planning problem ［D］.Qingdao：Ocean University of China，2012 （in Chinese）. ［王沛棟.改進(jìn)蟻群算法及在路徑規(guī)劃問(wèn)題的應(yīng)用研究 ［D］.青島：中國(guó)海洋大學(xué)，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.