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

牛金鳳

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

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

牛金鳳

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

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

空中交通；交通網(wǎng)絡(luò)；逆序算法；最短路徑；臨時航線

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

1 空中交通網(wǎng)絡(luò)

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

圖1 空中交通網(wǎng)絡(luò)

2 動態(tài)規(guī)劃模型的建立與求解

2.1 動態(tài)規(guī)劃模型的建立

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

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

狀態(tài)變量Sk：第k段航路的長度。

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

狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk+xk。

最優(yōu)指標(biāo)函數(shù)fk(Sk)：當(dāng)所選航路段為Sk時，選擇第k-1個航路段得到的最短路徑。

基本方程：

2.2 模型求解方法

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

從終點(diǎn)向始點(diǎn)逐階段逆推，找出各點(diǎn)到終點(diǎn)的最短路徑，當(dāng)逆推到始點(diǎn)時，也即找到了從始點(diǎn)到終點(diǎn)的全過程的最短路，最終求出全過程的最優(yōu)策略。

3 算例分析

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

圖2 參考航路

圖3 算例網(wǎng)絡(luò)

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

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

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

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

4 結(jié)語

本文根據(jù)航路上航路點(diǎn)的分布情況構(gòu)造出空中交通網(wǎng)絡(luò)，運(yùn)用運(yùn)籌學(xué)中的動態(tài)規(guī)劃方法建立模型，采用逆序算法求出最短路徑，本文首先根據(jù)空中航路點(diǎn)的分布情況建立空中交通網(wǎng)絡(luò)，把空中交通路徑可視化展現(xiàn)出來，更好地分析空中交通奠定基礎(chǔ)，然后采用動態(tài)規(guī)劃中的逆序算法求出最短路徑，一方面可以為流量較大的航路分流，而且為臨時航線的建立提供一種理論依據(jù)。但是本文僅限于理論研究，下一步工作應(yīng)該根據(jù)真實(shí)情況結(jié)合航路圖中的航路點(diǎn)來建立交通網(wǎng)絡(luò)，求出一條有實(shí)用價值的臨時航線。

[1]萬莉莉，田勇，葉博嘉.基于多目標(biāo)優(yōu)化的改航策略研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2010（22）：99-106.

[2]項(xiàng)瀛，馬蘭，張兆寧.基于動態(tài)空域配置的航路調(diào)整問題研究[J].航空計(jì)算技術(shù)，2014（3）：23-26.

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

[4]許孟可.空域靈活使用的基本問題及對策研究[J].科技與創(chuàng)新，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].飛行力學(xué)，2011（1）：84-88.

[7]郝光，張殿業(yè)，馮勛省.多目標(biāo)最短路徑模型及算法[J].西南交通大學(xué)學(xué)報，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]李雄，徐肖豪，朱承元，等.基于幾何算法的空中交通臨時航線規(guī)劃[J].系統(tǒng)工程，2008（8）：37-40.

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

[11]龐素超，陳實(shí).用動態(tài)規(guī)劃方法求解最短路問題[J].東北石油大學(xué)學(xué)報，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— ），女，安徽宿州，碩士研究生；研究方向：空域規(guī)劃。