Finding K shortest looping paths with waiting time in a time-window network

Hsu Hao Yang, Yen Liang Chen

研究成果: 雜誌貢獻期刊論文同行評審

22 引文 斯高帕斯(Scopus)

摘要

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

指紋

深入研究「Finding K shortest looping paths with waiting time in a time-window network」主題。共同形成了獨特的指紋。

引用此