馬衛(wèi)民,楊文娟,徐 博

(1.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院,上海200092;2.上海理工大學(xué)管理學(xué)院,上海200093)

1 引 言

隨著民航產(chǎn)業(yè)的迅速發(fā)展,空中交通流量顯著增加.機(jī)場(chǎng)跑道作為進(jìn)離港交通流量的瓶頸,其擁堵現(xiàn)象也越來(lái)越嚴(yán)重.研究終端區(qū)到達(dá)和起飛飛機(jī)的合理排序,能夠有效提高跑道容量及其利用率,從而改善跑道擁堵現(xiàn)象,并極大提高航空運(yùn)輸系統(tǒng)的運(yùn)行效率.

傳統(tǒng)的研究多將起飛和著陸飛機(jī)排序看作獨(dú)立的過(guò)程.對(duì)于起飛飛機(jī)排序問(wèn)題,Trivizas[1]較早的用動(dòng)態(tài)規(guī)劃的方法對(duì)其進(jìn)行求解.隨后,Anagnostakis等[2]對(duì)起飛飛機(jī)排序問(wèn)題進(jìn)行分析并提出兩階段起飛計(jì)劃.在國(guó)內(nèi),王來(lái)軍等[3]用遺傳算法對(duì)離港航班進(jìn)行了調(diào)度優(yōu)化.相對(duì)于起飛飛機(jī)排序問(wèn)題,更多的學(xué)者致力于著陸飛機(jī)排序問(wèn)題的研究,并提出了很多優(yōu)化方法.其中,Dear等[4]較早的用受限位移約束策略(CPS)研究了靜態(tài)飛機(jī)著陸排序問(wèn)題.隨后,許多學(xué)者在CPS策略下設(shè)計(jì)不同的算法,并取得不錯(cuò)的研究成果[5,6].此外,為提高求解效率,各類啟發(fā)式算法也相繼被用來(lái)求解飛機(jī)著陸調(diào)度問(wèn)題[7,8].其中,用蟻群算法求解飛機(jī)著陸調(diào)度問(wèn)題已取得了較為成熟的結(jié)果.蟻群算法由意大利學(xué)者Dorigo[9]提出,是一種高效的啟發(fā)式算法,且被廣泛應(yīng)用于求解各類優(yōu)化問(wèn)題[10,11].Randall[12]第一次將蟻群算法應(yīng)用于飛機(jī)著陸調(diào)度問(wèn)題的求解.隨后,Bencheikh等[13]利用蟻群算法去生成最初的解來(lái)處理單跑道和多跑道的飛機(jī)調(diào)度問(wèn)題.較近的研究成果是Zhan等[14]結(jié)合滾動(dòng)時(shí)域控制原理用蟻群算法研究了機(jī)場(chǎng)實(shí)時(shí)跑道調(diào)度問(wèn)題.

以上的研究均是單獨(dú)考慮起飛或著陸飛機(jī)排序問(wèn)題.然而,近年來(lái),為了進(jìn)一步提高跑道利用率,越來(lái)越多的機(jī)場(chǎng)采用混合起降跑道.但關(guān)于混合起降飛機(jī)排序的研究成果則相對(duì)較少.在國(guó)外,主要有Ghoniem等[15]建立關(guān)于起降飛機(jī)排序問(wèn)題的加強(qiáng)型模型,并用分支定界算法求解.Hancerliogullari等[16]將多跑道混合起降飛機(jī)排序問(wèn)題看成具有不同準(zhǔn)備時(shí)間、目標(biāo)時(shí)間和截止時(shí)間的平行機(jī)調(diào)度問(wèn)題,并提出求解該問(wèn)題的貪婪算法和啟發(fā)式算法.在國(guó)內(nèi),胡俊等[17]以最大航班流量為決策目標(biāo),建立了進(jìn)離港航班容量模型,采用離散時(shí)間混合排隊(duì)算法求解.但上述研究均未考慮到在混合起降隊(duì)列中,著陸飛機(jī)延誤所帶來(lái)的損失遠(yuǎn)遠(yuǎn)大于起飛飛機(jī),即并未給與著陸飛機(jī)一定的優(yōu)先性.

鑒于上述分析,本文提出兩種基于著陸優(yōu)先的兩階段算法(TPLP算法和M-TPLP算法)來(lái)解決單跑道混合起降飛機(jī)排序問(wèn)題.首先,研究混合起降飛機(jī)排序問(wèn)題,能夠進(jìn)一步節(jié)約跑道資源并提高其利用率;其次,考慮到著陸隊(duì)列延誤所帶來(lái)的損失遠(yuǎn)遠(yuǎn)大于起飛隊(duì)列,TPLP算法和M-TPLP算法均給與了著陸隊(duì)列一定的優(yōu)先性,這在一定程度上能夠?yàn)閷?shí)際的空中交通流量管理提供理論依據(jù).再次,本文考慮了起飛—起飛、起飛—著陸、著陸—起飛、著陸—著陸四種時(shí)間間隔,更為全面的設(shè)置了起降飛機(jī)排序問(wèn)題的約束條件,使調(diào)度更加符合實(shí)際.文章最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了本文所提出的兩種算法能夠在確保著陸優(yōu)先性的前提下,有效減少起降隊(duì)列的隊(duì)列完成時(shí)間,從而能夠在一定程度上提高跑道的運(yùn)行效率,減少跑道擁堵現(xiàn)象.

2 單跑道起降飛機(jī)排序問(wèn)題模型

2.1 起降飛機(jī)排序模型

飛機(jī)排序問(wèn)題是指對(duì)于給定的著陸/起飛飛機(jī),怎樣排序使隊(duì)列完成時(shí)間(makespan)最小,也就是最后一架飛機(jī)的著陸/起飛時(shí)間最小.本文提出著陸優(yōu)先的兩階段起降飛機(jī)排序模型.即在第一階段對(duì)著陸飛機(jī)進(jìn)行排序,并給出排序后每架飛機(jī)的著陸時(shí)間.在第二階段，通過(guò)插入算法,將起飛隊(duì)列插入到著陸隊(duì)列中,使得插入后的隊(duì)列仍滿足最小時(shí)間間隔,并計(jì)算每架飛機(jī)的起飛時(shí)間.

值得注意的是,在混合起降隊(duì)列中,任意一架著陸與起飛飛機(jī)之間的最小時(shí)間間隔S(最大值為40,其中,著陸飛機(jī)在前)小于任意兩架起飛飛機(jī)之間的S(最小值為60)(見(jiàn)表1).故對(duì)于任意的著陸飛機(jī)i后緊隨兩架起飛飛機(jī)(j和k)的情形,必有Si,k＜Sj,k,且Ti＜Tj,其中Si,k為飛機(jī)i和k的最小時(shí)間間隔(i在前,k在后),T為調(diào)度后的著陸/起飛時(shí)間.因此不等式Ti+Si,k＜Tj+Sj,k恒成立,即若起飛飛機(jī)的緊前飛機(jī)為著陸飛機(jī),則不僅需要考慮與該架著陸飛機(jī)的最小時(shí)間間隔,亦需要考慮與其不相鄰的前一架起飛飛機(jī)的最小時(shí)間間隔;若起飛飛機(jī)的緊前飛機(jī)為起飛飛機(jī),則只需考慮與其緊前飛機(jī)的最小時(shí)間間隔.

混合起降飛機(jī)排序的具體模型描述如下.

假設(shè)有n架飛機(jī)等待著陸或起飛,其中包括n1架著陸飛機(jī)和n2架起飛飛機(jī).首先將其分離為著陸隊(duì)列和起飛隊(duì)列,且均按照最早著陸/起飛時(shí)間的先后進(jìn)行排序(FCFS).

對(duì)于著陸隊(duì)列,用蟻群算法進(jìn)行排序.假設(shè)調(diào)度后的著陸飛機(jī)排序隊(duì)列為ψ,令ψi為隊(duì)列中的第i架著陸飛機(jī),ATψi為飛機(jī)ψi的調(diào)度后著陸時(shí)間,它可以由下式得出,即

其中Eψi為飛機(jī)ψi的最早著陸時(shí)間,Sψi-1,ψi為飛機(jī)ψi-1與ψi的最小時(shí)間間隔,其主要由飛機(jī)ψi-1與ψi的類型決定.

對(duì)于起飛隊(duì)列,按最早開(kāi)始時(shí)間的先后排序,記為序列ξ.令ξj為隊(duì)列ξ中的第j架起飛飛機(jī),DTξj為飛機(jī)ξj的調(diào)度后起飛時(shí)間.存在以下幾種情況.

1)若起飛飛機(jī)ξ1,ξ2,...,ξm1在飛機(jī)ψ1之前起飛,則有

2)若飛機(jī)ξk,ξk+1,...,ξk+m2在飛機(jī)ψi和飛機(jī)ψi+1之間起飛,則有

3)若飛機(jī)ξγ,ξγ+1,...,ξn2在飛機(jī)ψn1之后起飛,其中ψn1為著陸隊(duì)列ψ中的最后一架飛機(jī),ξn2為起飛隊(duì)列ξ中的最后一架飛機(jī),則有

若最后一架起飛飛機(jī)ξn2在飛機(jī)ψn1之前起飛,則整個(gè)起降飛機(jī)的隊(duì)列完成時(shí)間為ATψn1;若飛機(jī)ξn2在飛機(jī)ψn1之后起飛,則起降飛機(jī)的隊(duì)列完成時(shí)間為DTξn2.因此混合起降飛機(jī)的隊(duì)列完成時(shí)間為

故混合起降飛機(jī)排序問(wèn)題的優(yōu)化目標(biāo)即為尋找一個(gè)最優(yōu)隊(duì)列,使隊(duì)列完成時(shí)間最小,即

2.2 起降飛機(jī)排序問(wèn)題滿足的約束條件

1)時(shí)間窗約束

時(shí)間窗約束即為對(duì)于任一架飛機(jī)i,其調(diào)度后的著陸/起飛時(shí)間必須在[Ei,Li]之間,這使得起降飛機(jī)排序問(wèn)題更加符合實(shí)際.具體來(lái)說(shuō),對(duì)于著陸飛機(jī)ψi和起飛飛機(jī)ξj分別有

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

為飛機(jī)制定最小時(shí)間間隔是為了避免飛機(jī)產(chǎn)生的尾渦流對(duì)后機(jī)的影響,由于不同類型的飛機(jī)產(chǎn)生和抵抗尾渦流的能力不同,因此需要根據(jù)飛機(jī)類型制定最小時(shí)間間隔約束(如表1所示).需要注意的是,對(duì)于分離的著陸飛機(jī)隊(duì)列或者起飛飛機(jī)隊(duì)列,任意三架飛機(jī)的最小時(shí)間間隔滿足三角不等式約束,即Si,k+Sk,j＞Si,j.但對(duì)于混合起降飛機(jī)隊(duì)列,則不一定滿足三角不等式.如一架H型起飛飛機(jī)(HD)前一架和后一架相鄰飛機(jī)均為H型著陸飛機(jī)(HA).該H型起飛飛機(jī)與在其之前的H型著陸飛機(jī)所應(yīng)該滿足的時(shí)間間隔為40s,與之后的H型著陸飛機(jī)應(yīng)該滿足的時(shí)間間隔為50s,而兩架H型著陸飛機(jī)應(yīng)該滿足的時(shí)間間隔為99s.易知,40+50＜99,故不滿足三角不等式約束.因此,對(duì)于每架飛機(jī),不僅要考慮其與相鄰的前一架飛機(jī)的最小時(shí)間間隔,也考慮與其不相鄰的前一架運(yùn)行方式相同(著陸/起飛)的飛機(jī)的最小時(shí)間間隔.

表1 起降飛機(jī)尾渦流間隔標(biāo)準(zhǔn)(s)[16]Table 1 Minimize separation times(seconds)

3)最大移動(dòng)位置約束(MPS)

對(duì)于著陸飛機(jī)的調(diào)度,本文考慮MPS約束,即每架飛機(jī)在調(diào)度時(shí)相對(duì)于其在FCFS中的位置最多向前或向后偏移MPS個(gè)位置.MPS約束在一定程度上確保了調(diào)度的公平性.

3 著陸優(yōu)先的兩階段算法設(shè)計(jì)

為解決混合起降飛機(jī)的調(diào)度問(wèn)題,本文提出兩種著陸優(yōu)先的兩階段算法,即TPLP算法和M-TPLP算法.具體設(shè)計(jì)思路如下.

在第一階段,該兩種算法均是將著陸飛機(jī)與起飛飛機(jī)分離,并首先對(duì)著陸隊(duì)列進(jìn)行排序,這主要是考慮到著陸隊(duì)列整體的優(yōu)先性.對(duì)于著陸隊(duì)列,考慮最小時(shí)間間隔、時(shí)間窗、MPS等約束,用蟻群算法進(jìn)行排序,得出最優(yōu)或近似最優(yōu)的著陸隊(duì)列以及每架著陸飛機(jī)的實(shí)際著陸時(shí)間.在第二階段,TPLP算法以不改變已安排的著陸飛機(jī)次序以及著陸時(shí)間為原則,將起飛飛機(jī)按照FCFS順序依次插入到已排的著陸隊(duì)列中.M-TPLP算法引入比較參數(shù)M,若將一架起飛飛機(jī)插入兩架相鄰的著陸飛機(jī)時(shí),引起后一架著陸飛機(jī)后移的時(shí)間小于等于M,則將該起飛飛機(jī)插入這兩架著陸飛機(jī)中,并調(diào)整其后的所有著陸飛機(jī)的著陸時(shí)間.TPLP和M-TPLP算法在不同程度上確保了著陸飛機(jī)的優(yōu)先性,可以較好的應(yīng)用于現(xiàn)實(shí)的空中交通管理系統(tǒng)中.

3.1 著陸飛機(jī)的排序算法—蟻群算法

對(duì)于著陸飛機(jī)的排序問(wèn)題,本文用蟻群算法進(jìn)行求解.首先按最早著陸時(shí)間的先后對(duì)著陸飛機(jī)進(jìn)行排序,依次標(biāo)記為1,2,...,n1.考慮到MPS約束,算法開(kāi)始時(shí)首先列出在調(diào)度過(guò)程中每個(gè)位置所能安排的飛機(jī)集.其中,位置P上可能安排的飛機(jī)集為Λ(P)={x|max(1,P-MPS)≤x≤min(P+MPS,n1),x為正整數(shù)}.如本文考慮MPS=2,n1=6,則位置2可能安排的飛機(jī)集為{1,2,3,4}.參考文獻(xiàn)[14],蟻群算法的具體描述如下.

步驟1初始化.令迭代次數(shù)gen=0,設(shè)定最大的迭代次數(shù)NG-max,螞蟻總數(shù)m,取定參數(shù)α,β,ρ.令各待著陸飛機(jī)(i,j)之間的初始信息素為τij=1,且初始時(shí)刻Δτij=0;初始隊(duì)列完成時(shí)間充分大.禁忌表Tabum表示螞蟻m所對(duì)應(yīng)的飛機(jī)排序組合,且初始時(shí)Tabum=?.

步驟2讓m只螞蟻分別在Λ(1)中隨機(jī)選擇一架飛機(jī)作為待著陸飛機(jī),并將其移入每只螞蟻對(duì)應(yīng)的禁忌表中.按照每個(gè)位置可能的飛機(jī)分配和狀態(tài)轉(zhuǎn)移概率公式(9)選擇下一個(gè)位置的待著陸飛機(jī).

其中ηij為啟發(fā)信息,是指在安排飛機(jī)i著陸后直接安排飛機(jī)j著陸的期望度,本文取ηij=1/Si,j.allowedm為螞蟻m下一步允許選擇的飛機(jī)集合;α為信息素重要程度參數(shù);β為啟發(fā)信息重要程度參數(shù);p為0到1之間的隨機(jī)數(shù).隨機(jī)數(shù)p的引入可以避免過(guò)早陷入局部最優(yōu)解.

由上文知,當(dāng)螞蟻進(jìn)入位置P,P＞MPS時(shí),allowedm={x|x∈Λ(P),且Tabum}.檢查飛機(jī)(P-MPS)是否已被訪問(wèn).若(P-MPS)∈allowedm,即飛機(jī)(P-MPS)未被訪問(wèn),則在位置P直接訪問(wèn)該飛機(jī);否則,依據(jù)狀態(tài)轉(zhuǎn)移概率公式(9)選擇該位置的待著陸飛機(jī),并將該飛機(jī)移入禁忌表Tabum中,然后進(jìn)入下一位置的飛機(jī)選擇.

步驟3檢查每只螞蟻的Tabu,即為一個(gè)飛機(jī)排序組合,并按公式(1)計(jì)算該組合中每架飛機(jī)的著陸時(shí)間,從而得出每只螞蟻所選擇序列的隊(duì)列完成時(shí)間(makespan).找出本次循環(huán)中最小的makespan,記為ATmin,對(duì)應(yīng)的飛機(jī)排序組合為Tabumin.若ATmin＜ATmax,則ATmin=ATmax,否則ATmax不變.

步驟4更新信息素.

選擇信息素蟻群同步更新方式,即在m只螞蟻完成各自的飛機(jī)排序后,對(duì)信息素統(tǒng)一進(jìn)行更新.令τij(n)為第n次循環(huán)后的信息素量,則

其中ρ∈(0,1)為信息素?fù)]發(fā)系數(shù);為第k只螞蟻在本次循環(huán)中留在路徑i→j上的信息素增量.根據(jù)Dorigo的Ant-Cycle模型,可得

其中Q為信息素強(qiáng)度,為常數(shù),在算法初始化時(shí)設(shè)定;ATmin表示m只螞蟻在本次循環(huán)中所得到的最小的隊(duì)列完成時(shí)間(makespan),這種更新方法可以保證信息素不至于無(wú)限積累.

步驟5gen←gen+1,如果gen＜NGmax,清空禁忌表,轉(zhuǎn)步驟2;否則循環(huán)結(jié)束,輸出計(jì)算結(jié)果.

3.2 起飛飛機(jī)的排序算法—插入算法

假設(shè)3.1中第一階段優(yōu)化后的著陸隊(duì)列為ψ,令ψi為隊(duì)列ψ中的第i架著陸飛機(jī)(i=1,2,...,n1),ATψi為飛機(jī)ψi的已排著陸時(shí)間.對(duì)于余下的起飛飛機(jī),按照最早起飛時(shí)間的先后順序進(jìn)行排序,記為序列ξ.令ξj為隊(duì)列ξ中的第j架起飛飛機(jī)(j=1,2,...,n2),Eξj和Lξj分別為飛機(jī)ξj的最早起飛時(shí)間和最遲起飛時(shí)間.

初始時(shí),令待安排起飛飛機(jī)集合為U={ξ1,ξ2,...,ξn2},已排好的起飛飛機(jī)集合為I= ?.下面分別介紹TPLP算法和M-TPLP算法的第二階段的求解算法.

1)TPLP算法—不改變已排著陸飛機(jī)的著陸時(shí)間

步驟1選出可以在第一架著陸飛機(jī)ψ1之前起飛的飛機(jī).

(a)依次比較各起飛飛機(jī)的最早起飛時(shí)間Eξj與ATψ1的大小,記Eξj小于ATψ1的飛機(jī)集合為Θψ1.

(b)若Θψ1為空集,即各起飛飛機(jī)的最早起飛時(shí)間均大于ATψ1,則無(wú)法在飛機(jī)ψ1之前安排起飛飛機(jī),直接轉(zhuǎn)入步驟2.否則,按式(2)計(jì)算相應(yīng)的起飛時(shí)間DTξj(ξj∈Θψ1).

(c)依次判斷DTξj與ATψ1是否滿足最小時(shí)間間隔約束.若滿足,則放入已排起飛飛機(jī)集合I中,否則,轉(zhuǎn)步驟2.

步驟2在未安排的起飛隊(duì)列U中依次選擇能放入著陸飛機(jī)ψi與ψi+1之間的起飛飛機(jī)(i=1,2,...,n1-1).

(a)首先,令i=1.

(b)對(duì)于著陸飛機(jī)ψi與ψi+1之間.在未安排的起飛隊(duì)列U中,依次選擇最早起飛時(shí)間小于ATψi+1的起飛飛機(jī),記最早起飛時(shí)間小于ATψi+1的飛機(jī)集合為Θψi+1.

(c)若Θψi+1為空集,令i←i+1,轉(zhuǎn)入步驟(b);否則,按照公式(3)計(jì)算DTξj(ξj∈Θψi+1).

(d)依次判斷DTξj與ATψi+1是否滿足最小時(shí)間間隔約束.若滿足,則放入已排起飛飛機(jī)集合I中;若不滿足,亦令i←i+1,轉(zhuǎn)入步驟(b).依次類推,直至完成能在飛機(jī)ψn1之前起飛的飛機(jī)隊(duì)列的排序.

步驟3選擇在飛機(jī)ψn1之后起飛的飛機(jī),并計(jì)算起降隊(duì)列完成時(shí)間.

(a)若在步驟2之后,U=?,則完成調(diào)度,且起降飛機(jī)的隊(duì)列完成時(shí)間T=ATψn1.

(b)若?,對(duì)于余下的未安排飛機(jī),按照公式(4)計(jì)算相應(yīng)的DTξ(j).至此,完成所有起降飛機(jī)的排序,且起降飛機(jī)的隊(duì)列完成時(shí)間T=DTξn2.

2)M-TPLP算法—允許改變已排著陸飛機(jī)的著陸時(shí)間

M-TPLP算法是對(duì)TPLP算法的改進(jìn),引入比較參數(shù)M來(lái)控制著陸飛機(jī)的已安排著陸時(shí)間所允許變化的范圍.其主要的設(shè)計(jì)思路如下.

在已安排著陸飛機(jī)ψi與ψi+1之間,令集合R表示最早起飛時(shí)間早于ATψi+1但與飛機(jī)ψi+1并不滿足最小時(shí)間間隔約束的集合.假設(shè)起飛飛機(jī)ξk為R中的第一架飛機(jī),上述的TPLP算法是直接進(jìn)入ψi+1與ψi+2之間的起飛飛機(jī)的選擇.而M-TPLP算法是設(shè)置比較參數(shù)M,若DTξk+Sξk,ψi+1-ATψi+1≤M.也就是說(shuō),插入飛機(jī)ξk所引起后一架著陸飛機(jī)的后移時(shí)間小于等于M,則可以將飛機(jī)ξk放入ψi與ψi+1之間,并將飛機(jī)ψi+1至最后一架著陸飛機(jī)的已排著陸時(shí)間均后移Δt,其中Δt=DTξk+Sξk,ψi+1-ATψi+1.M-TPLP算法從一定程度上改善了將大量的起飛飛機(jī)后移的情形,使調(diào)度更具有靈活性.具體的步驟如下.

步驟1選出可以在第一架著陸飛機(jī)ψ1之前起飛的飛機(jī).其中,步驟(a)和(b)同TPLP算法步驟1中的(a)和(b).

(c)依次判斷DTξj與ATψ1是否滿足最小時(shí)間間隔約束.若滿足,則放入已排起飛飛機(jī)集合I中,并轉(zhuǎn)入步驟2;否則,記不滿足約束的飛機(jī)集合為Rψ1,易知,Rψ1={ξj|Eψj＜ATψ1且DTξj+Sξj,ψ1＞ATψ1}.

(d)判斷若將Rψ1中的第一架飛機(jī)安排在飛機(jī)ψ1之前,所引起飛機(jī)ψ1后移的時(shí)間與參數(shù)M的大小關(guān)系.若小于等于M,則將其安排在飛機(jī)ψ1之前,即移入集合I中,并轉(zhuǎn)入步驟2;否則,直接轉(zhuǎn)入步驟2.

步驟2在未安排的起飛隊(duì)列U中依次選擇能放入著陸飛機(jī)ψi與ψi+1之間的起飛飛機(jī)(i=1,2,...,n1-1).其中,步驟(a)到(c)同TPLP算法步驟2中的(a)到(c).

(d)依次判斷DTξj與ATψi+1是否滿足最小時(shí)間間隔約束.若滿足,則放入已排起飛飛機(jī)集合I中;否則,記不滿足約束的飛機(jī)集合為Rψi+1,其中,Rψi+1={ξj|Eψj＜ATψi+1且DTξj+Sξj,ψi+1＞ATψi+1}.

(e)判斷若將Rψi+1中的第一架飛機(jī)安排在飛機(jī)ψi+1之前,所引起飛機(jī)ψi+1后移的時(shí)間與參數(shù)M的大小關(guān)系.若小于等于M,則將其安排在飛機(jī)ψi+1之前,即移入集合I中,并令i←i+1,轉(zhuǎn)入步驟(b);否則,直接令i←i+1,轉(zhuǎn)入步驟(b).依次類推,直至完成能在飛機(jī)ψn1之前起飛的飛機(jī)隊(duì)列的排序.

步驟3同TPLP算法的步驟3.

4 算例仿真

為更好的對(duì)上述算法進(jìn)行解釋,本文首先給出一個(gè)具體的算例,如圖1所示.給定10架待排序飛機(jī),其中包括5架起飛飛機(jī)和5架著陸飛機(jī),并給出各架飛機(jī)的最早起飛和著陸時(shí)間,如圖1(a)所示.其中,每個(gè)箭線分別代表一架飛機(jī),箭頭向下(上)代表起飛(著陸)飛機(jī),其上方(下方)的標(biāo)注分別代表在初始隊(duì)列中的順序、最早開(kāi)始時(shí)間以及飛機(jī)種類.如第二條向下的箭線III,表示起降隊(duì)列中的第3架飛機(jī),其最早起飛時(shí)間為254,飛機(jī)種類為HD.

若用FCFS算法進(jìn)行排序,則只需令各架飛機(jī)之間滿足最小時(shí)間間隔約束.可以得出圖1(b)所示計(jì)算結(jié)果.

下面介紹TPLP算法和M-TPLP算法的求解過(guò)程.首先,將著陸隊(duì)列單獨(dú)列出,并先用蟻群算法進(jìn)行排序.可得出圖1(c)所示結(jié)果.

對(duì)于TPLP算法,首先選擇可以在著陸飛機(jī)II之前起飛的飛機(jī).易知,飛機(jī)II的著陸時(shí)間為95,而最早起飛時(shí)間小于95的僅有飛機(jī)I,則判斷能否將飛機(jī)I安排在飛機(jī)II之前起飛.飛機(jī)I的最早起飛時(shí)間EII=86,但飛機(jī)I與飛機(jī)II之間的最小時(shí)間間隔SI,I=53(表1中HD和LA的最小時(shí)間間隔為53,其中HD在前,LA在后).顯然,不滿足最小時(shí)間間隔約束,無(wú)法安排在飛機(jī)II之前起飛.

再次,選擇可以在飛機(jī)II和V之間起飛的飛機(jī).易知,飛機(jī)I、III和IV的最早起飛時(shí)間小于飛機(jī)V的著陸時(shí)間(476),則依次判斷這3架能否安排在飛機(jī)V之前.對(duì)于飛機(jī)I,首先假設(shè)將其安排在II和V之間,則其起飛時(shí)間DTI=max{86,95+35}=130,其中35為飛機(jī)II和飛機(jī)I的最小時(shí)間間隔.再判斷飛機(jī)I和飛機(jī)V能否滿足最小時(shí)間間隔約束.易知,SI,V=65,且130+65＜476,故可以將I放在II和V之間起飛;對(duì)于飛機(jī)III,亦先假設(shè)將其放在I和V之間,則有DTII=max{254,130+60}=254,且SIII,V=65.因此有DTII+SIII,V=254+65=319＜476,故可以將飛機(jī)III安排在飛機(jī)I之后.以此類推,直至將所有的起飛飛機(jī)都安排完.可以得到如圖1(d)所示結(jié)果.

對(duì)于M-TPLP算法,設(shè)定參數(shù)M=20,對(duì)于起飛飛機(jī)I、III和IV的安排同TPLP算法.由于飛機(jī)IX的最早開(kāi)始時(shí)間大于飛機(jī)VIII的著陸時(shí)間(576＞575),故直接進(jìn)入飛機(jī)VIII和VI中起飛飛機(jī)的選擇.易知,飛機(jī)IX和X的最早起飛時(shí)間均小于飛機(jī)VI的著陸時(shí)間.對(duì)于飛機(jī)IX,假設(shè)將其安排在飛機(jī)VIII之后,則有DTIX=max{576,575+30}=605.又SIX,VI=50,有DTIX+SIX,VI=605+50=655＞649,但由于655-649=6＜20=M,故允許將其放入飛機(jī)VIII和VI之間,同時(shí)將飛機(jī)VI和VII后移6,即ATVI變?yōu)?55,ATVII變?yōu)?54.然后進(jìn)入飛機(jī)VI和VII之間的選擇.直至安排完

圖1 算例分析Fig.1 Analysis of an example

進(jìn)一步,為檢驗(yàn)TPLP算法和M-TPLP算法的有效性,本文將該兩種算法與FCFS算法相比較.考慮到起降飛機(jī)需要滿足的最小時(shí)間間隔與分離的著陸或起飛調(diào)度相比更為復(fù)雜,本文參照文獻(xiàn)[16]對(duì)傳統(tǒng)的FCFS算法進(jìn)行改進(jìn).假設(shè)有n架飛機(jī)等待起飛/著陸,按照最早開(kāi)始時(shí)間的先后分別標(biāo)注為1,2,...,n,則隊(duì)列完成時(shí)間計(jì)算如下：

其中Ei為飛機(jī)i的最早開(kāi)始時(shí)間,Si,j為飛機(jī)(i,j)的最小時(shí)間間隔.Ti為飛機(jī)i排序后的實(shí)際著陸/起飛時(shí)間.

表2 FCFS、TPLP算法和M-TPLP算法得到的排序結(jié)果Table 2 Computational results for FCFS,TPLP and M-TPLP

4.1 初始數(shù)據(jù)的生成與蟻群算法參數(shù)的選取

數(shù)據(jù)生成方面,本文參考文獻(xiàn)[16].用1,2,3,4,5,6分別代表H型著陸飛機(jī)、L型著陸飛機(jī)、S型著陸飛機(jī)、H型起飛飛機(jī)、L型起飛飛機(jī)和S型起飛飛機(jī),6種類型的飛機(jī)隨機(jī)產(chǎn)生,起飛飛機(jī)和著陸飛機(jī)的數(shù)量各占50%,且H型、L型、S型的飛機(jī)分別占50%、30%、20%.最早開(kāi)始時(shí)間Ei隨機(jī)產(chǎn)生,且服從[0,65n]區(qū)間上的離散均勻分布.最晚開(kāi)始時(shí)間設(shè)定為最早開(kāi)始時(shí)間之后的60 min.此外,第一階段蟻群算法選取的參數(shù)分別為α=1;β=5;ρ=0.1;Q=100;m=150;NCmax=100.

4.2 實(shí)驗(yàn)結(jié)果分析

表2列出了40架起降飛機(jī)在FCFS算法、TPLP算法和M-TPLP算法計(jì)算下所得到的排序結(jié)果(其中,令M=20).易知,FCFS得到的隊(duì)列完成時(shí)間(makespan)為2 934s,TPLP算法得到的makespan為2 587s,M-TPLP算法得到的makespan為2 510s.即TPLP算法和M-TPLP算法求解的makespan與FCFS算法相比分別減少了11.83%和14.45%.說(shuō)明這兩種算法對(duì)于減少起降飛機(jī)的隊(duì)列完成時(shí)間、提高跑道利用率具有較高的求解質(zhì)量.

為進(jìn)一步驗(yàn)證表2中求解結(jié)果的有效性,本文對(duì)表2中的初始數(shù)據(jù)進(jìn)行了50次測(cè)算,并給出最差解、最優(yōu)解和平均值,如表3所示.可以看出,經(jīng)過(guò)多次測(cè)試,TPLP算法求得的平均解為2 648s,M-TPLP算法求得的平均解為2 542s.相比較FCFS算法,隊(duì)列完成時(shí)間分別減少了9.75%和13.36%,且該兩種算法均在12s內(nèi)完成了40架起降飛機(jī)的排序.從而進(jìn)一步驗(yàn)證了上述結(jié)論的正確性.

為了驗(yàn)證該算法在求解規(guī)模較大(起降飛機(jī)數(shù)量較多)時(shí)仍具有較好的求解效果,本文以20為步距,選取10組起降飛機(jī)序列(20架～200架飛機(jī)),并與FCFS算法進(jìn)行比較.如表4所示,TPLP算法求解的隊(duì)列完成時(shí)間相比較FCFS算法減少了5%～13%,M-TPLP算法求解的隊(duì)列完成時(shí)間減少了10%～17%,且均在60s完成了200架起降飛機(jī)的計(jì)算.可見(jiàn),大量的數(shù)值模擬試驗(yàn)仍表明該算法能夠較為有效的減少混合起降飛機(jī)的隊(duì)列完成時(shí)間,從而在一定程度上提高跑道的運(yùn)行效率.

此外,作者對(duì)參數(shù)M的選取也進(jìn)行了多次測(cè)試.圖2分別表示當(dāng)飛機(jī)數(shù)目n=80和n=160,M取10～100時(shí)(間距為10)的三次實(shí)驗(yàn)結(jié)果.可以看出,當(dāng)取20～40時(shí),M-TPLP算法取得的結(jié)果更優(yōu).故本文中M-TPLP算法的多次實(shí)驗(yàn)均令參數(shù)M=20.

表3 算例中TPLP算法和M-TPLP算法的求解效果Table 3 Solution quality of TPLP and M-TPLP

表4 FCFS、TPLP算法和M-TPLP算法的隊(duì)列完成時(shí)間的比較Table 4 Comparisons between FCFS,TPLP and M-TPLP

圖2 M-TPLP算法中參數(shù)M的影響Fig.2 Inf l uence of the parameters M on M-TPLP

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

本文為提高機(jī)場(chǎng)跑道的利用率和運(yùn)行效率,對(duì)單跑道混合起降飛機(jī)的排序問(wèn)題進(jìn)行了研究.首先,建立基于著陸優(yōu)先的起降飛機(jī)排序模型.該模型考慮了著陸隊(duì)列的優(yōu)先性以及混合起降隊(duì)列的最小時(shí)間間隔的復(fù)雜性,并設(shè)置更加全面的約束條件.其次,考慮到現(xiàn)實(shí)空管中著陸飛機(jī)延誤所帶來(lái)的損失遠(yuǎn)遠(yuǎn)大于起飛飛機(jī),本文提出兩種著陸優(yōu)先的兩階段算法,即TPLP算法和M-TPLP算法.該兩種算法給與了著陸飛機(jī)不同的優(yōu)先性,使調(diào)度更加符合現(xiàn)實(shí)空管的要求.最后,通過(guò)大量的仿真實(shí)驗(yàn)驗(yàn)證本文所提出的算法能有效的減少混合起降飛機(jī)的隊(duì)列完成時(shí)間,從而能夠在一定程度上提高機(jī)場(chǎng)跑道的運(yùn)行效率.

參考文獻(xiàn):

[1]Trivizas D A.Optimal scheduling with maximum position shift(mps)constraints：A runway scheduling application.Journal of Navigation,1998,51(2)：250—266.

[2]Anagnostakis I,Clarke J P.Runway operations planning,a two-stage heuristic algorithm.Los Angeles：AIAA Aircraft,Technology,Integration and Operations Forum,2002.

[3]王來(lái)軍,史忠科.航班離場(chǎng)排序問(wèn)題的遺傳算法設(shè)計(jì).系統(tǒng)工程理論與實(shí)踐,2005,25(9)：119—125.Wang L J,Shi Z K.The implement of genetic algorithms in departure sequencing problem.Systems Engineering：Theory&Practice,1999,36(3)：84—87.(in Chinese)

[4]Dear R G.The dynamic scheduling of aircraft in the near terminal area.MIT Flight Transportation Report R76—9,Cambridge：Massachusetts Institute of Technology,1976.

[5]Psaraftis H N.A dynamic programming approach for sequencing groups of identical jobs.Operations Research,1980,28(6)：1347—1359.

[6]Balakrishnan H,Chandran B G.Algorithms for scheduling runway operations under constrained position shifting.Operations Research,2010,58(6)：1650—1665.

[7]Hu X B,Chen W H.Genetic algorithm based on receding horizon control for arrival sequencing and scheduling.Engineering Applications of Artif i cial Intelligence,2005,6(2)：633—642.

[8]王 飛,徐肖豪,張 靜.終端區(qū)飛機(jī)排序的混合人工魚(yú)群算法.交通運(yùn)輸工程學(xué)報(bào),2008,8(3)：68-72.Wang F,Xu X H,Zhang J.Mixed artif i cial f i sh school algorithm of aircraft sequencing in terminal area.Journal of Traff i c and Transportation Engineering,2008,8(3)：68—72.(in Chinese)

[9]Dorigo M,Gambardella L M.Ant colony system：A cooperative learning approach to the traveling salesman problem.IEEE Transactions on Evolutionary Computation,1997,1(1)：53—56.

[10]胡小兵,黃席樾.基于蟻群優(yōu)化算法的0-1背包問(wèn)題求解.系統(tǒng)工程學(xué)報(bào),2005,20(5)：520—529.Hu X B,Huang X Y.Solving 0-1 knapsack problem based on ant colony optimization algorithm.Journal of Systems Engineering,2005,20(5)：520—529.(in Chinese)

[11]何小鋒,馬 良.Steiner最小樹(shù)問(wèn)題的量子蟻群算法.系統(tǒng)工程學(xué)報(bào),2012,27(4)：467—473.He X F,Ma L.A quantum-inspired ant colony algorithm for Steiner minimum tree problem.Journal of Systems Engineering,2012,27(4)：467—473.(in Chinese)

[12]Randall M C.Scheduling aircraft landings using ant colony optimisation.Proceedings of the IASTED International Conference Artif i cial Intelligence and Soft Computing,Banff：2002.

[13]Bencheikh G,Boukachour J,Alaoui A E H,et al.Hybrid method for aircraft landing scheduling based on a job shop formulation.International Journal Computer Science Network Security,2009,9(8)：78—88.

[14]Zhan Z H,Zhang J,Liu O,et al.An eff i cient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem.IEEE Transactions on Intelligent Transportation Systems,2010,11(2)：399—412.

[15]Ghoniem A,Sherali H D,Baik H.Enhanced models for a mixed arrival-departure aircraft sequencing problem.INFORMS Journal on Computing,2014,26(3)：514—530.

[16]Hancerliogullari G,Rabadi G,Al-Salem A H.Greedy algorithms and metaheuristics for a multiple runway combined arrivaldeparture aircraft sequencing problem.Journal of Air Transport Management,2013,32(6)：39—48.

[17]胡 俊,胡海波.進(jìn)離港航班容量及其影響因素.西南交通大學(xué)學(xué)報(bào)，2012,47(1)：163-168.Hu J,Hu H B.Arrival-departure capacity and its inf l uencing factors.Journal of Southwest Jiaotong University,2012,47(1)：163—168.(in Chinese)