国际航线网络中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-01 发布日期:2014-04-29
通讯作者: 胡欣
作者简介:胡欣(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-01 Published:2014-04-29
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]	李文霞, 刘林忠, 代存杰, 李玉. 基于多种群组合策略的人工蜂群算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3113-3119.
[2]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[3]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[4]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[5]	邹复民, 罗思杰, 陈志辉, 廖律超. 基于轨迹数据的出租车交接班时空分布识别方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3376-3384.
[6]	肖智豪胡志华朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0.
[7]	赖自成, 张玉萍, 马燕. 基于门控图卷积神经网络的有机化学反应预测[J]. 计算机应用, 2021, 41(10): 3070-3074.
[8]	沙林秀，聂凡，高倩，孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0.
[9]	董永峰孙跃华高立超韩鹏季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0.
[10]	李大海刘庆腾艾志刚王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0.
[11]	朱诚潘旭华张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0.
[12]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[13]	杨杰张名扬芮晓彬王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0.
[14]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[15]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics