Improvement and simulation of K-shortest-paths algorithm in international flight route network

doi:10.11772/j.issn.1001-9081.2014.04.1192

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (4): 1192-1195.DOI: 10.11772/j.issn.1001-9081.2014.04.1192

Previous Articles Next Articles

Improvement and simulation of K-shortest-paths algorithm in international flight route network

HU Xin¹,XU Tao¹,²,DING Xialu²,LI Jianfu²

1. Information Technology Research Base, Civil Aviation University of China, Tianjin 300300, China
2. College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China

Received:2013-10-09 Revised:2013-12-09 Online:2014-04-29 Published:2014-04-01
Contact: HU Xin

国际航线网络中K条最短路径算法改进与仿真

胡欣¹,徐涛¹,²,丁晓璐²,李建伏²

1. 中国民航大学中国民航信息技术科研基地,天津 300300;
2. 中国民航大学计算机科学与技术学院,天津 300300

通讯作者: 胡欣
作者简介:胡欣(1984-),女,江西鄱阳人,实习研究员,硕士,主要研究方向:交通信息工程及控制;
徐涛(1962-),男,重庆人,教授, CCF会员,主要研究方向:民航信息系统、智能信息处理;
丁晓璐(1988-),女,河南濮阳人,硕士研究生,主要研究方向:民航信息系统;
李建伏(1979-),女,河北沧州人,讲师,博士,主要研究方向:民航信息系统、人工智能。
基金资助:
中国民用航空局科技项目;2013年度中国民航大学预研重大项目

Abstract

Abstract:

K-Shortest-Paths (KSP) problem is the optimization issue in international flight route network. With the analysis on the international flight route network and KSP algorithm, the typical Yen algorithm solve KSP problem was investigated. To resolve the problem that Yen algorithm occupied much time in solving the candidate paths, an improved Yen algorithm was proposed. The improved Yen algorithm was set up by using the heuristic strategy of A* algorithm, which reduced the time to generate candidate paths, thereby, the search efficiency was improved and the search scale was reduced. The simulation results of international flight route network example show that the improved Yen algorithm can quickly solve KSP problem in international flight route network. Compared with the Yen algorithm, the efficiency of the proposed algorithm is increased by 75.19%, so it can provide decision support for international flight route optimization.

摘要：

K条最短路径(KSP)问题是国际航线网络实际路径优化问题。通过对航线网络特征与K条最短路径算法的分析，研究了解决KSP问题的典型Yen算法。针对Yen算法求解候选路径占用大量运算时间的问题，提出一种改进Yen算法。改进Yen算法通过借助A*算法的启发式策略，减少了产生候选航线路径的时间，从而提高了算法的搜索效率并减小了算法搜索的规模。通过对国际航线网络实例的仿真，实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题;同时，与Yen算法相比，运算效率提升了75.19%以上，能够为航线路径优化提供决策支持。

CLC Number:

TP301

HU Xin XU Tao DING Xialu LI Jianfu. Improvement and simulation of K-shortest-paths algorithm in international flight route network[J]. Journal of Computer Applications, 2014, 34(4): 1192-1195.

胡欣徐涛丁晓璐李建伏. 国际航线网络中K条最短路径算法改进与仿真[J]. 计算机应用, 2014, 34(4): 1192-1195.

References

［1］LU F. Shortest path algorithms: taxonomy and advance in research ［J］. Acta Geodaetica et Cartographica Sinica, 2001, 30(3): 269-275. (陆锋. 最短路径算法:分类体系与研究进展［J］.测绘学报,2001,30(3):269-275.)
［2］GODSIL C, ROYEL G F. Algebraic graph theory ［M］. Berlin: Springer-Verlag, 2004.
［3］DIAS L C, CLIMACO J N. Shortest path problems with partial information: models and algorithms for detecting dominance ［J］. European Journal of Operation Research, 2000, 121(1):16-31.
［4］BAI Y, HU P, XIA L, et al.A kth-shortest path algorithm based on k-1 shortest paths ［J］. Geomatics and Information Science of Wuhan University, 2009, 34(4):492-494. (白轶多,胡鹏,夏兰芳,等.关于k次短路径问题的分析与求解［J］.武汉大学学报,2009,34(4):492-494.)
［5］HOFFMAN W, PAVLEY R. A method of solution of the Nth best path problem ［J］. Journal of the ACM, 1959, 6(4): 506-514.
［6］WANG Z, HAN W, LI Y. Shortest path problem with multiple shortest paths ［J］. Journal of Harbin Institute of Technology, 2010, 42(9): 1428-1431. (王志坚,韩伟一,李一军.具有多条最短路径的最短路问题［J］.哈尔滨工业大学学报,2010,42(9):1428-1431.)
［7］KANG T, ZHANG X, WANG Z, et al.Algorithm for shortest path of multi-objectives based on k short path algorithm ［J］. Journal of Changzhou Institute of Technology, 2011, 24(3): 25-28. (康太平,张晓刚,王宗峰,等.基于k短路径算法的多目标最短路径算法［J］.常州工学院学报,2011,24(3):25-28.)
［8］MA X, LIU Q. A shuffled frog leaping algorithm for k-shortest paths problem［J］. Information and Control, 2011, 40(5): 614-618. (马炫,刘庆.求解k条最短路径问题的混合蛙跳算法［J］.信息与控制,2011,40(5):614-618.)
［9］GAO S, LU F. The kth shortest path algorithms: accuracy and efficiency evaluation ［J］. Journal of Image and Graphics, 2009, 14(8): 1677-1683. (高松,陆峰.K则最短路径算法效率与精度评估［J］.中国图象图形学报,2009,14(8):1677-1683.)
［10］YEN J Y. Finding the K shortest loopless paths in a network ［J］. Management Science, 1971, 17(11): 712-716.
［11］MARTINS E Q V, PASCOAL M M B, SANTOS J L E. A new algorithm for ranking loopless paths ［R］. Coimbra, Portugal: Center for Informatics and Systems of the University of Coimbra, 1997.
［12］MARTINS E Q V, PASCOAL M M B. A new implementation of Yen's ranking loopless paths algorithm ［J］. Quarterly Journal of the Belgian, French, Italian Opertaions Research Societies, 2000, 1(2):121-134.
［13］HERSHBERGER J, MAXEL M, SUR S. Finding the K shortestsimple paths: a new algorithm and its implementation ［J］. ACM Transactions on Algorithms, 2007, 3(4): 45-es.
［14］NILSSON N J. Artificial intelligence: a new synthesis ［M］. SanFrancisco: Morgan Kaufmann Publishers Inc., 2000.

[1]	. YOLOv5s-MRD: an efficient fire and smoke detection algorithm for complex scenarios based on YOLOv5s [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	Yawei HUANG, Xuezhong QIAN, Wei SONG. Improved differential evolution algorithm based on dual-archive population size adaptive method [J]. Journal of Computer Applications, 2024, 44(12): 3844-3853.
[3]	Hongru JIANG, Wei FANG. Survey of application of deep learning in meteorological data correction [J]. Journal of Computer Applications, 2024, 44(12): 3930-3940.
[4]	Qiye ZHANG, Xinrui ZENG. Efficient active-set method for support vector data description problem with Gaussian kernel [J]. Journal of Computer Applications, 2024, 44(12): 3808-3814.
[5]	. Improvement method of heuristic vehicle routing algorithm based on constrained spectral clustering [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	. Path planning of multi-UAV formation based on improved artificial potential field method [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	. Dual-population dual-stage evolutionary algorithm for complex constrained multi-objective optimization problems [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	Qin LENG, Zhengyuan MAO. Two echelon location-routing optimization considering facility sizing decision [J]. Journal of Computer Applications, 2024, 44(11): 3513-3520.
[9]	Qingyuan PENG, Xiaofeng WANG, Junxia WANG, Yingying HUA, Ao TANG, Fei HE. Review of phase transition in satisfiability problems [J]. Journal of Computer Applications, 2024, 44(11): 3503-3512.
[10]	Jie HUANG, Ruizi WU, Junli LI. Efficient adaptive robustness optimization algorithm for complex networks [J]. Journal of Computer Applications, 2024, 44(11): 3530-3539.
[11]	Renke SUN, Zhiyu HUANGFU, Hu CHEN, Zhongnian LI, Xinzheng XU. Survey of neural architecture search [J]. Journal of Computer Applications, 2024, 44(10): 2983-2994.
[12]	Antai SUN, Ye LIU, Dongmei XU. Dynamic surface asymptotic compensation algorithm for multi-agent systems [J]. Journal of Computer Applications, 2024, 44(10): 3151-3157.
[13]	Chaoying YAN, Ziyi ZHANG, Yingnan QU, Qiuyu LI, Dixiang ZHENG, Lijun SUN. Double auction carbon trading based on consortium blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3240-3245.
[14]	. Dung beetle optimizer algorithm with restricted reverse learning and Cauchy-Gauss variation [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	Guanglei YAO, Juxia XIONG, Guowu YANG. Flower pollination algorithm based on neural network optimization [J]. Journal of Computer Applications, 2024, 44(9): 2829-2837.

Improvement and simulation of K-shortest-paths algorithm in international flight route network

国际航线网络中K条最短路径算法改进与仿真

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics