The problem of computing minimum-time paths from all nodes to one destination node, for all possible departure times, in continuous-time dynamic networks with piecewise linear link travel-time functions is considered. Two types of algorithms to solve this problem are presented: a continuous-time label-correcting algorithm and an algorithm that determines optimal minimum travel-time functions in decreasing order of departure times. The algorithms are valid in networks in which “first in, first out” holds and does not necessarily hold. Computer implementations of these algorithms were developed and are available. It is demonstrated that the algorithms have modest computational time and memory requirements. The decreasing order of time algorithm generally requires less running time than the label-correcting algorithm, which is comparatively easier to implement.
Computing Fastest Paths in Continuous-Time Dynamic Networks with Piecewise Linear Link Travel-Time Functions
Transportation Research Record: Journal of the Transportation Research Board
2001-01-01
Article (Journal)
Electronic Resource
English
British Library Conference Proceedings | 2001
|Bitwise Algorithm for Fastest Paths in Time-Dependent Networks
Online Contents | 2001
|Bitwise Algorithm for Fastest Paths in Time-Dependent Networks
British Library Conference Proceedings | 2001
|Bitwise Algorithm for Fastest Paths in Time-Dependent Networks
Transportation Research Record | 2001
|