Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6893119 | Computers & Operations Research | 2013 | 8 Pages |
Abstract
We study a new variant of the time-constrained shortest path problem (TCSPP), that is, the K shortest paths problem in a time-schedule network with constraints on arcs. In such networks, each arc has a list of pre-specified departure times, and traversal along the arc can only take place at one of those departure times. We develop a solution algorithm that finds the K shortest looping paths in O(mlog(nr)+Kmr2η) time, where n is the number of nodes, m is the number of arcs, r is the maximum number of departure times on an arc, and η is the maximum in-degree of a node. Computational experiments show that our algorithm outperforms existing ones adapted to solve the same problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Wen Jin, Shuiping Chen, Hai Jiang,