Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems

References

• Bellman R (1958) On a routing problem. Quart. Appl. Math. 16(1):87–90.Crossref, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, Google Scholar
• Chabini I (1998) Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Res. Rec. J. Transportation Res. Board 1645(1):170–175.Crossref, Google Scholar
• Cooke KL, Halsey E (1966) The shortest route through a network with time-dependent internodal transit times. J. Math. Anal. Appl. 14(3):493–498.Crossref, Google Scholar
• Dash S, Güunlüuk O, Lodi A, Tramontani A (2012) A time bucket formulation for the traveling salesman problem with time windows. INFORMS J. Comput. 24(1):132–147.Google Scholar
• Dean BC (2004) Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms. Rapport Technique (Massachusetts Institute of Technology, Cambridge, MA).Google Scholar
• Demiryurek U, Banaei-Kashani F, Shahabi C, Ranganathan A (2011) Online computation of fastest path in time-dependent spatial networks. Internat. Sympos. Spatial Temporal Databases (Springer, Berlin), 92–111.Crossref, Google Scholar
• Ding B, Yu JX, Qin L (2008) Finding time-dependent shortest paths over large graphs. Proc. 11th Internat. Conf. Extending Database Tech. Adv. Database Tech. (ACM, New York), 205–216.Google Scholar
• Figliozzi MA (2012) The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Res. Part E Logist. Transportation Rev. 48(3):616–636.Crossref, Google Scholar
• Ford LR, Fulkerson DR (1962) Flows in Networks (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Foschini L, Hershberger J, Suri S (2014) On the complexity of time-dependent shortest paths. Algorithmica 68(4):1075–1097.Crossref, Google Scholar
• Gunturi VMV, Joseph K, Shekhar S, Carley KM (2012) Information lifetime aware analysis for dynamic social networks. Technical report, University of Minnesota, Minneapolis.Google Scholar
• He E, Boland N, Nemhauser G, Savelsbergh M (2020) Time-dependent shortest path problems with penalties and limits on waiting. Optimization Online Eprint ID 2019–02–7083.Google Scholar
• Jabali O, Van Woensel T, De Kok AG (2012) Analysis of travel times and CO2 emissions in time-dependent vehicle routing. Production Oper. Management 21(6):1060–1074.Crossref, Google Scholar
• Kanoulas E, Du Y, Xia T, Zhang D (2006) Finding fastest paths on a road network with speed patterns. Proc. 22nd Internat. Conf. Data Engrg. (IEEE, Piscataway, NJ), 10.Google Scholar
• Li L, Wen H, Du X, Zhou X (2017) Minimal on-road time route scheduling on timedependent graphs. Proceedings of the VLDB Endowment 10(11):1274–1285.Crossref, Google Scholar
• Marshall L (2019) Private communication.Google Scholar
• Nachtigall K (1995) Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1):154–166.Crossref, Google Scholar
• Omer J, Poss M (2019) Time-dependent shortest paths with discounted waits. Networks 74(3):287–301.Crossref, Google Scholar
• Orda A, Rom R (1990) Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3):607–625.Crossref, Google Scholar
• Wang X, Regan AC (2002) Local truckload pickup and delivery with hard time window constraints. Transportation Research Part B: Methodological 36(2):97–112.Crossref, Google Scholar
• Wang X, Regan AC (2009) On the convergence of a new time window discretization method for the traveling salesman problem with time window constraints. Computers & Industrial Engineering 56(1):161–164.Crossref, Google Scholar