側向跑道機場滑行路徑優化

何 庶， 盧朝陽*， 王顏顏， 王大山

(1.南京航空航天大學民航學院， 南京 211100； 2.中國商用飛機有限責任公司民用飛機試飛中心， 上海 210000)

中國民航事業的發展迅猛，截至2019年，中國共有頒證運輸機場238個，2019年中國民航運輸機場完成旅客吞吐量13.52億人次，較上年增長6.9%[1]，航班起降量急劇上升，機場和航空器的數量不斷增加。中國通過建設側向跑道機場，以減少跑道穿越，提高場面運行效率。但是隨著側向跑道的建設，機場場面的跑滑結構也越來越復雜，滑行沖突點以及航空器在運行過程中產生的沖突也逐漸增多。因此，如何提高側向跑道機場的場面運行效率和航空器滑行效率成為當前亟需解決的問題。

對于機場場面滑行路徑規劃問題，中外學者已經做出了大量研究。Rathinam等[2]考慮了航空器機型和各種場面滑行安全約束，利用混合整數線性規劃(mixed integer linear programming，MILP)進行航空器路由調度研究。Smeltink等[3]提出了采用靜態規劃方法給出了MILP模型的滑行路徑和進離場時間。Clare等[4]提出了一種結合跑道排序問題的MILP 路徑優化問題模型。付宇曉等[5]提出了基于人工勢場和競爭性脈沖耦合神經網絡(competitive pulse coupled neural network，CPCNN)的滑行路徑規劃算法。姜雨等[6]以所有航空器的滑行總時間最小為目標建立相關模型，采用了雙層規劃法對模型進行求解，得到協同優化的結果。張兆寧等[7]使用遠端繞行滑行道優化航空器滑行路徑的問題，有效地縮短了全局滑行時間。姜雨等[8]建立了基于時空網絡的大型機場航空器滑行調度模型，引入距離阻抗權重與轉向阻抗權重對滑行路徑進行優化，并利用Dijkstra算法進行求解。

而對于側向跑道機場的研究就比較少。Henderson[9]分析了不同模式下的尾流模型，并對尾流的產生和消散進行仿真。Meng等[10]對交叉跑道的離場容量進行了研究。Li等[11]分析了平行跑道和側向跑道的不同特點，研究了機場在4種不同模式下的安全時間間隔，建立了機場仿真模型，對側向跑道機場的運行效率進行評估。李雄等[12]以成都天府國際機場為例，對側向跑道的在不同運行模式下的運行容量進行分析。沈志遠等[13]針對側向雙跑道機場系統，考慮尾流影響構建出側向雙跑道系統的跑道容量理論計算模型。

然而，現有的機場場面滑行路徑優化多針對單跑道或平行跑道構型，缺少對于側向跑道機場的滑行路徑優化問題的研究。因此，研究側向跑道機場場面滑行路徑優化問題，對于提高場面運行效率，指導中國未來機場建設具有重大意義。

1 滑行路徑優化模型構建

1.1 問題描述

面對滑行路徑優化的問題，需要解決航空器在場面滑行中的滑行沖突，并找到一個最優的滑行路徑，使成本降到最低。根據多方因素考慮實際滑行過程中的最低目標成本設定，將機場場面圖在網絡圖上表現出來，然后在根據相應的智能算法和建模分析優化現有路徑，最終達到優化的目的。

1.2 優化方案

在實際的場面運行中，出現沖突時，管制員通常采用讓航空器等待，當航空器等待無法解決沖突時，就考慮讓航空器選擇另外的滑行路徑。當發生沖突解脫時，采用以下原則進行設置航空器的優先級：航空器延誤越高，其優先級越高。如果航空器延誤相同，離場航空器的優先級更高。如果兩架航空器均為進場或均為離場，則認為預計先到達終點的航空器優先級更高。基于以上原則，提出了滑行道調度優化策略，即根據側向跑道機場場面滑行路徑的變化，動態地調整飛機滑行的優先順序，如果航空器選擇的滑行路徑較優，則可以加大優先級的變化。如果航空器選擇的滑行路徑較差，則應使得航空器的優先級的變化減小，提高算法的效率和解的質量。

1.3 建立模型

根據航空器的滑行特點和側向跑道機場的場面布局，用點和線段組成的網絡拓撲圖G=(V,E)抽象表示機場的場面布局，其中V表示航空器場面滑行過程中的各個節點或停機區，E表示各個節點的連接弧段。

1.3.1 目標函數

(1)

1.3.2 約束條件

為了保證側向跑道機場的航空器場面滑行的安全性，需解決滑行過程中的4種沖突：交叉沖突，追尾沖突，對頭沖突和復飛沖突。基于以上沖突，約束條件用數學公式表達如下。

(1) 點順序約束可表示為

Ziju+Zjiu=1, ?u∈Ri∩Rj, ?i,j∈Nf,i≠j

(2)

式(2)中：i,j表示不同的航空器，若航空器i比航空器j先到達節點u，則Ziju=1，反之，Ziju=0。

(2) 邊順序約束可表示為

Ziju=Zjiv, ?euv∈Ei∩Ej, ?i,j∈Nf,i≠j

(3)

Ziju=Zjiv, ?euv∈Ei, ?euv∈Ej, ?i,j∈Nf,i≠j

(4)

該約束表示如果滑行邊euv是航空器i和航空器j的相向或同向滑行邊，則若航空器i比航空器j先通過節點u，也需要比航空器j先通過節點v反之亦然。

(3) 交叉點最小安全間隔約束，可表示為

min{sep,luv}，?u∈Ri∩Rj,euv∈Ei,

?i,j∈Nf,i≠j

(5)

min{sep,lwv}，?v∈Ri∩Rj,ewv∈Ei,

?i,j∈Nf,i≠j

(6)

(4) 滑行時間約束可表示為

(7)

(8)

(9)

式中:PBTi表示離場航空器i預計推出時間；SATi表示航空器i到達快速脫離道口時間；RATi表示從側向跑道離場的航空器i的可起飛時間。該約束表示離場航空器i必須在航空器預計推出時間PBTi之后開始滑行，進場航空器i的滑行時間需要在預計到達快速脫離道口SATi后，側向跑道離場航空器的航班i需在可起飛時間后離場。

(5)滑行速度約束可表示為

(10)

(6) 停機位約束可表示為

(11)

2 算法設計

2.1 遺傳算法

遺傳算法(genetic algorithm，GA)是一種全局自適應概率搜索算法，以自然選擇和基因遺傳學原理為基礎，以生物進化優勝劣汰的自然選擇機理和生物界繁衍進化的遺傳機制作為指導思想。遺傳算法是一種搜索啟發式算法，常用來解決一些路徑的搜索和優化問題。

遺傳算法的主要步驟包括：染色體編碼、設計適應度函數、選擇操作、交叉操作與變異操作等。算法的基本流程圖如圖1所示。

圖1 算法基本框架

2.2 基于改進遺傳算法的滑行路徑優化算法設計

2.2.1 編碼

2.2.2 適應度函數

由于是雙鏈染色體，設定兩個適應度函數。

(12)

(13)

式中：適應度函數fitness1為航空器的滑行路徑總長度取倒數，用來評價各航班的滑行路徑；適應度函數fitness2為目標函數取倒數，用來評價沖突解脫后種群的目標值。

2.2.3 選擇

進行選擇操作能夠選擇出較好的個體，從而提升種群的整體適應度。輪盤賭是常用的方法，適應度函數fitness2是根據沖突解脫后的目標函數而得到的，通過該函數選取優良個體再生種群。選擇的概率為pi，可表示為

(14)

2.2.4 交叉

采用自適應遺傳算法中的交叉率p1,可表示為

(15)

式(15)中：fitness1max表示種群中fitness1的最優值；fitness1a表示fitness1的平均值；fitness1表示兩架進行交叉變異的航空器中較優的fitness1值；fitness1β表示需要變異的航空器的fitness1值；k1、k2為常數。

2.2.5 變異

采用自適應的變異率p2，可表示為

(16)

式(16)中：fitness1β為要進行變異航班的fitness1值；k3、k4為常數。采用自適應交叉變異率，可以使種群的多樣性得到保障，同時也使得改進的遺傳算法能夠實現高效收斂。

2.2.6 精英保留

根據適應度函數fitness2保留每一代種群中15%的最優個體用于再生種群，以加快算法收斂。

2.3 滑行沖突與解脫

側向跑道機場的航空器在滑行及等待過程中存在4種沖突引起延誤，分別為交叉沖突，對頭沖突，追尾沖突和平行跑道對側向跑道造成的運行沖突引起的延誤。用Points集合表示航班的點占用集合。用DifEdges集合表示相向滑行邊占用集合。用SameEdges集合表示同向滑行邊占用集合。用Judges集合表示判定區占用集合，對于從側向跑道離場的航班，需要判斷Judges集合中是否有進近航班，若有，則直到沖突解脫即可離場，反之亦然。對4個集合進行遍歷，找出可能存在的滑行沖突，進行相應的沖突解脫，及時更新4個集合，直到全部的航空器在滑行中都達到最小安全間隔為止。

2.3.1 交叉沖突

在交叉沖突解脫過程中，先判斷各航空器的優先級，以此確定各架航空器經過交叉點u的順序和時間，從而實現交叉沖突解脫。當航空器i優先級較高時，則先讓航空器i通過，航空器j需要等待，直到航空器i和航空器j達到安全間隔，并且更新航空器j的節點時間，直到沖突解脫。交叉沖突如圖2所示。

圖2 交叉沖突示意圖

2.3.2 追尾沖突

如果發生追尾沖突，則需要判斷航空器euv的優先級，以此調整各航空器經過鏈路的順序和時間，避免發生追尾沖突。當航空器i優先級較高，但航空器j速度大于前機，則航空器j在滑行到與航空器i距離小于安全距離后需減速，和航空器i保持一致，直至實現追尾沖突解脫。追尾沖突如圖3所示。

圖3 追尾沖突示意圖

2.3.3 對頭沖突

在滑行過程中，航空器到達節點u及節點v的時間可依據航班的優先級來調整，讓航班之間滿足最小安全滑行間隔，實現對頭沖突的解脫。對頭沖突如圖4所示。

圖4 對頭沖突示意圖

2.3.4 復飛沖突

當航班i在euv判斷區航段內，離場航班j需在原地等待，并判斷航班i是否產生復飛，若有復飛，則當航班i飛越v點時，航班j繼續等待，直到航班i飛越w點時方可離場。復飛沖突如圖5所示。

圖5 復飛沖突示意圖

2.4 求解步驟

步驟1設Iter為迭代次數，M為種群數目。隨機生成X架航空器的優先級序列和滑行路徑，并初始化種群，計算每個種群的適應度函數fitness1的值。

步驟2進行沖突探測與解脫，計算種群的滑行時刻表，并求出適應度函數fitness2的值，具體過程如下。

(1)首先輸入相應的染色體，設定航空器的優先級最高級k為1，且認為最高級別的航空器滑行路徑是無沖突的，將最高級別的航空器經過的節點和對應時間添加到Points、SameEdges、DifEdges和Judges 4個集合中。

(2)遍歷k(k=2,3,…,n)級別的航空器經過的節點和過點時間，將其與Points、SameEdges、DifEdges和Judges集合中記錄的節點和過點時間做比較，探測是否存在滑行沖突。

(3)如果探測出沖突，則修改該級別的航空器的滑行時刻，如果在路徑的第二節點探測出沖突，則修改航空器的出發時間，返回步驟2。如果無沖突，則轉到步驟4。

(4)在Points、SameEdges、DifEdges和Judges 4個集合中記錄k級別航空器經過的滑行節點和對應的過點時間。

(5)判斷k是否為最高級別n，如果不是，k+1，返回至步驟2。否則返回至步驟3。

步驟3按照計算出的fitness2，按照一定的比例對精英種群進行保留。然后選取再生種群,根據fitness1確定p1、p2、p3、p4，并選擇需要進行交叉變異操作的種群。

步驟4至此產生新一代種群，迭代次數Iter-1，當滿足條件(5)，則停止，否則返回至步驟2。

步驟5當Iter為0時，算法終止，輸出最優的航空器的優先級序列，滑行路徑和對應過點時間。

3 實例分析

以天府國際機場，對機場場面結構進行簡化，得到機場網絡有向拓撲圖(圖6)。

圖6 成都天府國際機場網絡拓撲圖

為簡化場面環境，將停機位分成21個區域，分別是1～21區，每個停機區包含多個停機位，離場航空器從停機區出發，進場航空器則選擇相應的可用停機區，各停機區分布如圖7所示。選取典型日高峰小時15 min(08:45—09:00時段內)的仿真航班數據進行驗證，為使得結果更加清晰，將航班號以序列號代稱，該時間段內共有12架航班，通過數據處理，得到航班時刻表，如表1所示。

表1 航班滑行時刻

圖7 停機區分布

在Hewlett-Packard(3.20 GHz，4.00 GB)計算機中，用MATLAB語言進行編程，并對算法的參數進行設定：迭代次數Iter=80，種群大小M=200，目標函數中，滑行時間權重系數m=1，離場出發延誤系數n=1，取α=0.5，pf取極小數，將交叉概率中的參數設置為k1=0.5，k2=0.9，變異概率中的參數設置為k3=0.02，k4=0.05，航空器運行管理手冊中指出，航班在場面上滑行的速度在10～50 km/h。為了簡化成都天府國際機場的場面運行環境，各航班在側向跑道機場的場面滑行道上的滑行速度為8 m/s。通過實驗可以得出，航空器在側向跑道機場場面滑行的最優調度序列為(4、7、9、10、11、3、5、1、8、6、2、12)，具體調度規劃如表2所示。

表2 滑行序列優化對比

用上取整標記法記錄航空器到達各個路徑點的時間。在實際航班調度的情況中，采用的原則通常是先到先服務(FCFS)。因此，為了驗證本算法的有效性和可行性，分別對采用優化航班序列的結果和采用先到先服務得出的結果進行對比，如表3所示。

表3 FCFS序列與優化序列對比

為了使FCFS序列和優化序列的結果對比更加清晰，根據出發延誤，滑行道延誤，滑行時間和滑行總時間繪制了不同序列下的對比，如圖8所示。

圖8 優化序列與FCFS序列對比

多架航空器經過同一滑行節點時，通過該節點的優先次序取決于航空器的優先級，當一架高級別的航空器的時刻表產生更新，會對低級別航空器的航班時刻產生相應的影響，因此管制員進行滑行道調度時，需要合理分配航空器的優先級，從而提高場面運行效率。航空器經過相同路徑，但航空器的優先級序列不同時所得到的調度結果如表3所示。可以看出，在當前的優化序列下，全部航空器的滑行總耗費時間成本為3 226 s，而在FCFS序列下，所有航空器的滑行總耗費時間成本為3 268 s，在優化序列的調度規則下，其總耗費時間比先到先服務(FCFS)的總耗費時間少 42 s。其中，優化序列的出發延誤時間為4 s，FCFS序列的出發延誤時間達到了46 s，優化序列的出發延誤比FCFS序列的出發延誤減少了42 s，滑行道延誤均為2 s，滑行時間均為3 220 s。可以看出各航空器在滑行過程中，分別停機區和滑行道上進行等待，從而使得側向跑道機場的滑行道的運行效率大大提高。

為驗證算法的有效性，利用蟻群算法對實驗數據進行測試，設置改進遺傳算法與蟻群算法的種群大小為30，迭代次數為80，兩種算法各自運行15次得出對比情況如圖9所示。在15次運行結果中，蟻群算法同樣可以得到最優解，但解的波動性較大，而改進的遺傳算法雖然同有波動性，但其與最優解相差較少，且尋優次數更多。

圖9 遺傳算法與蟻群算法對比

4 結論

以加權滑行時間和延誤等待總時間最小為目標，建立側向跑道機場滑行路徑優化模型，對航空器的滑行路徑進行優化，并以成都天府國際機場為例，利用遺傳算法進行求解，得出每個航班的滑行路徑及相應的航班時刻，并與FCFS方案進行對比，得到以下結論。

(1) 優化方案有效地縮短滑行道滑行時間，可以為側向跑道機場的滑行路徑提供規劃策略，提高場面運行效率。

(2) 通過與蟻群算法的對比分析，驗證了改進遺傳算法的有效性。