Updating Paths in Time-Varying Networks Given Arc Weight Changes

References

• Ahuja R., Magnanti T., Orlin J.Network Flows (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Bazaraa M., Langley J. A dual shortest path algorithm. SIAM J. Appl. Math. (1974) 26:496–501Crossref, Google Scholar
• Bellman R. On a routing problem. Quart. Appl. Math. (1958) 16:87–90Crossref, Google Scholar
• Beroggi G. A real-time routing model for hazardous materials. Eur. J. Oper. Res. (1994) 75:508–520Crossref, Google Scholar
• Bertsekas D. An auction algorithm for shortest paths. SIAM J. Optim. (1991) 1:425–447Crossref, Google Scholar
• Bertsekas D., Tsitsiklis J.Parallel and Distributed Computation: Numerical Methods (1989) (Prentice Hall, Inc., Upper Saddle River, NJ) Google Scholar
• Bertsekas D., Guerriero F., Musmanno R. Parallel asynchronous label-correcting methods for shortest paths. J. Optim. Theory Appl. (1996) 88:297–320Crossref, Google Scholar
• Catling I., Belcher P. Autoguide-route guidance in the United Kingdom. Proc. 1st Navigation Inform. Systems Conf. (VNIS ’89) (1989) (IEEE, Toronto, Canada) 467–473Crossref, Google Scholar
• Chabini I. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Res. Record (1998) 1645:170–175Crossref, Google Scholar
• Cooke K., Halsey E. The shortest route through a network with time-dependent intermodal transit times. J. Math. Anal. Appl. (1966) 14:493–498Crossref, Google Scholar
• Demetrescu C., Italiano G. Fully dynamic all pairs shortest paths with real edge weights. IEEE Sympos. Foundations Comput. Sci. (2001) Las Vegas, NVCrossref, Google Scholar
• Dionne R. Étude et Extension d’un Algorithme de Murchland. INFOR (1978) 16:132–146Google Scholar
• Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithms (2000) 34:251–281Crossref, Google Scholar
• Fujishige S. A note on the problem of updating shortest paths. Networks (1981) 11:317–319Crossref, Google Scholar
• Gallo G. Reoptimization procedures in shortest path problems. Rivista di Matematica per le Scienze Economiche e Sociali (1980) 3:3–13Crossref, Google Scholar
• Gallo G., Pallottino S. Shortest path methods: A unifying approach. Mathematical Programming Study (1986) 26(North-Holland, Amsterdam, The Netherlands) 38–64Crossref, Google Scholar
• Goto S., Sangiovanni-Vincentelli A. A new shortest path updating algorithm. Networks (1978) 8:341–372Crossref, Google Scholar
• Miller-Hooks E., Mahmassani H. Least expected time paths in stochastic, time-varying transportation networks. Transportation Sci. (2000) 34:198–215Link, Google Scholar
• Miller-Hooks E., Stock Patterson S. On solving quickest time problems in time-dependent and dynamic networks. J. Math. Model. Algorithms (2004) 3:39–71Crossref, Google Scholar
• Miller-Hooks E., Yang B. Impact of travel time models on quality of real-time routing instructions. Transportation Res. Record (2003) 1857:21–29Crossref, Google Scholar
• Murchland J. A fixed matrix method for all shortest distances in a directed graph and for the inverse problem. (1970) . Ph.D. thesis, University of Karlsruhe, Karlsruhe, GermanyGoogle Scholar
• Orda A., Rom R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. Association Comput. Machinery (1990) 37:607–625Crossref, Google Scholar
• Pallottino S. Shortest-path methods: Complexity, interrelations and new propositions. Networks (1984) 14:257–267Crossref, Google Scholar
• Pallottino S., Scutellà M. Dual algorithms for the shortest path tree problem. Networks (1997) 29:125–133Crossref, Google Scholar
• Pallottino S., Scutellà M., Marcotte P., Nguyen S. Shortest path algorithms in transportation models: Classical and innovative aspects. Equilibrium and Advanced Transportation Modeling (1998) (Kluwer Academic Publishers, Boston, MA) 245–281Crossref, Google Scholar
• Pallottino S., Scutellà M. A new algorithm for reoptimizing shortest paths when the arc costs change. Oper. Res. Lett. (2003) 31:149–160Crossref, Google Scholar
• Pape U. Implementation and efficiency of Moore-algorithms for the shortest route problem. Math. Programming (1974) 7:212–222Crossref, Google Scholar
• Ramalingam G., Reps T. An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms (1996) 21:267–305Crossref, Google Scholar
• Rodionov V. The parametric problem of shortest distances. U.S.S.R. Computational Math. Math. Phys. (1968) 8:336–343Crossref, Google Scholar
• Sparmann J. LISB route guidance and information system: First results of the field trial. Proc. 1st Navigation Inform. Systems Conf. (VNIS ’89) (1989) (IEEE, Toronto, Canada) 463–466Crossref, Google Scholar
• Yang B. Robust on-line routing in intelligent transportation systems. (2001) . Ph.D. thesis, Pennsylvania State University, University Park, PAGoogle Scholar
• Yang B., Miller-Hooks E. Adaptive routing considering delays due to signal operations. Transportation Res. B (2004) 38:385–413Crossref, Google Scholar
• Ziliaskopoulos A. Optimum path algorithms on multidimensional networks: Analysis and design, implementation and computational experience. (1994) . Ph.D. thesis, University of Texas, Austin, TXGoogle Scholar
• Ziliaskopoulos A., Mahmassani H. Time-dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications. Transportation Res. Record (1993) 1408:94–100Google Scholar