基于AATCSR-SA算法的多跑道進(jìn)離場(chǎng)航班優(yōu)化調(diào)度

黃 濤，郝 雅

(沈陽(yáng)航空航天大學(xué) a通用航空產(chǎn)業(yè)發(fā)展研究中心;b民用航空學(xué)院，沈陽(yáng) 110036)

近年來(lái)，隨著空中交通流量的快速增長(zhǎng)，許多機(jī)場(chǎng)均有大面積航班延誤現(xiàn)象出現(xiàn)，嚴(yán)重危及飛行安全，同時(shí)也給乘客的出行帶來(lái)諸多的不便。針對(duì)這種現(xiàn)象，機(jī)場(chǎng)方面采取了很多措施，我國(guó)的一些樞紐機(jī)場(chǎng)修建了多條跑道，如首都機(jī)場(chǎng)、浦東機(jī)場(chǎng)以及白云機(jī)場(chǎng)等。多跑道進(jìn)離場(chǎng)航班的排序優(yōu)化問(wèn)題是在保證飛行安全即航班之間保證最小安全間隔的前提下，運(yùn)用智能的優(yōu)化方法，合理安排航班的起降順序，最大程度減少航班延誤帶來(lái)的損失。因此，如何安排區(qū)域內(nèi)飛機(jī)的起降次序，已成為人們關(guān)注的焦點(diǎn)。

針對(duì)航班排序問(wèn)題，國(guó)內(nèi)外的專家學(xué)者研究的重點(diǎn)不盡相同。在國(guó)外，Dear[1]早在1976年就對(duì)航班排序問(wèn)題進(jìn)行了研究，并提出解決航班排序問(wèn)題可以采用數(shù)學(xué)求解方法，首次提出約束位置轉(zhuǎn)換法解決ASP問(wèn)題。Beasley[2]提出混合整數(shù)規(guī)劃法解決航班排序問(wèn)題，但由于航班排序問(wèn)題本身是NP-Hard的。因此，隨著航班數(shù)量的增大，算法的復(fù)雜度也按照指數(shù)增長(zhǎng)的速度在遞增。Paolo[3]采用遺傳算法對(duì)多跑道的進(jìn)場(chǎng)航班排序問(wèn)題進(jìn)行了求解，在算法中應(yīng)用了均勻交叉算子的方式。Zhan[4]在進(jìn)場(chǎng)航班排序中采用了滾動(dòng)時(shí)域的蟻群算法進(jìn)行求解。Wieland[5]考慮最小間隔約束，提出以航班最小延誤量為目標(biāo)的混合整數(shù)規(guī)劃算法。Chandrasekar等[6]提出最速搜索規(guī)則與分支定界相結(jié)合的方法，并在多跑道進(jìn)場(chǎng)航班排序的應(yīng)用中使用，證明了算法的有效性和實(shí)用性。我國(guó)對(duì)于航班排序問(wèn)題的研究起步較晚，直至上世紀(jì)80年代，隨著航班量的不斷增加，管制人員的壓力日益增大，國(guó)內(nèi)學(xué)者逐漸意識(shí)到航班排序研究的重要性。荀海波[7]通過(guò)設(shè)定調(diào)度邊界，提出了改進(jìn)的先到先服務(wù)算法;徐肖豪[8]應(yīng)用遺傳算法解決航班排序問(wèn)題，用兩個(gè)染色體代表航班與跑道，通過(guò)它們之間的交叉遺傳尋找最優(yōu)解。曹嵩[9]將起飛航班延誤所產(chǎn)生的系列影響加入到模型建立過(guò)程中，提出了一種基于滑動(dòng)時(shí)間窗的分布估計(jì)算法。李曉麗[10]提出了改進(jìn)的免疫克隆方法，將航班排序視為免疫系統(tǒng)進(jìn)行ASP問(wèn)題的求解。徐肖豪等[11]以最小化延誤時(shí)間為目標(biāo)，引入基因移位思想，解決了傳統(tǒng)蛙跳算法會(huì)使航班排序問(wèn)題產(chǎn)生無(wú)效解的問(wèn)題，提出了改進(jìn)的蛙跳算法。

鑒于上述分析，目前針對(duì)單跑道航班排序的研究較多，關(guān)于多跑道航班排序的文獻(xiàn)較少，亦或是將進(jìn)港航班與出港航班分別研究，在實(shí)際情況中，不會(huì)有大量飛機(jī)集中離場(chǎng)或進(jìn)場(chǎng)，而是進(jìn)離場(chǎng)航班同時(shí)存在。因此，研究多跑道進(jìn)離場(chǎng)航班協(xié)同排序更具實(shí)際意義。本文將基于以上信息，考慮最小安全間隔約束以及每個(gè)航班都有不同的到達(dá)時(shí)間和間隔時(shí)間，提出一種基于優(yōu)先級(jí)的貪心算法與模擬退火算法相結(jié)合的方法，旨在高效解決最小化加權(quán)總延遲為目標(biāo)的多跑道進(jìn)離場(chǎng)航班排序問(wèn)題。

1 多跑道進(jìn)離場(chǎng)航班調(diào)度模型

1.1 問(wèn)題描述

航班的延誤會(huì)產(chǎn)生一定的延遲成本，進(jìn)離場(chǎng)航班排序問(wèn)題即是指如何根據(jù)給定的起降時(shí)間，在保證飛行安全的前提下，最大限度地減少整個(gè)起降隊(duì)列的延誤成本。具體來(lái)說(shuō)，對(duì)于等待起飛或降落的n架航班按預(yù)計(jì)到達(dá)或起飛時(shí)間安排在m條跑道上，ETi表示航班預(yù)計(jì)到達(dá)/離場(chǎng)時(shí)間，Ti表示航班調(diào)度后的起降時(shí)間，Si,j表示第i和第j架航空器之間的安全間隔。由于規(guī)定的最小安全間隔的影響，且任意三架航空器在機(jī)型不同或者起降方式不同時(shí)未必滿足三角不等式(Si,k≤Si,j+Sj,k，i,j,k表示第i,j,k架航空器)，因此，不僅要考慮與其相鄰起降飛機(jī)的尾流影響，還應(yīng)考慮與其不相鄰的緊前三架航空器產(chǎn)生的影響。根據(jù)文獻(xiàn)[12],本文采用公式(1)-(4)確定航班調(diào)度后的起降時(shí)間：

T1=ET1

(1)

T2=max{ET2,ET1+S1,2}

(2)

T3=max{ET3,ET1+S1,3，ET2+S2,3}

(3)

Tk=max{ETk,ETk-1+Sk-1,k，ETk-2+Sk-2,k,ETk-3+Sk-3,k}?k=4,5…,n

(4)

1.2 模型建立

1.2.1 目標(biāo)函數(shù)

若航班未按計(jì)劃時(shí)間起飛/著陸，會(huì)產(chǎn)生一定的延遲成本，用wj表示延誤成本系數(shù)，其中j代表第j架航空器。因此，本文所優(yōu)化的目標(biāo)函數(shù)是使所有航班的延遲成本最小，即：

Min∑wj(Tj-ETj)

(5)

其中，延誤成本系數(shù)wj采用文獻(xiàn)[13]中三維優(yōu)先級(jí)表設(shè)計(jì)方法。

wj=「M/Priorj?

(6)

Priorj表示航班j的優(yōu)先級(jí)，M為所有航班所在優(yōu)先級(jí)表中的最大值。

1.2.2 約束條件

(1)最小時(shí)間間隔約束

為保證航空器起飛或降落不受前機(jī)的尾流影響，需要每架航空器在進(jìn)場(chǎng)或離場(chǎng)時(shí)與前機(jī)保持最小的安全間隔，即規(guī)定的最小時(shí)間間隔。值得注意的是，若將進(jìn)離場(chǎng)航班分離，單獨(dú)進(jìn)場(chǎng)(只運(yùn)行進(jìn)場(chǎng)航班管制)或單獨(dú)離場(chǎng)(只運(yùn)行離場(chǎng)航班管制)時(shí)，每架航空器僅需考慮與其緊前一架航空器的最小時(shí)間間隔；對(duì)于混合起降航班，任一航空器需要考慮與其緊前三架航空器的最小時(shí)間間隔。因此，本文需要考慮的最小時(shí)間間隔均為該架航空器與其緊前三架航空器之間的安全間隔。

表1 起降飛機(jī)尾渦流間隔標(biāo)準(zhǔn) (秒)

(其中，H、L、S表示重型、中型和輕型航空器；D和A分別表示起飛和著陸航空器。)

(2)時(shí)間窗約束

時(shí)間窗約束是指飛機(jī)調(diào)度的時(shí)間必須在預(yù)計(jì)到達(dá)/起飛時(shí)刻與最晚到達(dá)/起飛時(shí)刻之間，用區(qū)間[ETi,LTi]表示。因此，對(duì)于著陸航班i與起飛航班j分別有：

ETi≤ATi≤LTi

(7)

ETj≤DTj≤LTj

(8)

(3)優(yōu)先級(jí)約束

對(duì)于延遲時(shí)間的權(quán)重系數(shù)wj，本文取wj=「M/Priorj?,其中,M為優(yōu)先級(jí)表中的最大值，Priorj為航班j的優(yōu)先級(jí)，本文中Priorj的確定采用文獻(xiàn)[13]中的三維優(yōu)先級(jí)表設(shè)計(jì)方法，每架航班考慮航程是否連續(xù)，運(yùn)行方式(起飛或降落) 以及飛機(jī)類型這三個(gè)參數(shù)。此外，三個(gè)特征參數(shù)的重要程度依次遞減。以航班j為例，其對(duì)應(yīng)的特征參數(shù)，即航程是否連續(xù)，運(yùn)行方式以及航班類型分別表示為Ij,Jj,Rj。其中，

因此，航班j的優(yōu)先級(jí)可以表示為

Priorj=priorj(Ij,Jj,Rj)=(priorj-1)(priorj-2)(priorj-3)/6+(2priorj-Ij-2)(Ij-1)/2+Jj

(9)

其中，

priorj(Ij,Jj,Rj)=Ij+Jj+Rj

(10)

2 算法設(shè)計(jì)

2.1 AATCSR算法

AATCSR復(fù)合貪婪算法作為AATCS規(guī)則的擴(kuò)展，由Lee等人[14]提出。在AATCSR中，我們考慮了間隔時(shí)間和準(zhǔn)備時(shí)間的新約束。所提出的AATCSR啟發(fā)式算法是動(dòng)態(tài)的，因?yàn)樵诿考茱w機(jī)被分配到跑道后，其余的飛機(jī)將根據(jù)優(yōu)先級(jí)進(jìn)行排序。算法步驟如下：

Step1.設(shè)定初值

Step2.定飛機(jī)。根據(jù)優(yōu)先級(jí)表計(jì)算各航班的優(yōu)先級(jí)系數(shù)，選取最大者作為待排飛機(jī)。

Step3.定跑道。選取飛機(jī)在跑道上開(kāi)始操作(起飛或著陸)時(shí)間最早的跑道。

Step4.循環(huán)，直至排完所有航班。

偽代碼如下：

設(shè)置初值，決定時(shí)間t=0，開(kāi)始時(shí)間tj=0，跑道集合M={1,2,…,m}，航班集合J={1,2,…,n}

計(jì)算優(yōu)先級(jí)wj

WhileJ≠φ

Whiletj

Findj={j∈J：πj(t,k)=max{πl(wèi)(t,k)}}

Findi={i∈M:PSTi(t)=min{PSTm(t)}}

更新tj，tj=PSTi(t)

更新時(shí)間表長(zhǎng)Cmaxi(t)=tj

2.2 基于AATCSR的模擬退火算法

模擬退火算法最顯著的優(yōu)點(diǎn)是通用，并且算法的結(jié)果質(zhì)量較高，能夠較好地達(dá)到預(yù)期目標(biāo)。從算法的結(jié)構(gòu)可知，新的狀態(tài)產(chǎn)生函數(shù)、初溫、退溫函數(shù)、Markov鏈長(zhǎng)度和算法停止準(zhǔn)則，是直接影響算法結(jié)果的主要因素。

(1)狀態(tài)產(chǎn)生函數(shù)

狀態(tài)產(chǎn)生函數(shù)一般由產(chǎn)生新解的方式和其相對(duì)的概率分布兩部分構(gòu)成，在設(shè)計(jì)狀態(tài)產(chǎn)生函數(shù)時(shí)，應(yīng)盡可能保證新解遍布整個(gè)解空間。本文中采用隨機(jī)交換兩架已排飛機(jī)作為擾動(dòng)，產(chǎn)生新的排列方式，即新解。

(2)初溫

溫度是模擬退火算法最重要的影響因素，它對(duì)退火的方向起著決定性作用。由隨機(jī)移動(dòng)的接受準(zhǔn)則可知:初始溫度越高，產(chǎn)生高質(zhì)量解的概率就越大。本文中取初始溫度為當(dāng)前解的目標(biāo)函數(shù)值，T=f(θ)。

(3)退溫函數(shù)

通過(guò)退溫函數(shù)使每一階段的溫度值不斷更新，常用于外循環(huán)中。本文將公式Tk=αTk-1作為退溫函數(shù)，其中系數(shù)α根據(jù)已有文獻(xiàn)實(shí)驗(yàn)檢驗(yàn)，當(dāng)α=0.8時(shí)退溫效果最佳。

(4)Markov鏈長(zhǎng)度L的選取

Markov鏈長(zhǎng)度是用于內(nèi)循環(huán)時(shí)等溫條件下進(jìn)行的迭代次數(shù)。其選取原則是在衰減函數(shù)確定的前提下，使每一取值均能恢復(fù)準(zhǔn)平衡，L的取值范圍一般在[100,1000]內(nèi)，本文中迭代次數(shù)取1000。

(5)算法終止準(zhǔn)則

算法終止準(zhǔn)則用于決定算法何時(shí)結(jié)束。常用的終止準(zhǔn)則包括:設(shè)置終止溫度和迭代次數(shù)的閾值，或者當(dāng)搜索到的最優(yōu)值連續(xù)保持不變時(shí)停止搜索。本文以內(nèi)環(huán)迭代次數(shù)10作為終止準(zhǔn)則。

(6)算法步驟

Step1.設(shè)定初值。以AATCSR算法的解作為初始解，目標(biāo)函數(shù)值作為初始溫度。

Step2.計(jì)算當(dāng)前解的目標(biāo)函數(shù)值，并令溫度為冷卻進(jìn)度表中的下一個(gè)值。

Step3.進(jìn)行擾動(dòng)，得到新解并計(jì)算該解的目標(biāo)函數(shù)值。

Step4.計(jì)算新解目標(biāo)函數(shù)值與初始解目標(biāo)函數(shù)值之差，決定是否接受新解。

Step5.在該溫度下，重復(fù)擾動(dòng)。

Step6.判斷是否達(dá)到終止溫度，是則終止；否則，轉(zhuǎn)step2.

(7)算法偽代碼

以AATCSR算法的解作為初始解，計(jì)算目標(biāo)函數(shù)f(θ)

初始memory，記MO={θ,f(θ)}

設(shè)置內(nèi)外環(huán)迭代次數(shù)imax,tmax

whilec

whilei

作鄰域搜索算法，即擾動(dòng)，產(chǎn)生新解f(θ′)

ThenMO={(θ′,f(θ′))}

End if

I=i+1,c=c+1

End while

降溫T=αT

End while

Outputθ*andf(θ*)

3 計(jì)算結(jié)果分析

3.1 數(shù)據(jù)生成

在航班數(shù)據(jù)中，每架航班都有其準(zhǔn)備時(shí)間、目標(biāo)時(shí)間、截止時(shí)間、飛機(jī)型號(hào)(即重型、大型或小型)進(jìn)場(chǎng)或離場(chǎng)方式兩種，采用的數(shù)據(jù)生成方法如下：

飛機(jī)的操作類型用0/1規(guī)劃表示：0表示進(jìn)場(chǎng)航班，1表示離場(chǎng)航班。飛機(jī)類型表示方法：1表示重型，2表示中型，3表示輕型。準(zhǔn)備時(shí)間rj由規(guī)則1和規(guī)則2隨機(jī)生成：

val1=max{0，(num-1)*rand}

(11)

val2=num*rand

(12)

其中，rand是1到60之間隨機(jī)生成的整數(shù)，num在每次迭代遞增1。

目標(biāo)時(shí)間δj由式(13)確定。

(13)

截止時(shí)間dj=δj+600

(14)

最小時(shí)間間隔skj根據(jù)表1確定，大小取決于飛機(jī)類型和操作類型。

3.2 算法有效性

從相對(duì)誤差和計(jì)算時(shí)間兩方面分析了AATCSR-SA算法的有效性。如式(15)所示，通過(guò)計(jì)算算法的目標(biāo)函數(shù)值(總加權(quán)延遲)與最優(yōu)調(diào)度之間的差值，測(cè)量這些問(wèn)題的相對(duì)誤差。

(15)

其中，

f(θ*)=TWTAATCSR-SA

(16)

f(θ) =TWToptimal

(17)

平均相對(duì)誤差和平均占用CPU時(shí)間是通過(guò)對(duì)10個(gè)實(shí)例取平均值找到的。利用Ghoniem等[15]給出的混合整數(shù)規(guī)劃公式，得到最優(yōu)解。通過(guò)提出的啟發(fā)式算法計(jì)算出結(jié)果與混合整數(shù)規(guī)劃的解進(jìn)行誤差分析，結(jié)果如表2和表3所示。

表2 平均相對(duì)誤差分析

表3 平均CPU占用時(shí)間 (秒)

從計(jì)算結(jié)果可以看出，當(dāng)跑道從兩條增加到四條，航班數(shù)量從15到25架，其平均相對(duì)誤差和CPU占用時(shí)間有輕微變化，但均在可接受的范圍內(nèi)?？傮w來(lái)看，平均相對(duì)誤差在2%以內(nèi)，平均CPU占用時(shí)間在1秒內(nèi)。

4 總結(jié)

本文研究了飛機(jī)排序問(wèn)題的實(shí)際應(yīng)用，即同時(shí)考慮航班的進(jìn)離場(chǎng)并將其分配到多跑道的聯(lián)合調(diào)度問(wèn)題。在每條跑道上，要求加權(quán)延誤最小化。基于該問(wèn)題，本文提出了在可接受的時(shí)間框架內(nèi)的高質(zhì)量解決ASP問(wèn)題的方案。文中ASP問(wèn)題被建模為一個(gè)含有目標(biāo)時(shí)間、截止時(shí)間、動(dòng)態(tài)準(zhǔn)備時(shí)間，以最小化總加權(quán)延遲成本為目標(biāo)函數(shù)的平行機(jī)器調(diào)度問(wèn)題。該問(wèn)題的混合整數(shù)規(guī)劃模型是可行的，但對(duì)于較大的問(wèn)題規(guī)模，混合整數(shù)規(guī)劃是沒(méi)辦法實(shí)現(xiàn)的。同時(shí)由于ASP問(wèn)題是NP-hard的，因此有必要在合理的計(jì)算時(shí)間內(nèi)開(kāi)發(fā)和實(shí)現(xiàn)新的解決方案。為了快速求解，本文提出一種新的組合調(diào)度規(guī)則AATCSR-SA的元啟發(fā)式算法，可以高效解決該問(wèn)題，并通過(guò)將該方法得到的解與最優(yōu)解進(jìn)行比較，得出平均相對(duì)誤差，對(duì)算法的有效性進(jìn)行了驗(yàn)證，因此該算法可以高效解決ASP問(wèn)題。