国际航线网络联程路径搜索的KMCSP问题研究

徐涛; 丁晓璐; 李建伏

doi:10.3969/j.issn.0258-2724.2014.01.024

国际航线网络联程路径搜索的KMCSP问题研究

doi: 10.3969/j.issn.0258-2724.2014.01.024

徐涛^1,2,
丁晓璐^1,2,
李建伏¹

基金项目:

中国民用航空局科技项目（MHRD201007）

中央高校基本科研业务费用中国民航大学专项基金资助项目（ZXH2011B003）

计量
- 文章访问数: 847
- HTML全文浏览量: 54
- PDF下载量: 504
- 被引次数: 0
出版历程
- 收稿日期: 2013-01-05
- 刊出日期: 2014-01-25

K-Multiple Constrained Shortest Paths Problem for Connecting Path Search in International Flight Path Network

摘要

摘要: 为了解决在国际航线网络中查找联程路径时间花费较长的问题，针对国际航线网络联程路径搜索的特点，借助于A*算法的启发式策略，在对Yen算法改进的基础上，提出一种新的解决多约束条件下K条最短路径（K-multiple constrained shortest paths，KMCSP）问题的算法，即约束Yen*算法.在中转次数约束和特定中转点约束条件下，对国际航线网络进行了测试实验，结果表明：与约束Yen算法相比，约束Yen*算法的搜索效率提高了2.98倍，平均运行时间减少了78.3%，算法的搜索规模缩小了86%，且波动范围小.约束Yen*算法适用于多约束条件下快速求解国际航线网络联程路径搜索问题.
- 航线 /
- 联程路径搜索 /
- KMCSP问题 /
- Yen*算法 /
- A*算法 /
- 启发式策略
Abstract: In order to solve the problem that the connecting path search method takes long time in international flight path network, according to the features of the connecting path search in the network, a constrained Yen* algorithm, which adopts the heuristic strategy of A* algorithm and is based on the Yen algorithm, is proposed to solve the K-multiple constrained shortest paths (KMCSP) problem. The proposed algorithm is tested in the international flight path network under the constraints of transfer times and a given transferring node. The results show that compared with the constrained Yen algorithm, the constrained Yen* algorithm improves the searching efficiency by 2.98 times, reduces the average running time by 78.3%, and decrease the search space by 86% with a small fluctuation range. Therefore, the constrained Yen* algorithm can be used to quickly solve the multiple constrained connecting path problem in international flight path network.
- flight path /
- connecting path search /
- KMCSP problem /
- Yen* algorithm /
- A* algorithm /
- heuristic strategy

HTML全文

参考文献(15)

CHEN S, NAHRESTEDT K. On finding multi-constrained paths[C]//Proceedings of the ICC'98 Conference.[S.l.]: IEEE, 1998: 874-879.

ⅡT S V, PANDIT A K. A* prune modified algorithm in video compression[J]. Ubiquitous Computing and Communication Journal, 2008, 3(5): 49-52.

MOHSEN M, HASSAN D. Network reduction for the acyclic constrained shortest path problem[J]. European Journal of Operational Research, 1992, 63(1):124-132.

邹永贵, 魏来. 带多约束条件的最优路径选择算法研究[J]. 计算机应用, 2008, 28(5): 1101-1104. ZOU Yonggui, WEI Lai. Optimal path algorithm with multi-constrained condition[J]. Computer Applica-tions, 2008, 28(5): 1101-1104.

SUN Q, WANG G. Study on the performance of the A* prune QoS routing algorithm for intelligent optical networks and its improvements[J]. China Universities of Posts and Telecommunications, 2006, 13(3): 65-70.

CLIMACO J, CRAVEIRINHA J, PASCOAL M. A bicriterion approach for routing problems in multimedia networks[J]. Networks, 2003, 41(4): 206-220.

AZEVEDO J A, MADEIRA J J E R S, MARTINS E Q V, et al. A shortest paths ranking algorithm[C]//Proceedings of the Annual Conference AIRO'90, Models and Methods for Decision Support.[S.l.]: Operational Research Society of Italy, 1990, 85(2): 1001-1011.

ZHANG Z, ZHAO J. Multi-constraint-pruning: an algorithm for finding K shortest paths subject to multiple constraints[C]//Proceedings of APCC'2008. Tokyo: IEEE, 2008: 1-5.

LIU G, RAMAKRISHNAM R. A* prune: an algorithm for finding K shortest paths subject to multiple constraints[C]//Proceedings of INFOCOM'2001. Anchorage: IEEE, 2001: 743-749.

NING S. K constrained shortest path problem[J]. IEEE Transactions on Automation Science and Engineering, 2010, 1(7): 15-23.

ZIJPP N J, CATALANO S F. Path enumeration by finding the constrained K-shortest paths[J]. Transportation Research Part B, 2005, 39(6): 545-563.

YEN J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716.

MARTINS E Q V, PASCOAL M M B, SANTOS J L E. A new algorithm for ranking loopless paths[R]. Coimbra: Center for Informatics and Systems of the University of Coimbra, 1997.

MARTINS E Q V, PASCOAL M M B. A new implementation of Yen's ranking loopless paths algorithm[J]. A Quarterly Journal of the Belgian, French, Italian Operations Research Societies, 2003, 1(2): 121-133.

HERSHBERGER J, MAXEL M, SURI S. Finding the K shortest simple paths: a new algorithm and its implementation[J]. ACM Transactions on Algorithms, 2007, 3(4): 45-1-45-19.

施引文献

附加材料(0)

访问统计

点击查看大图

计量

文章访问数: 847
HTML全文浏览量: 54
PDF下载量: 504
被引次数: 0

国际航线网络联程路径搜索的KMCSP问题研究

doi: 10.3969/j.issn.0258-2724.2014.01.024

计量

出版历程

K-Multiple Constrained Shortest Paths Problem for Connecting Path Search in International Flight Path Network

计量

出版历程

目录