• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus
  • Indexed by Core Journals of China, Chinese S&T Journal Citation Reports
  • Chinese S&T Journal Citation Reports
  • Chinese Science Citation Database
Volume 27 Issue 1
Jan.  2014
Turn off MathJax
Article Contents
Journal of Southwest Jiaotong University  > 2014  >  27(1): 153-159.
XU Tao, DING Xiaolu, LI Jianfu. K-Multiple Constrained Shortest Paths Problem for Connecting Path Search in International Flight Path Network[J]. Journal of Southwest Jiaotong University, 2014, 27(1): 153-159. doi: 10.3969/j.issn.0258-2724.2014.01.024
Citation: XU Tao, DING Xiaolu, LI Jianfu. K-Multiple Constrained Shortest Paths Problem for Connecting Path Search in International Flight Path Network[J]. Journal of Southwest Jiaotong University, 2014, 27(1): 153-159. doi: 10.3969/j.issn.0258-2724.2014.01.024
shu

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

doi: 10.3969/j.issn.0258-2724.2014.01.024
  • Received Date: 05 Jan 2013
  • Publish Date: 25 Jan 2014
    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.

     

    • FullText(HTML)
  • loading
    • References(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.
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML
    Article views(847) PDF downloads(504) Cited by()
    Proportional views
    Related

    Copyright © 2009 Journal of Southwest Jiaotong University

    Address: RM449 & 451, Administrative Building, Xipu Campus, Southwest Jiaotong University Western Hi-tech Zone, Chengdu, Sichuan 611756, P. R. China

    Tel: 028-66367562Fax: 028-66366552Email: xbz@home.swjtu.edu.cn

    Supported by: Beijing Renhe Information Technology Co. Ltd  support: info@rhhz.net

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return