基于理想滑行路徑的機場滑行道調度策略模型

牟德一，劉金鳳

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

0 引言

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

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

1 飛機地面滑行調度問題

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

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

通常情況下的一般作法是將交叉沖突看作結點沖突，把相遇沖突看作滑行邊沖突，而追尾沖突既可以看作邊沖突，也可以看作點沖突.因為如果在滑行速度保持不變的情形下，若兩架飛機在滑行邊相向滑行因間距不足而產生追尾沖突，則在構成該滑行邊的兩結點也會產生結點沖突，反之亦然.因此，本文只將沖突分為邊沖突和點沖突.

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

本文假設，所有飛機的優先級相同，即先到達結點先滑行原則.當時刻相等時，進港飛機優先于離港飛機，主要是為了減少進港飛機的空中等待時間，做到安全節油.

2 分散等待時間模型

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

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

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

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

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

因此本文引入兩個時刻來表示飛機到達且經過該結點的時間:

下面對進離港飛機的特殊結點到達和離開時間進行特殊說明.

進港飛機:

第一個結點為滑行道入口，飛機到達該點的時間為飛機的進港時刻，離開該結點的時間為飛機接到指令開始滑行的時刻.即:=飛機著落時刻，=開始滑行的時刻;

最后一個結點為停機位，飛機到達該結點時間為實際到達時間，離開時間為無窮大(不考慮轉機情形)，在此模型中，設置為+整個研究的時間段即可.

離港飛機:

變量ziju=1表示飛機i在飛機j之前到達結點u，否則為0.

Tsep為滑行規定通過同一結點的兩架飛機的時間間隔，一般因機型不同而有所差距.

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

上一節將滑行時間與調度時間區分開，下面將理想滑行路徑與最短路徑區分開.飛機最短路徑是指地面交通網絡上任意起始終止點間存在的多條路徑中滑行距離最短或滑行時間最短的一條路徑;飛機理想滑行路徑是指在地面滑行調度中，以沖突最小，最終實現所有飛機調度時間最短為目標的路徑，通常情況下是次短路.最短路徑是飛機滑行的最基本路徑，次短路徑作為補充部分構成飛機滑行路徑的理想路徑.飛機只有按照理想滑行路徑在機場地面交通網絡上滑行才有助于網絡上運行飛機的合理分布及網絡上飛機流的動態均衡.

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

計算次數p的確定:

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

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

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

圖3 首都機聲T2和東跑道部分簡化圖

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

①R7—T10—T11—T12—G217;

②R7—T10—T11—T27—G217.

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

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

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

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

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

圖4 算法流程圖

圖4為飛機到達滑行道任意結點A，而目的地設為F時的路徑選擇流程圖.

4 模型計算與算例實現

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

表1 航班計劃

表2 驗結果比較

方案1:以滑行時間最短為目標函數，確定飛機最短路徑，使飛機在停機位或跑到入口無限時等待，以最優放飛數序放飛［4］;

方案2:以滑行時間最短為目標函數，將等待時間分散到滑行中各個結點，避免停機位和跑道入口無休止等待;

方案3:以調度時間最短為目標，運用Floyd算法計算理想路徑，確立多條無障礙路徑，必要時繞開最短路，選擇次短路，避開滑行高峰路段.

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

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

5 結論

本文在文獻［4-5］的基礎上，改進了目標函數，將滑行時間最短轉化為調度時間最短，極大的緩解了機場地面滑行道的緊張狀況.同時，Floyd算法的引入，提供了飛機滑行的多條無障礙路線，避免了最短路的擁擠，使機場資源得到最大限度的使用.

然而在本文的研究中為了問題的簡化，忽略了機型的不同.實際的場面調度中，因機型的不同會產生飛機優先級的不同，最短安全間隔的不同，會增大問題的復雜度.因此，把飛機機型考慮在內是進一步研究的方向.

［1］劉兆明，葛宏偉，錢峰.基于遺傳算法的機場調度優化算法［J］，華東理工大學學報(自然科學版)，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語言在運籌學中的應用［M］.長沙:湖南大學出版社，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］，河北北方學院學報(自然科學版)，2008，24(6):60-62.