Solving the constrained shortest path problem using random search strategy

作     者：LI KePing, GAO ZiYou , TANG Tao & YANG LiXing State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044, China 

作者机构：State Key Laboratory of Rail Traffic Control and Safety Beijing Jiaotong University Beijing China 

出 版 物：《Science China(Technological Sciences)》 (中国科学（技术科学英文版）)

年 卷 期：2010年第53卷第12期

页      面：3258-3263页

核心收录：

学科分类：0810[工学-信息与通信工程] 07[理学] 0805[工学-材料科学与工程（可授工学、理学学位）] 0701[理学-数学] 0702[理学-物理学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China (Grant Nos. 60634010 and 60776829) the State Key Laboratory of Rail Traffic Control and Safety (Contract No. RCS2008ZZ001), Beijing Jiaotong University 

主　　题：constrained shortest path deterministic random walk optimization 

摘      要：In this paper, we propose an improved walk search strategy to solve the constrained shortest path problem. The proposed search strategy is a local search algorithm which explores a network by walker navigating through the network. In order to analyze and evaluate the proposed search strategy, we present the results of three computational studies in which the proposed search algorithm is tested. Moreover, we compare the proposed algorithm with the ant colony algorithm and k shortest paths algorithm. The analysis and comparison results demonstrate that the proposed algorithm is an effective tool for solving the constrained shortest path problem. It can not only be used to solve the optimization problem on a larger network, but also is superior to the ant colony algorithm in terms of the solution time and optimal paths.