基于理想滑行路徑的機(jī)場滑行道調(diào)度策略模型

牟德一，劉金鳳

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

0 引言

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

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

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

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

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

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

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

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

2 分散等待時間模型

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

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

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

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

圖2 跑道和滑行道的等待線

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

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

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

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

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

離港飛機(jī):

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

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

3 確定多條無障礙路徑的Floyd算法

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

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

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

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

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

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

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

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

①R7—T10—T11—T12—G217;

②R7—T10—T11—T27—G217.

在實(shí)際的滑行中就可以為飛機(jī)提供更多的選擇，若此時恰好有飛機(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處等待若干秒后的滑行時間和繞行滑行時間相比較，采取總調(diào)度時間較短的方案執(zhí)行.具體算法流程圖如圖4.

圖4 算法流程圖

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

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

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

表1 航班計(jì)劃

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

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

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

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

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

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

5 結(jié)論

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

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

［1］劉兆明，葛宏偉，錢峰.基于遺傳算法的機(jī)場調(diào)度優(yōu)化算法［J］，華東理工大學(xué)學(xué)報(自然科學(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］黃雍檢，賴明勇，MATLAB語言在運(yùn)籌學(xué)中的應(yīng)用［M］.長沙:湖南大學(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ī)場地面作業(yè)調(diào)度問題研究［J］，河北北方學(xué)院學(xué)報(自然科學(xué)版)，2008，24(6):60-62.