基于最短路徑的臨時航線規劃方法研究

牛金鳳

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

基于最短路徑的臨時航線規劃方法研究

牛金鳳

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

為解決空中交通流量的擁堵造成的大規模航班延誤情況，文章根據航路上航路點的分布情況畫出網絡圖，建立動態規劃模型，應用了逆序算法求出網絡圖中的最短航路，并將此航路作為航空器選擇的一條臨時航線，最后用算例進行分析求解，驗證了該方法的可行性。

空中交通；交通網絡；逆序算法；最短路徑；臨時航線

近年來，人們的生活水平不斷提高，民用航空運輸不斷發展，空中交通擁堵已經成了一種普遍現象。航空器改航飛行不僅能夠保障航班的正班率，而且可以實現空域資源的優化配置，給航班安排一條臨時航線[1-5]，可以有效地緩解空中交通擁堵問題，對于航班的改航問題，近年來國內外學者進行了大量的發展研究，已經取得了一定的研究成果，包括航班臨時航線規劃研究綜述、基于改進幾何算法的擴散危險區改航策略研究、基于幾何算法的空中交通航路規劃、空中交通流量管理中的改航策略研究、基于蟻群算法的航路規劃研究與應用、基于人工勢場算法的航路規劃、飛行危險天氣下的航班臨時航線規劃研究、危險天氣下航路策略研究等[6-10]許多關于改航的方法和理論研究，大多數都是根據危險天氣的類型提出針對性的改航策略，本文在參考了上述文獻的基礎上，以交通流量擁堵為背景，提出了一種臨時航線的規劃方法，并通過算例驗證了該方法的可行性。

1 空中交通網絡

臨時航線的建立可以有效地緩解空中交通流量的壓力，本文以繁忙區域某段航路周圍的航路點為基礎建立空中交通網絡。如圖1所示，從A點到E點是流量擁堵的航路段，其余各點是距AE航段較近的點，要從網絡圖中找出一個從A到E的一個最短路徑，網絡中相鄰兩個節點之間的連線為航路，兩點之間連線上的數字表示航路距離，距離已知，采用動態規劃得到這條最短路徑[10]。

圖1 空中交通網絡

2 動態規劃模型的建立與求解

2.1 動態規劃模型的建立

對于一個非線性規劃模型，要應用動態規劃方法求解，首先要賦予“時段”的概念，將航段排序，如圖1所示，依次量出航段k=1，2，3，4的距離，將問題劃分為k個階段，每個階段只選一個航段，從而轉化成K段決策過程，然后選擇正確的決策變量，使后部子過程之間具有遞推關系。

階段K：取k=1，2，3...n。

狀態變量Sk：第k段航路的長度。

決策變量xk：決定選擇的地k段航路的長度。

狀態轉移方程：Sk+1=Sk+xk。

最優指標函數fk(Sk)：當所選航路段為Sk時，選擇第k-1個航路段得到的最短路徑。

基本方程：

2.2 模型求解方法

動態規劃的求解有兩種基本方法：逆序解法（后向動態規劃方法）、順序解法（前向動態規劃方法）[11]，本文采用逆序解法，即先要把需要解決的問題分為幾個先后階段，從最后一個階段開始，按照基本方程：

從終點向始點逐階段逆推，找出各點到終點的最短路徑，當逆推到始點時，也即找到了從始點到終點的全過程的最短路，最終求出全過程的最優策略。

3 算例分析

如圖2所示，A，M是航路上的兩點，圖3是從航路圖2中簡化出來的，圖3中其余各點是A到M這條直線周圍的航路點，從A到M有多種路徑，下面用逆序法算出從航路點A到航路點M走過的最短路徑。假設它們之間的距離已知。

圖2 參考航路

圖3 算例網絡

第一步，從k=4開始，狀態變量s4可取兩種狀態F，G，它們到M點的路長分別為20，40，即：f4(F)=20，f4(G)=40。

第二步，k=3，狀態變量s3可取3個值C，D，E，這是一個兩級決策問題，從狀態3到M不止一種方法，需加以比較，取其中最短的，即：

按照同樣的方法得到f2=90，f1=140。

所以得到最優路線A→B→C→F→M或A→B→D→F→E→M，即為從A到的M最短路徑，將如圖2所示的紅色線條，作為求出的一條臨時航線。

4 結語

本文根據航路上航路點的分布情況構造出空中交通網絡，運用運籌學中的動態規劃方法建立模型，采用逆序算法求出最短路徑，本文首先根據空中航路點的分布情況建立空中交通網絡，把空中交通路徑可視化展現出來，更好地分析空中交通奠定基礎，然后采用動態規劃中的逆序算法求出最短路徑，一方面可以為流量較大的航路分流，而且為臨時航線的建立提供一種理論依據。但是本文僅限于理論研究，下一步工作應該根據真實情況結合航路圖中的航路點來建立交通網絡，求出一條有實用價值的臨時航線。

[1]萬莉莉，田勇，葉博嘉.基于多目標優化的改航策略研究[J].數學的實踐與認識，2010（22）：99-106.

[2]項瀛，馬蘭，張兆寧.基于動態空域配置的航路調整問題研究[J].航空計算技術，2014（3）：23-26.

[3]戴德忠.臨時航線使用與管理初探[J].空運商務，2012（11）：4-8.

[4]許孟可.空域靈活使用的基本問題及對策研究[J].科技與創新，2015（16）：32-33.

[5]PRIETO A.Solutions within the Super Highway Project Allowing Integrated Use of Airspace of Both, Civil and Military Users[C]. Northern Ireland：7th AIAA ATIO Conference, 2nd CEIAT Int’l Conference on Innovation and Integration in Aero Sciences, 17th LTA Systems Tech Conference followed by 2nd TEOS Forum Belfast, 2007.

[6]李雄，徐肖豪.空中交通臨時航線評估方法研究[J].飛行力學，2011（1）：84-88.

[7]郝光，張殿業，馮勛省.多目標最短路徑模型及算法[J].西南交通大學學報，2007（5）：641-646.

[8]TIEN S L.A Route-Based Queuing Network Model for Air Traffic Flow Contingency Management[D].Texas：University of North Texas, 2011.

[9]李雄，徐肖豪，朱承元，等.基于幾何算法的空中交通臨時航線規劃[J].系統工程，2008（8）：37-40.

[10]邱慧，黃解宇，黃麗丹.管理運籌學中最短路問題的兩種算法研究[J].運城學院學報，2014（2）：89-91.

[11]龐素超，陳實.用動態規劃方法求解最短路問題[J].東北石油大學學報，2007（3）：118-120.

Research on the method of temporary route planning based on shortest path

Niu Jinfeng

（Air Traffic Management College of Civil Aviation University of China, TianJin 300300, China）

In order to solve the large-scale flight delay caused by traffic congestion in the air, this paper draws the network diagram according to the distribution of the route points on the route, and builds dynamic programming model, applies reverse algorithm to compute the shortest path in network map. The route is chosen as a temporary route for aircraft selection. Finally, a numerical example is used to solve the problem and the feasibility of the method is verified.

air traffic; traffic network; reverse algorithm; shortest route; temporary route

牛金鳳（1989— ），女，安徽宿州，碩士研究生；研究方向：空域規劃。