摘要
A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time-window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK2 V1 3), where r is the number of different windows of a node and V1 is the number of nodes in the original network.
原文 | ???core.languages.en_GB??? |
---|---|
頁(從 - 到) | 458-465 |
頁數 | 8 |
期刊 | Applied Mathematical Modelling |
卷 | 30 |
發行號 | 5 |
DOIs | |
出版狀態 | 已出版 - 5月 2006 |