翟文鵬，劉潤南，朱承元

（中國民航大學空中交通管理學院，天津300300）

為了緩解航空運輸壓力、機場滑行道擁堵、航班延誤、機場容量不足等問題，民航界學者對場面滑行路徑優(yōu)化展開了大量研究[1]，選取的優(yōu)化目標主要包括：航班滑行時間最短與延誤時間最少[2]、航班無沖突與滑行距離最短[3]、航班等待與延誤時間最少[4]等。這些研究考慮了多個優(yōu)化目標，但均假設(shè)滑行路徑規(guī)劃起始時刻航班均處于停機位或快速脫離道入口，場面無正在滑行的航班。這與大型繁忙機場24 h 全天候運行情況不符。其次在優(yōu)化算法方面，多以精確求解算法（如混合整數(shù)規(guī)劃[5]）、智能算法（如遺傳算法[6]、蟻群算法[7]等）為主。在大規(guī)模航班滑行路徑優(yōu)化問題上，精確求解算法計算量大、求解時間長；智能算法求解時間大大縮短，但求解得出的規(guī)劃方案嚴重依賴場面的精確運行，發(fā)生一次滑行道入侵或航班延誤，就必須對全局重新規(guī)劃。同時航班在場面滑行過程中受諸多隨機因素影響，文獻[8]對20 多個滑行路徑優(yōu)化算法進行了優(yōu)缺點分析和評價，其中總結(jié)的算法皆屬于離線靜態(tài)算法，無法動態(tài)規(guī)劃路徑，實用性不高，如能結(jié)合動態(tài)路徑搜索思路則更具有現(xiàn)實意義。文獻[9]針對這一問題提出了滾動時域的滑行路徑優(yōu)化算法，較好地實現(xiàn)了航班滑行路徑中的動態(tài)搜索，但滾動時域算法對時間精度要求高，實際操作難度大，計算錯誤易被疊加放大。

綜上，現(xiàn)有研究方法不僅局限于靜態(tài)搜索，研究思路也大多考慮戰(zhàn)術(shù)性優(yōu)化滑行路徑，而實際運行中，以預戰(zhàn)術(shù)的思路對航班進行規(guī)劃更能提高機場工作效率。因此，提出對處于機場終端區(qū)的航班預先進行戰(zhàn)術(shù)性的滑行路徑動態(tài)優(yōu)化。以降低場面擁堵、航班延誤及地面管制人員的工作負荷為目的，借鑒滾動時域算法的動態(tài)搜索思想[10]對傳統(tǒng)Dijkstra 算法[11-12]進行改進，綜合算法優(yōu)點計算最優(yōu)解。以滑行時間最短和沖突避免為目標，建立大型繁忙機場的運行環(huán)境，通過TAAM（total airspace and airport modeller）仿真軟件結(jié)合Matlab 編程，對滑行路徑動態(tài)優(yōu)化方法進行研究，驗證提出方案的可行性。

1 滑行路徑動態(tài)優(yōu)化算法

通過在終端區(qū)對航班進行預戰(zhàn)術(shù)性優(yōu)化，提前將終端區(qū)的航班進行分類。對需要優(yōu)化的航班建立優(yōu)化模型，在每次優(yōu)化計算航班滑行路徑前，對當時機場場面具體情況進行預測。通過改進Dijkstra 算法對每架在中間進近階段前的航班進行滑行路徑優(yōu)化，減少航班降落后地面管制人員的工作負荷。

1.1 航班集合劃分

出于預戰(zhàn)術(shù)側(cè)重的思想，首先對終端區(qū)航班進行提前分類。在保證不出現(xiàn)航班沖突等失誤的前提下，進一步對特定航班集合進行優(yōu)化，以達到滑行路徑的最優(yōu)選擇。圖1 展示了依據(jù)時間劃分航班集合的原理。

圖1 航班集合劃分原理圖Fig.1 Principle diagram of flight assembly division

圖1 中t 為時鐘，記錄和更新當前時刻，每當終端區(qū)雷達掃描到新航班時（t3時刻），便將此航班由航班集合3（未優(yōu)化）移到航班集合2（進行優(yōu)化）中，航班集合2 即為后文進行改進算法優(yōu)化的航班集合。隨著時間的進行（t2時刻），航班集合2 中最早進入的航空器將被推送到航班集合1（已優(yōu)化）中，考慮到航空器必須滿足安全間隔，凍結(jié)時間不能過小，凍結(jié)區(qū)域的航空器不會參與下一次的排序計算，航班集合1 中的航空器滑行路徑不會再變更。

航班集合的分類涉及實際時間與規(guī)劃時間，在仿真操作中分別對應后文中兩次TAAM 仿真運行。兩者的具體關(guān)系如圖2 所示。

圖2 實際時間與規(guī)劃時間關(guān)系Fig.2 Relationship between actual time and planning time

圖2 中：Tw為航班進行路徑優(yōu)化的時長，每架航班的優(yōu)化時長（Tw）將被均勻分割成連續(xù)等長的時間片進行具體優(yōu)化計算，便于與后文滑行道傳輸模型相結(jié)合，判斷模型節(jié)點處是否存在航空器沖突；TL為前置時間，前置時間TL對應后文兩次仿真運行的時間差，前置時間具體長度對應圖1 中t2時刻至航班落地脫離跑道的時刻；Tc為優(yōu)化計算所需時長，即程序優(yōu)化計算所用時間；Tadv表示相鄰兩次優(yōu)化計算運行的時間間隔，間隔時長Tadv會根據(jù)不同機場對應的進近程序及平均滑行時間進行調(diào)整，同時為保證凍結(jié)時間的作用，間隔時長Tadv的值應等于凍結(jié)時長的值；Twait為相鄰兩架航班依次出現(xiàn)的時間差。

基于仿真與航班運行的真實情況，不同時長的值應滿足以下條件

Tadv

Twait=Tadv-Tc

Tadv>Tc或Twait>0

Tw-Tadv為進行路徑優(yōu)化的時間，其數(shù)值等于圖1 中（t3-t2），同時t2、t3應滿足

1.2 航班數(shù)據(jù)獲取及預測

每架航班在終端區(qū)所處位置及對應時間可從TAAM 仿真軟件中獲得。假設(shè)航班時刻信息與機場場面情況均由機場場面控制人員掌握，實現(xiàn)空地信息共享。在每次場面路徑規(guī)劃前，將機場場面滑行道實際運行情況與航班的具體位置等數(shù)據(jù)作為每次航班滑行路徑優(yōu)化的初始數(shù)據(jù)。根據(jù)各機場不同進場程序，取平均最小值作為規(guī)劃前置時間，結(jié)合已知場面情況、場面各類型航班滑行速度等，得出規(guī)劃窗口中的預測基礎(chǔ)數(shù)據(jù)，再通過基礎(chǔ)數(shù)據(jù)進行路徑優(yōu)化，從而加強算法準確度，建模與優(yōu)化過程均在判斷航班集合2 中是否有新航班加入后進行。

1.3 滑行路徑優(yōu)化目標函數(shù)

對終端區(qū)航班進行分類以后，針對航班集合2，首先建立一個相對時間片內(nèi)的靜態(tài)場面運行模型。

1.3.1 模型假設(shè)

（1）離場航班推出時間可預測，預計離場時間已知，起飛跑道已知；

（2）進場航班預計進場時間已知，脫離跑道時間可預測，停機位已知；

（3）相較于進場航班，離場航班優(yōu)先級高，同為離場或進場航班優(yōu)先級相同；

（4）場內(nèi)所有滑行道適用于任何航班；

（5）每架航班都具備相應屬性，如機型、平均滑行速度等；

（6）在滑行道上同機型的航班滑行速度相同；

（7）地面最低尾流間隔可由速度轉(zhuǎn)化為時間間隔。

1.3.2 滑行道傳輸模型

將機場場面看作是由節(jié)點和鏈路構(gòu)成的網(wǎng)絡(luò)模型，如圖3 所示。

圖3 機場節(jié)點網(wǎng)絡(luò)模型Fig.3 Network model of airport node

假設(shè)G（N，L）為有向網(wǎng)絡(luò)圖，N={N1，N2，…，Nn}為節(jié)點集合。L={（Np，Nj）∈N×N}為鏈路集合，（Np，Nj）表示從節(jié)點Np到節(jié)點Nj，定義滑行道網(wǎng)絡(luò)的距離矩陣D=（dNpNj）n×n，其中

航班集合2 為R={f1，f2，…，fA}，共有A 個航班。對于任一航班fa∈R 在時間片k 所在窗口內(nèi)，從該時間片中起始節(jié)點Np滑行到節(jié)點Ns，在路段Ns→Nj上出現(xiàn)航班fb∈R，即認為節(jié)點Ns為沖突節(jié)點。

首先判斷航班fa與航班fb的優(yōu)先級，用H 表示優(yōu)先級高低，即

若航班fa優(yōu)先級低于航班fb，即H=1，航班fa在不需要重新尋找最短路徑的情況下，其滑行時間需要加上一個等待時間tha加以懲罰。

若α=1，則航班fa需要進行等待或更改此時段的滑行路徑。若航班fa在不需要重新尋找最短路徑的情況下，最小滑行時間還需要加上一個等待時間tha。

綜合以上描述可得時間當量長度表達式為

式中：lNsNj為節(jié)點Ns到節(jié)點Nj的鏈路長度為航班fa滑行的平均速度。

由于不同機型航空器滑行速度不同，對于同一滑行道，不同機型對應不同的時間當量長度。時間當量矩陣表示為Ts={tNsNj}，其中

如選擇改變滑行路徑由節(jié)點Ns更改至Nm，避免節(jié)點Ns沖突等待時間，滑行時間計算步驟同上。

由此可得k 到k+1 時段上的局部滑行路徑最短時間當量T 表達式為

每兩個連續(xù)時間片中，上一時間片的結(jié)束節(jié)點為下一時間段的起始節(jié)點，共有K 個時間段。航班集合2全局滑行路徑優(yōu)化目標函數(shù)表達式為

其中在同一個時間片內(nèi)計算路徑最短時間采用改進Dijkstra 算法。

1.4 改進Dijkstra 算法

傳統(tǒng)Dijkstra 算法由荷蘭計算機科學家Dijkstra于1959年提出，是從一個頂點到其余各頂點的最短路徑算法，解決了有向圖中最短路徑問題?，F(xiàn)對傳統(tǒng)Dijkstra 算法進行改進，加入時間窗口并將運行時間分為k 段時間片，每2 s 移動一次時間片。改進Dijkstra算法在每次增加后續(xù)節(jié)點時，根據(jù)所劃分時間片的時間當量長度更新一次相鄰的時間當量矩陣，通過不斷迭代求出時間當量長度最短的優(yōu)化滑行路徑。

將距離矩陣D 中每條路段劃分用向量In表示，In=[i1i2…in]，in表示第n 條路段。起始節(jié)點為滑行道入口，如時間片結(jié)束時該航班未處于已有節(jié)點，則根據(jù)所處位置增加臨時節(jié)點臨時節(jié)點不計入節(jié)點集合N 中），以記錄該時間片該航班的結(jié)束位置，并作為下一時間片該航班的起始節(jié)點。由于滑行速度一定，可直接得出速度矩陣（i）。改進Dijkstra 算法的主要計算步驟如下：

步驟1初始化，對于任意航班fa，距離矩陣D，時間段向量In，速度矩陣（i）；假設(shè)第一個時間段向量內(nèi)，t0時刻發(fā)生沖突，發(fā)生沖突的節(jié)點標記為Ns，航班fa出發(fā)節(jié)點記為Np。記使用節(jié)點集合P = {Np，Ns}，則未使用節(jié)點集合P′=N-P，循環(huán)次數(shù)in=1；

步驟2標記沖突節(jié)點Ns，設(shè)置Ns=（Ts，Zs）；Ts=Tp，Zs={Np}；

步驟3對任意節(jié)點Nm∈P′，且dNpNm＞0，取min{tNpNs，tNpNm}，計算公式為式（7）；

步驟4對新加入P 的節(jié)點Nm，將節(jié)點Nm作為起始節(jié)點，尋找P′中所有與Nm直接相連的節(jié)點（即dNmNj＞0），計算最小時間當量。同時令Ts= Tm，Zs={Nm}∪Zs，P={Nm}∪P，P′=P′-{Nm}；

步驟5更新滑行最短時間向量In，時間當量矩陣Ts及其最短路徑前驅(qū)節(jié)點向量集合Zs；in=in+1；

步驟6若in

2 TAAM 仿真軟件建模與算法實現(xiàn)

2.1 空中與地面仿真建模

基于西安咸陽國際機場的空中與地面數(shù)據(jù)建立TAAM 仿真模型。西安咸陽國際機場進近扇區(qū)分為5個，有6 條離場程序，7 條進場程序。地面現(xiàn)有3 座航站樓面積共350 000 m2；共有2 條跑道，跑道長度分別為3 000、3 800 m；停機位127 個。實驗規(guī)劃前置時間為12 min，移動間隔為2 s。建立機場具體仿真場景如圖4、圖5 所示，地面節(jié)點鏈路圖如圖6 所示。

圖4 西安咸陽國際機場空中仿真模型Fig.4 Air simulation model of Xi'an Xianyang International Airport

圖5 西安咸陽國際機場地面仿真模型Fig.5 Simulation model for ground of Xi'an Xianyang International Airportt

圖6 機場地面節(jié)點模型Fig.6 Node model for airport ground

從2018年全年航班日流量中選取航班978 架次（2018年8月20日），圖7 為部分航班時刻表。

圖7 部分航班時刻表Fig.7 A part of flight schedule

2.2 算法實現(xiàn)

TAAM 仿真軟件默認路徑選取方式即為傳統(tǒng)Dijkstra 算法。實現(xiàn)改進Dijkstra 算法的運用需通過TAAM 仿真軟件中的兩個網(wǎng)關(guān)，分別是TAAM 控制網(wǎng)關(guān)、模擬ADSI 網(wǎng)關(guān)。TAAM 控制網(wǎng)關(guān)能夠使用Matlab編程在模擬運行中代替默認代碼，使仿真運行時使用改進Dijkstra 算法。模擬ADSI 網(wǎng)關(guān)支持TAAM 仿真軟件將模擬情況轉(zhuǎn)換為ADSI 格式依次轉(zhuǎn)發(fā)至Matlab程序，以獲得模擬運行中場面各航班的具體位置。第1次運行TAAM 仿真（TAAM1）時得到Matlab 編程中關(guān)于各航班在終端區(qū)的時刻、飛行航跡、脫離跑道或停機位的具體位置與時間等內(nèi)容，以此為基礎(chǔ)編寫算法。第2 次運行TAAM（TAAM2）仿真時插入兩個網(wǎng)關(guān)，實現(xiàn)仿真與算法的結(jié)合。具體實現(xiàn)流程如圖8 所示。

圖8 算法實現(xiàn)流程圖Fig.8 Flow chart of algorithm implementation

圖8 中，TAAM1 獲得每個航班進入規(guī)劃終端區(qū)的時間、離開規(guī)劃窗口至快速脫離道入口的時長、到達快速脫離道入口的時刻與具體位置。由于模型是提前預測，假設(shè)此時TAAM1 運行時間為t0+前置時間，則航班處在終端區(qū)的時刻應為t0。Matlab 程序從TAAM 數(shù)據(jù)庫中獲取航班預計降落時場面具體情況（t0+前置時間時，機場場面有多少航班，以及航班所處位置；隨著時間片的移動，場面航班變化情況，以及各航班位置及對應時刻），根據(jù)獲得的基礎(chǔ)數(shù)據(jù)執(zhí)行算法，對航班滑行路徑進行規(guī)劃。規(guī)劃結(jié)束后將相應路徑通過TAAM控制網(wǎng)關(guān)輸入TAAM2 中運行，一直運行到再無新的航班進入終端區(qū)，此時TAAM2 中運行時間為t0時刻。最后通過模擬ADSI 網(wǎng)關(guān)獲得的TAAM2 中航班的實時數(shù)據(jù)，經(jīng)Matlab 處理后得到優(yōu)化后的場面運行數(shù)據(jù)。

3 結(jié)果及分析

以機場2018年8月20日的部分航班為例，由于優(yōu)化模型考慮可更改滑行路徑使時間最短，因此有必要對航班路徑更改的情況進行列舉，具體情況如表1所示。表1 中航班的路徑更改情況較為合理地證明了改進算法的有效性。

表1 部分航班滑行路徑更改對比Tab.1 Comparison of changes of taxiway of certain flights

同時改進算法中考慮了沖突解決，在仿真中，通過GMA（generic model area）工具箱可以實現(xiàn)對空間內(nèi)任意區(qū)域內(nèi)航班詳細流量進行統(tǒng)計；運用Reaporter 對滑行道沖突點進行統(tǒng)計，如圖9 所示。統(tǒng)計流量較大滑行道為圖9 中圈出區(qū)域。

圖9 滑行道擁堵區(qū)域Fig.9 Congestion area of taxiway

兩種算法下航班流量的對比統(tǒng)計情況如表2 所示。

表2 流量架次對比Tab.2 Comparison of traffic sorties

通過大流量區(qū)域的航班流量對比可以看出，改進Dijkstra 算法有效地緩解了滑行道擁堵情況，使得航班流量分配更加平均。由于改進Dijkstra 算法一定程度上進行了沖突規(guī)避，現(xiàn)對滑行道沖突點數(shù)量進行統(tǒng)計，得出優(yōu)化前后的沖突點數(shù)量分別為74 和59?？梢钥闯龈倪MDijkstra 算法在一定程度上減少了沖突量，減緩了場面擁堵的同時避開了沖突點，從而實現(xiàn)了滑行路徑的優(yōu)化。

最后對傳統(tǒng)Dijkstra 算法與改進Dijkstra 算法得出的2018年8月20日所有航班平均滑行時間、平均延誤時間進行對比，驗證優(yōu)化目標是否實現(xiàn)。統(tǒng)計結(jié)果如表3 所示。

表3 平均滑行時間與平均延誤時間對比Tab.3 Comparison of average taxiing time and delay time

由表3 可知，改進Dijkstra 算法較傳統(tǒng)Dijkstra 算法航班平均滑行時間縮短了12.2%，平均延誤時間縮短了25.8%。

傳統(tǒng)Dijkstra 算法與改進Dijkstra 算法全天滑行延誤時間統(tǒng)計如圖10 所示。

圖10 全天滑行延誤時間Fig.10 Taxiing delay time within a whole day

對比傳統(tǒng)Dijkstra 算法，改進Dijkstra 算法全天滑行延誤時間明顯縮短，全天滑行延誤峰值由239 s降至184 s，下降23%，高峰時段（18：00—22：00）總延誤時長由1 653 s（約27.5 min）降至1196 s（約19.9 min），下降了27.6%。實驗結(jié)果表明：改進Dijkstra 算法有效地解決了動態(tài)滑行路徑優(yōu)化問題，減少了延誤時間。

4 結(jié)語

滑行路徑優(yōu)化問題直接影響機場場面運行效率，也是提升機場容量和規(guī)模的關(guān)鍵。結(jié)合時間窗口對機場終端區(qū)航班進行提前規(guī)劃，對傳統(tǒng)Dijkstra 算法進行改進，利用TAAM 仿真軟件進行實際數(shù)據(jù)分析驗證。實驗結(jié)果表明，改進Dijkstra 算法克服了傳統(tǒng)Dijkstra 算法不能應用于動態(tài)路徑搜索的欠缺，通過時間片的加入較好地解決了隨機性等多種問題，使機場結(jié)果數(shù)據(jù)較優(yōu)于傳統(tǒng)算法，有效地減少了場面擁擠、滑行時間、滑行沖突及延誤時間，為今后機場場面航空器滑行規(guī)劃提供了一種更完善的理論方法。但由于改進Dijkstra 算法計算量較大，需要的時間窗口相應較大，間接導致了精確度降低。接下來可以進一步研究如何簡化計算，提高反饋精確度和預測準確性，更快速、簡單、有效地解決滑行路徑優(yōu)化問題。