Time-Dependent, Label-Constrained Shortest Path Problems with Applications

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice-Hall, NJ) Google Scholar
• Barrett C., Jacob R., Marathe M. V. Formal language constrained path problems. SIAM J. Comput. (2001) 30(3):809–837Crossref, Google Scholar
• Bazaraa M. S., Jarvis J. J., Sherali H. D.Linear Programming and Network Flows (1990) 2nd ed(John Wiley and Sons, New York) Google Scholar
• Bertsekas D. P.Linear Network Optimization (1991) (MIT Press, Cambridge, MA) Google Scholar
• Cook K. L., Halsey E. The shortest route through a network with time-dependent intermodal transit times. J. Math. Anal. Appl. (1966) 14:493–498Crossref, Google Scholar
• Dijkstra E. W. A note on two problems in connection with graphs. Numerical Math. (1959) 1:269–271Crossref, Google Scholar
• Dreyfus S. E. An appraisal of some shortest path algorithms. Oper. Res. (1969) 17:395–412Link, Google Scholar
• Glover F., Klingman D., Phillips N. A new polynomially bounded shortest path algorithm. Oper. Res. (1985a) 33(1):65–73Link, Google Scholar
• Glover F., Klingman D., Phillips N., Schneider R. New polynomial shortest path algorithms and their computational attributes. Management Sci. (1985b) 31(9):1106–1128Link, Google Scholar
• Halpern H. J. Shortest route with time dependent length of edges and limited delay possibilities in nodes. Zeitschrift Oper. Res. (1977) 21:117–124Crossref, Google Scholar
• Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics (1968) SSC-4(2):100–107Crossref, Google Scholar
• Hassin R. Approximation schemes for the restricted shortest path problems. Math. Oper. Res. (1992) 17(1):36–42Link, Google Scholar
• Hopcroft J. E., Ullman J. D.Introduction to Automata Theory, Languages, and Computation (1979) (Addison-Wesley Publishing Company, Reading, MA) Google Scholar
• Jacob R., Marathe M., Nagel K. A computational study of routing algorithms for realistic transportation networks. (1998) . Los Alamos National Laboratory Report Series LA-UR-98-2249Google Scholar
• Kangwalklai S. Time dynamic label-constrained shortest path problems with application to TRANSIMS: A transportation planning system. (2000) . M.S. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VAGoogle Scholar
• Kaufman D. E., Smith R. L. Fastest paths in time-dependent networks for IVHS applications. IVHS J. (1993) 1:1–11Google Scholar
• Los Alamos National Laboratory TRansportation ANalysis SIMulation System (TRANSIMS) Version: TRANSIMS-LANL-1.0, NM. (1999) Google Scholar
• Los Alamos National Laboratory TRansportation ANalysis SIMulation System (TRANSIMS) Version: TRANSIMS-LANL-1.1, NM. (2000) Google Scholar
• Mendelzon A., Wood P. Finding regular simple paths in graph databases. SIAM J. Comput. (1995) 24(6):1235–Crossref, Google Scholar
• Orda A., Rom R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-lengths. J. Assoc. Comput. Machinery (1990) 37:607–625Crossref, 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
• Romeuf J.-F. Shortest path under rational constraint. Inform. Processing Lett. (1988) 28:245–248Crossref, Google Scholar
• Sedgewick R., Vitter J. S. Shortest paths in euclidean graphs. Algorithmica (1986) 1:31–48Crossref, Google Scholar
• Sherali H. D. On the equivalence between some shortest path algorithms. Oper. Res. Lett. (1991) 10:61–65Crossref, Google Scholar
• Sherali H. D., Ozbay K., Subramanian S. The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms. Networks (1998) 31:259–272Crossref, Google Scholar
• U.S. Department of Transportation TMIP: Data collection in the Portland, Oregon, metropolitan area case study. (1996) (Washington, D.C)Google Scholar