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 

出　　处：《Science China(Technological Sciences)》2010年第12期3258-3263,共6页中国科学（技术科学英文版）

基　　金：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

摘　　要：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.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.

关 键 词：CONSTRAINED shortest PATH DETERMINISTIC RANDOM WALK optimization 

分 类 号：TB114.1[理学—运筹学与控制论]