A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs. Issue 2 (June 2017)

• Record Type: Journal Article
• Authors: Guo, Jianyuan; Jia, Limin
• Is Part Of: Journal of algorithms & computational technology. Volume 11:Issue 2(2017)
• Page Start: 170
• Page End: 177
• Publication Date: 2017-06
• Subjects: K shortest paths -- time-schedule network -- constraints on arcs -- parallel arcs; Computer algorithms -- Periodicals; Numerical calculations -- Periodicals; Computer algorithms; Numerical calculations; Periodicals; 518.1
• DOI: 10.1177/1748301816680470
• Languages: English
• ISSNs: 1748-3018

Abstract

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 isO ( | A | log r + K 2 | A | + K 2 | N | log ( K | N | ) ), wherer is the maximum number of departure times from a node, | A | is the number of arcs in network, and| N | 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.