牟德一，劉金鳳

(中國(guó)民航大學(xué) 理學(xué)院，天津 300300)

0 引言

隨著航空運(yùn)輸需求日益增長(zhǎng)，飛機(jī)延誤已成普遍現(xiàn)象，并有不斷增長(zhǎng)的趨勢(shì).據(jù)美國(guó)FAA研究表明，84%的飛機(jī)延誤發(fā)生在地面，漢莎航空公司1999年由于飛機(jī)在空中等待降落而浪費(fèi)了26000 t燃料［1］.在我國(guó)的北京、上海、廣州等大型機(jī)場(chǎng)，該問(wèn)題也十分突出.飛機(jī)的地面延誤主要發(fā)生在道面滑行，高峰時(shí)刻道面滑行沖突最為嚴(yán)重.由于擴(kuò)大基礎(chǔ)設(shè)施投資昂貴且短時(shí)間內(nèi)難以實(shí)現(xiàn)，所以研究機(jī)場(chǎng)有限資源的整合優(yōu)化，提高資源的合理利用率越來(lái)越重要.為了提高飛機(jī)滑行效率，減少地面滑行的等待時(shí)間，國(guó)內(nèi)外學(xué)者做出了不同層次的研究，提出了多種解決方案.

在減少地面滑行時(shí)間，解決飛機(jī)滑行路徑?jīng)_突問(wèn)題上，一些學(xué)者試圖從兩個(gè)方面提出解決方案.一方面是為飛機(jī)確定無(wú)沖突的滑行路徑，使飛機(jī)在停機(jī)位或跑道入口無(wú)限時(shí)等待并以最優(yōu)放飛順序放飛，J-P.Gotteland［2］和 B.Pesic［3］對(duì)這方面進(jìn)行了研究，Sivakumar［4］以 Dall-Fort Worth 機(jī)場(chǎng)為例，運(yùn)用混合整數(shù)規(guī)劃進(jìn)行分析，并將此模型應(yīng)用擴(kuò)展到任意機(jī)場(chǎng)的布局.另一方面是確定更多的無(wú)沖突的滑行路徑，提供更多的無(wú)障礙路線(xiàn).本文對(duì)第一種方案進(jìn)行改進(jìn)，同時(shí)兼顧第二種方法.即分散等待時(shí)間，把第一種方法的停機(jī)位或跑道入口等待轉(zhuǎn)化為各個(gè)滑行道結(jié)點(diǎn)均可等待的新方案，這種做法在機(jī)場(chǎng)地面滑行指揮領(lǐng)域是允許的.此外，本文還采用了Floyd算法計(jì)算了多條無(wú)障礙路線(xiàn)，把最短路與理想路徑嚴(yán)格區(qū)分，實(shí)現(xiàn)必要時(shí)安排優(yōu)先級(jí)別較低的飛機(jī)按照次短路滑行，可以回避沖突，減少總調(diào)度時(shí)間，緩解機(jī)場(chǎng)地面忙碌狀態(tài).

1 飛機(jī)地面滑行調(diào)度問(wèn)題

離港飛機(jī)從停機(jī)位到跑道出口，進(jìn)港飛機(jī)從跑道入口到停機(jī)位所經(jīng)過(guò)的路線(xiàn)稱(chēng)為飛機(jī)地面滑行路徑.飛機(jī)地面滑行調(diào)度研究的主要目的是為空中交通管制員提供有效的滑行調(diào)度方案，以降低機(jī)場(chǎng)的地面滑行延誤.

由于滑行過(guò)程要受到進(jìn)離港過(guò)程給出的位置和時(shí)間上的約束，同時(shí)在龐大的滑行路徑上進(jìn)行滑行的進(jìn)離港飛機(jī)也會(huì)發(fā)生各種沖突，突出表現(xiàn)為:追尾沖突——在同一條滑行路徑上進(jìn)港和離港的兩架飛機(jī)相向滑行;相遇沖突——同一滑行路徑上進(jìn)港(或者離港)的兩架飛機(jī)同向滑行或同一結(jié)點(diǎn)處兩架飛機(jī)相遇(見(jiàn)圖1).

通常情況下的一般作法是將交叉沖突看作結(jié)點(diǎn)沖突，把相遇沖突看作滑行邊沖突，而追尾沖突既可以看作邊沖突，也可以看作點(diǎn)沖突.因?yàn)槿绻诨兴俣缺３植蛔兊那樾蜗?，若兩架飛機(jī)在滑行邊相向滑行因間距不足而產(chǎn)生追尾沖突，則在構(gòu)成該滑行邊的兩結(jié)點(diǎn)也會(huì)產(chǎn)生結(jié)點(diǎn)沖突，反之亦然.因此，本文只將沖突分為邊沖突和點(diǎn)沖突.

圖1 三種類(lèi)型相撞:交叉沖突(左)，追尾沖突(中)和相遇沖突(右)

本文假設(shè)，所有飛機(jī)的優(yōu)先級(jí)相同，即先到達(dá)結(jié)點(diǎn)先滑行原則.當(dāng)時(shí)刻相等時(shí)，進(jìn)港飛機(jī)優(yōu)先于離港飛機(jī)，主要是為了減少進(jìn)港飛機(jī)的空中等待時(shí)間，做到安全節(jié)油.

2 分散等待時(shí)間模型

為了更合理地利用機(jī)場(chǎng)滑行道資源，Sivakumar［4］與 Smeltink［5］以所有參加調(diào)度飛機(jī)的總滑行時(shí)間最短為目標(biāo):

運(yùn)用混合整數(shù)規(guī)劃為每架飛機(jī)確定理想滑行路徑，安排最優(yōu)放飛順序，讓其他飛機(jī)在停機(jī)位或跑道入口無(wú)限時(shí)等待，為每架飛機(jī)找到到達(dá)且經(jīng)過(guò)每個(gè)結(jié)點(diǎn)的時(shí)間，即.模型的目的是為每架飛機(jī)確定最短滑行路徑，安排最優(yōu)放飛順序，確立滑行的初始時(shí)刻，滑行一旦開(kāi)始滑行中途將不再停止.

固定時(shí)間段的飛機(jī)滑行時(shí)間指的是該時(shí)間段內(nèi)所有滑行飛機(jī)的滑行時(shí)間總和;而調(diào)度時(shí)間是指該時(shí)間段內(nèi)的第一架飛機(jī)開(kāi)始滑行時(shí)計(jì)時(shí)，到最后一架飛機(jī)結(jié)束滑行時(shí)為止.通常，調(diào)度時(shí)間遠(yuǎn)小于滑行時(shí)間.目前涉及飛機(jī)地面滑行路徑選擇的研究中，如文獻(xiàn)［4-5］等，大多以滑行時(shí)間最小為目標(biāo)函數(shù).顯然，只有每架飛機(jī)選擇了最短路才能達(dá)到滑行時(shí)間的絕對(duì)最短，但會(huì)導(dǎo)致多數(shù)飛機(jī)擁擠在最短路上，等待放飛.因此，從實(shí)際運(yùn)用角度這種調(diào)度策略并不一定是最佳解決方案.因此本文將調(diào)度時(shí)間最短確定為目標(biāo)函數(shù)，研究建立一種新的調(diào)度方案.

在實(shí)際的地面交通管制中，跑道出入口和滑行道的交叉點(diǎn)處是有等待線(xiàn)的(見(jiàn)圖2)，即滑行中的飛機(jī)為了避免沖突，保持相鄰飛機(jī)之間的時(shí)間間隔或距離間隔，可以在等待線(xiàn)上等待，直到?jīng)_突消失為止.如此考慮，飛機(jī)在滑行路徑的結(jié)點(diǎn)處就不再是一個(gè)固定的時(shí)刻，而很可能為一個(gè)時(shí)間段.比如，飛機(jī)在到達(dá)十字交叉結(jié)點(diǎn)后，發(fā)現(xiàn)前一個(gè)經(jīng)過(guò)飛機(jī)還不滿(mǎn)足時(shí)間間隔，就需要在結(jié)點(diǎn)處進(jìn)行等待片刻，那么該飛機(jī)在此結(jié)點(diǎn)就要經(jīng)歷一個(gè)時(shí)間段.

圖2 跑道和滑行道的等待線(xiàn)

因此本文引入兩個(gè)時(shí)刻來(lái)表示飛機(jī)到達(dá)且經(jīng)過(guò)該結(jié)點(diǎn)的時(shí)間:

下面對(duì)進(jìn)離港飛機(jī)的特殊結(jié)點(diǎn)到達(dá)和離開(kāi)時(shí)間進(jìn)行特殊說(shuō)明.

進(jìn)港飛機(jī):

第一個(gè)結(jié)點(diǎn)為滑行道入口，飛機(jī)到達(dá)該點(diǎn)的時(shí)間為飛機(jī)的進(jìn)港時(shí)刻，離開(kāi)該結(jié)點(diǎn)的時(shí)間為飛機(jī)接到指令開(kāi)始滑行的時(shí)刻.即:=飛機(jī)著落時(shí)刻，=開(kāi)始滑行的時(shí)刻;

最后一個(gè)結(jié)點(diǎn)為停機(jī)位，飛機(jī)到達(dá)該結(jié)點(diǎn)時(shí)間為實(shí)際到達(dá)時(shí)間，離開(kāi)時(shí)間為無(wú)窮大(不考慮轉(zhuǎn)機(jī)情形)，在此模型中，設(shè)置為+整個(gè)研究的時(shí)間段即可.

離港飛機(jī):

變量ziju=1表示飛機(jī)i在飛機(jī)j之前到達(dá)結(jié)點(diǎn)u，否則為0.

Tsep為滑行規(guī)定通過(guò)同一結(jié)點(diǎn)的兩架飛機(jī)的時(shí)間間隔，一般因機(jī)型不同而有所差距.

3 確定多條無(wú)障礙路徑的Floyd算法

上一節(jié)將滑行時(shí)間與調(diào)度時(shí)間區(qū)分開(kāi)，下面將理想滑行路徑與最短路徑區(qū)分開(kāi).飛機(jī)最短路徑是指地面交通網(wǎng)絡(luò)上任意起始終止點(diǎn)間存在的多條路徑中滑行距離最短或滑行時(shí)間最短的一條路徑;飛機(jī)理想滑行路徑是指在地面滑行調(diào)度中，以沖突最小，最終實(shí)現(xiàn)所有飛機(jī)調(diào)度時(shí)間最短為目標(biāo)的路徑，通常情況下是次短路.最短路徑是飛機(jī)滑行的最基本路徑，次短路徑作為補(bǔ)充部分構(gòu)成飛機(jī)滑行路徑的理想路徑.飛機(jī)只有按照理想滑行路徑在機(jī)場(chǎng)地面交通網(wǎng)絡(luò)上滑行才有助于網(wǎng)絡(luò)上運(yùn)行飛機(jī)的合理分布及網(wǎng)絡(luò)上飛機(jī)流的動(dòng)態(tài)均衡.

Floyd算法又稱(chēng)距離矩陣冪乘法.該算法在確定網(wǎng)絡(luò)上任意兩點(diǎn)之間的最短距離時(shí)，對(duì)有向和無(wú)向網(wǎng)絡(luò)都是可行的.具體算法如下［6］:

計(jì)算次數(shù)p的確定:

(1)當(dāng)wij≥0時(shí)，p由下式確定:P≥ln(n－1)/ln(2).這樣的Dp就確定了網(wǎng)絡(luò)各點(diǎn)間的最短距離.

(2)在其他情況下，如果出現(xiàn)Dk=D(k－1)或時(shí)，可取 p=k .

本文采用Floyd算法求出每架飛機(jī)的滑行路徑之后，可以求出每架飛機(jī)到達(dá)最短路徑上每個(gè)結(jié)點(diǎn)的時(shí)間.然后判斷可能產(chǎn)生沖突的點(diǎn)和滑行邊，并假設(shè)存在沖突的邊為斷路，再次采用Floyd算法求出新的最短路，即次短路，令優(yōu)先級(jí)別較低的飛機(jī)避開(kāi)高峰路段，選擇次短路滑行.

圖3 首都機(jī)聲T2和東跑道部分簡(jiǎn)化圖

以上是首都機(jī)場(chǎng)T2和東跑道的部分簡(jiǎn)化圖，比如飛機(jī)i著落后要從跑道R7結(jié)點(diǎn)到停機(jī)位G217，可以為之確定多條理想路徑:

①R7—T10—T11—T12—G217;

②R7—T10—T11—T27—G217.

在實(shí)際的滑行中就可以為飛機(jī)提供更多的選擇，若此時(shí)恰好有飛機(jī)j在T10—T11中與其發(fā)生沖突，則可以假設(shè)T10—T11為斷路，重新利用Floyd算法計(jì)算新的理想路徑:

③R7—T10—T9—T26—T27—G217;

④R7—T10—T9—T11—T27—G217;

⑤R7—T10—T9—T11—T12—G217.

計(jì)算若將飛機(jī)甲在T10處等待若干秒后的滑行時(shí)間和繞行滑行時(shí)間相比較，采取總調(diào)度時(shí)間較短的方案執(zhí)行.具體算法流程圖如圖4.

圖4 算法流程圖

圖4為飛機(jī)到達(dá)滑行道任意結(jié)點(diǎn)A，而目的地設(shè)為F時(shí)的路徑選擇流程圖.

4 模型計(jì)算與算例實(shí)現(xiàn)

本文采用首都機(jī)場(chǎng)T2和東跑道某天機(jī)場(chǎng)道面的滑行調(diào)度的實(shí)際數(shù)據(jù)進(jìn)行研究，給出了某一高峰時(shí)刻15 min內(nèi)在T2航站樓進(jìn)行起降的10個(gè)飛機(jī)(見(jiàn)表1).針對(duì)以下3種方案進(jìn)行了實(shí)驗(yàn)比較，主要包括總路長(zhǎng)，滑行時(shí)間和調(diào)度時(shí)間，延誤航班數(shù)等(見(jiàn)表2).

表1 航班計(jì)劃

表2 驗(yàn)結(jié)果比較

方案1:以滑行時(shí)間最短為目標(biāo)函數(shù)，確定飛機(jī)最短路徑，使飛機(jī)在停機(jī)位或跑到入口無(wú)限時(shí)等待，以最優(yōu)放飛數(shù)序放飛［4］;

方案2:以滑行時(shí)間最短為目標(biāo)函數(shù)，將等待時(shí)間分散到滑行中各個(gè)結(jié)點(diǎn)，避免停機(jī)位和跑道入口無(wú)休止等待;

方案3:以調(diào)度時(shí)間最短為目標(biāo)，運(yùn)用Floyd算法計(jì)算理想路徑，確立多條無(wú)障礙路徑，必要時(shí)繞開(kāi)最短路，選擇次短路，避開(kāi)滑行高峰路段.

由此可以看出，方案2將等待時(shí)間分散到各個(gè)結(jié)點(diǎn)后，雖然總滑行時(shí)間不變，但是調(diào)度時(shí)間減少了，尤其是方案3中選擇次短路后，回避了沖突，增加了滑行總路徑和滑行時(shí)間，但是就總體調(diào)度來(lái)說(shuō)，時(shí)間減少了，緩解了機(jī)場(chǎng)的忙碌狀態(tài)，節(jié)約了調(diào)度時(shí)間.此外，進(jìn)港飛機(jī)的空中等待時(shí)間減少，提高了機(jī)場(chǎng)跑道容量的實(shí)際利用率，在一定程度上，提高了航班的安全性.

比如一個(gè)機(jī)場(chǎng)年運(yùn)行量30萬(wàn)架次，旅客吞吐量2700萬(wàn)的機(jī)場(chǎng)，如果每架飛機(jī)平均減少30 s的調(diào)度時(shí)間，那么每年就可以節(jié)省2500個(gè)飛機(jī)小時(shí)和22萬(wàn)多個(gè)旅客小時(shí).這也說(shuō)明了本文的模型不僅對(duì)機(jī)場(chǎng)滑行道高峰時(shí)刻飛機(jī)的調(diào)度是有效的，對(duì)于整個(gè)航空運(yùn)輸系統(tǒng)來(lái)說(shuō)更是非常有意義的.

5 結(jié)論

本文在文獻(xiàn)［4-5］的基礎(chǔ)上，改進(jìn)了目標(biāo)函數(shù)，將滑行時(shí)間最短轉(zhuǎn)化為調(diào)度時(shí)間最短，極大的緩解了機(jī)場(chǎng)地面滑行道的緊張狀況.同時(shí)，F(xiàn)loyd算法的引入，提供了飛機(jī)滑行的多條無(wú)障礙路線(xiàn)，避免了最短路的擁擠，使機(jī)場(chǎng)資源得到最大限度的使用.

然而在本文的研究中為了問(wèn)題的簡(jiǎn)化，忽略了機(jī)型的不同.實(shí)際的場(chǎng)面調(diào)度中，因機(jī)型的不同會(huì)產(chǎn)生飛機(jī)優(yōu)先級(jí)的不同，最短安全間隔的不同，會(huì)增大問(wèn)題的復(fù)雜度.因此，把飛機(jī)機(jī)型考慮在內(nèi)是進(jìn)一步研究的方向.

［1］劉兆明，葛宏偉，錢(qián)峰.基于遺傳算法的機(jī)場(chǎng)調(diào)度優(yōu)化算法［J］，華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，34(3):392-398.

［2］GOTTELAND J B，DURAND N，ALIOT J M，et al.Aircraft Ground Traffic Optimization［C］.4th International Air Traffic Management R＆D Seminar ATM 2001，Santa Fe，2001.

［3］PESIC B，DURAND N，ALIOT J M.Aircraft Ground Traffic Optimization using a Genetic Algorithm［C］.Gentic and Evolutionary Conputation Conference GECCO 2001，San Francisco，2001.

［4］SIVAKUMAR RATHINAM，JUSTIN MONTOYA，YOON JUNG.An Optimization Model For Reducing Aircraft Taxi Times at The Dallas Fort Worth International Airport［C］，26th International Congress of The Aeronautical Sciences，2008.

［5］SMELTINK J W，SOOMER M J，DeWaal P R，et al.An Optimisation Model for Airport Taxi Scheduling［C］.Thirtieth Conference on the Mathematics of Operations Research，Lunteren，The Netherlands，2005.

［6］黃雍檢，賴(lài)明勇，MATLAB語(yǔ)言在運(yùn)籌學(xué)中的應(yīng)用［M］.長(zhǎng)沙:湖南大學(xué)出版社，2005:75-84.

［7］VISSER H G，ROLING P C.Optimal Airport Surface Traffic Planning Using Mixed Integer Linear Programming［C］.AIAA Aviation Technology，Integration and Operations(ATIO)Conference，Denver，CO，2003.

［8］BALAKRISHNAN H，JUNG Y.A Framework for Coordinated Surface Operations Planning at Dallas-Fort Worth International Airport，AIAA Guidance，Navigation，and Control Conferen-ce Hilton Head，SC，2007，20-23.

［9］鄭潔，高劍明.機(jī)場(chǎng)地面作業(yè)調(diào)度問(wèn)題研究［J］，河北北方學(xué)院學(xué)報(bào)(自然科學(xué)版)，2008，24(6):60-62.