A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs

被引：4
作者：
Guo, Jianyuan [1 ,2 ]
Jia, Limin [2 ,3 ]
机构：
[1] Beijing Jiaotong Univ, Sch Traff & Transportat, Beijing, Peoples R China
[2] Beijing Jiaotong Univ, Beijing Res Ctr Urban Traff Informat Sensing & Se, Beijing, Peoples R China
[3] Beijing Jiaotong Univ, State Key Lab Rail Traff Control & Safety, Beijing 100044, Peoples R China
来源：
JOURNAL OF ALGORITHMS & COMPUTATIONAL TECHNOLOGY | 2017年 / 11卷 / 02期
关键词：
K shortest paths; time-schedule network; constraints on arcs; parallel arcs;
D O I：
10.1177/1748301816680470
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Time-schedule network with constraints on arcs (TSNCA) means network with a list of pre-defined departure times for each arc. Compared to past research on finding the K shortest paths in TSNCA, the algorithm in this paper is suitable for networks having parallel arcs with the same direction between two nodes. A node label algorithm for finding the K shortest paths between two nodes is proposed. Temporal-arcs are put into the labels of nodes and arranged by ascending order. The number of temporal-arcs is limited to K in every label of node to improve the effectiveness of the algorithm. The complexity of this algorithm is O((vertical bar A vertical bar log r+ K-2 vertical bar A vertical bar +K-2 vertical bar N vertical bar logdK vertical bar N vertical bar)), where r is the maximum number of departure times from a node, vertical bar A vertical bar is the number of arcs in network, and vertical bar N vertical bar is the number of nodes in network. Experiments are carried out on major part of real urban mass transit network in Beijing, China. The result proves that the algorithm is effective and practical.
引用
收藏
页码：170 / 177
页数：8
相关论文
共 20 条
  • [1] Brander A.W., Sinclair M.C., A comparative study of k-shortest path algorithms, Performance Engineering of Computer and Telecommunications Systems, pp. 370-379, (1997)
  • [2] Hoffman W., Pavley R., A method for the solution of the Nth best path problem, J Assoc Comput Mach, 6, pp. 506-514, (1959)
  • [3] Yen J.Y., Finding the k shortest loopless paths in a network, Manag Sci, 17, pp. 712-716, (1971)
  • [4] Eugene L., Lawler a procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem, Manag Sci, 18, pp. 401-405, (1972)
  • [5] Katoh N., Ibaraki T., Mine H., An efficient algorithm for k shortest simple paths, Networks, 12, pp. 411-427, (1982)
  • [6] Martins E., An algorithm for ranking paths that may contain cycles, Eur J Oper Res, 18, pp. 123-130, (1984)
  • [7] Gotthilf Z., Lewenstein M., Improved algorithms for the k simple shortest paths and the replacement paths problems, Informat Process Lett, 109, pp. 352-355, (2009)
  • [8] Sedeno-Noda A., An efficient time and space K point-to-point shortest simple paths algorithm, Appl Math Comput, 218, pp. 10244-10257, (2012)
  • [9] Chen Y.L., Tang K., Minimum time paths in a network with mixed time constraints, Comput Oper Res, 25, pp. 793-805, (1998)
  • [10] Van Der Zijpp N.J., Fiorenzo Catalano S., Path enumeration by finding the constrained K-shortest paths, Transport Res B, 39, pp. 545-563, (2005)
12