基于最短路径的临时航线规划方法研究

牛金凤

（中国民航大学空中交通管理学院 天津 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— ），女，安徽宿州，硕士研究生；研究方向：空域规划。