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

doi:10.11772/j.issn.1001-9081.2014.04.1192

计算机应用 ›› 2014, Vol. 34 ›› Issue (4): 1192-1195.DOI: 10.11772/j.issn.1001-9081.2014.04.1192

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

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

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

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

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

摘要/Abstract

摘要：

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

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.

中图分类号:

TP301

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

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.

参考文献

［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的复杂场景下高效烟火检测算法——YOLOv5s-MRD[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	黄亚伟, 钱雪忠, 宋威. 基于双档案种群大小自适应方法的改进差分进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3844-3853.
[3]	蒋鸿儒, 方巍. 深度学习在气象数据订正中的应用综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3930-3940.
[4]	张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3808-3814.
[5]	罗蒙高超王震. 基于带约束谱聚类的启发式车辆路径规划算法优化方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[6]	曹晓意罗煦琼李景贺恩锋. 改进人工势场法下的多无人机编队路径规划方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	袁志超杨磊田井林魏晓威李康顺. 面向复杂约束多目标优化问题的双种群双阶段进化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	冷琴, 毛政元. 考虑设施规模决策的两级选址-路径优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3513-3520.
[9]	彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.
[10]	黄杰, 武瑞梓, 李均利. 高效的自适应复杂网络鲁棒性优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3530-3539.
[11]	孙仁科, 皇甫志宇, 陈虎, 李仲年, 许新征. 神经架构搜索综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 2983-2994.
[12]	孙安泰, 刘烨, 徐冬梅. 多智能体系统的动态面渐近补偿算法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3151-3157.
[13]	颜超英, 张紫仪, 曲映楠, 李秋禹, 郑地翔, 孙丽珺. 基于联盟链的双向拍卖碳交易[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3240-3245.
[14]	杨志龙邹德旋李灿邵莹莹马乐杰. 融入限制反向学习与柯西-高斯变异的蜣螂优化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics