FASTEST PATHS IN TIME-DEPENDENT NETWORKS FOR INTELLIGENT VEHICLE-HIGHWAY SYSTEMS APPLICATION∗
- 1 January 1993
- journal article
- research article
- Published by Taylor & Francis in I V H S Journal
- Vol. 1 (1), 1-11
- https://doi.org/10.1080/10248079308903779
Abstract
We consider the problem of individual route guidance in an Intelligent Vehicle-Highway Systems (IVHS ) environment, based on time-dependent forecasts of link travel time. We propose a consistency condition which deterministic forecasts should be constrained to satisfy, and show that under consistency, the time-dependent fastest path can be calculated with exactly the same computational complexity as for static fastest paths, regardless of the time index set. In particular, consistency reduces computational complexity by O(T) in a T-period discrete time problem. We also comment on the stochastic fastest path problem, suggesting modifications to a general-case algorithm from the literature.Keywords
This publication has 8 references indexed in Scilit:
- Shortest-path and minimum-delay algorithms in networks with time-dependent edge-lengthJournal of the ACM, 1990
- Shortest path algorithmsAnnals of Operations Research, 1988
- The Fastest Path through a Network with Random Time-Dependent Travel TimesTransportation Science, 1986
- Path Preferences and Optimal Paths in Probabilistic NetworksTransportation Science, 1985
- Shortest route with time dependent length of edges and limited delay possibilities in nodesMathematical Methods of Operations Research, 1977
- An Appraisal of Some Shortest-Path AlgorithmsOperations Research, 1969
- The shortest route through a network with time-dependent internodal transit timesJournal of Mathematical Analysis and Applications, 1966
- A note on two problems in connexion with graphsNumerische Mathematik, 1959