黃 濤，郝 雅

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

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

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

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

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

1.1 問題描述

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

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ù)

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

Min∑wj(Tj-ETj)

(5)

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

wj=「M/Priorj?

(6)

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

1.2.2 約束條件

(1)最小時間間隔約束

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

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

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

(2)時間窗約束

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

ETi≤ATi≤LTi

(7)

ETj≤DTj≤LTj

(8)

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

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

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

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è)計

2.1 AATCSR算法

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

Step1.設(shè)定初值

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

Step3.定跑道。選取飛機在跑道上開始操作(起飛或著陸)時間最早的跑道。

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

偽代碼如下：

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

計算優(yōu)先級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)

更新時間表長Cmaxi(t)=tj

2.2 基于AATCSR的模擬退火算法

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

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

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

(2)初溫

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

(3)退溫函數(shù)

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

(4)Markov鏈長度L的選取

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

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

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

(6)算法步驟

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

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

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

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

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

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

(7)算法偽代碼

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

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

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

whilec

whilei

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

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

End if

I=i+1,c=c+1

End while

降溫T=αT

End while

Outputθ*andf(θ*)

3 計算結(jié)果分析

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

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

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

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

(11)

val2=num*rand

(12)

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

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

(13)

截止時間dj=δj+600

(14)

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

3.2 算法有效性

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

(15)

其中，

f(θ*)=TWTAATCSR-SA

(16)

f(θ) =TWToptimal

(17)

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

表2 平均相對誤差分析

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

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

4 總結(jié)

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