Transportation Research Record Journal of the Transportation Research Board · 1998 · 332 citations · 12 references
ComputingComputer ScienceTransportation PlanningAlgorithmsTransportationTransportation EngineeringIntelligent Transportation SystemsNetwork OptimizationShortest Path AlgorithmsTransportation ModelsTransportation NetworksTransportation ProblemsDynamic Shortest PathsPath ComputationShortest Path ProblemsShortest PathsTransportation ApplicationsTransportation System Optimization
Dynamic transportation systems rely on efficient algorithms for all‑to‑one dynamic shortest paths and one‑to‑all fastest paths, which are central to intelligent transportation system models. The study addresses a 30‑year‑old challenge by proposing a new, simple algorithm to compute all‑to‑one shortest paths in discrete dynamic networks. The authors develop an optimal‑run‑time algorithm that computes all‑to‑one shortest paths for every departure interval in discrete dynamic networks. They prove the algorithm achieves optimal run‑time complexity, confirm its efficiency through experiments, and show it offers major benefits for real‑time management of large‑scale ITSs.
A solution is provided for what appears to be a 30-year-old problem dealing with the discovery of the most efficient algorithms possible to compute all-to-one shortest paths in discrete dynamic networks. This problem lies at the heart of efficient solution approaches to dynamic network models that arise in dynamic transportation systems, such as intelligent transportation systems (ITS) applications. The all-to-one dynamic shortest paths problem and the one-to-all fastest paths problems are studied. Early results are revisited and new properties are established. The complexity of these problems is established, and solution algorithms optimal for run time are developed. A new and simple solution algorithm is proposed for all-to-one, all departure time intervals, shortest paths problems. It is proved, theoretically, that the new solution algorithm has an optimal run time complexity that equals the complexity of the problem. Computer implementations and experimental evaluations of various solution algorithms support the theoretical findings and demonstrate the efficiency of the proposed solution algorithm. The findings should be of major benefit to research and development activities in the field of dynamic management, in particular real-time management, and to control of large-scale ITSs.
12
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Transportation Research Record
Anne Vingaard Olesen, Erik Kjems, Kristian Hegner Reinau et al. · 2016 · 11.4K citations
An Appraisal of Some Shortest-Path Algorithms
Stuart E. Dreyfus · Operations Research · 1969 · 997 citations
Giorgio Gallo, Stefano Pallottino · Annals of Operations Research · 1988 · 350 citations