Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems

Edward Yuhang He (), Natashia Boland (), George Nemhauser () and Martin Savelsbergh ()
Additional contact information
Edward Yuhang He: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Natashia Boland: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
George Nemhauser: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Martin Savelsbergh: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 1086-1114

Abstract: Finding a shortest path in a network is a fundamental optimization problem. We focus on settings in which the travel time on an arc in the network depends on the time at which traversal of the arc begins. In such settings, reaching the destination as early as possible is not the only objective of interest. Minimizing the duration of the path, that is, the difference between the arrival time at the destination and the departure from the origin, and minimizing the travel time along the path from origin to destination, are also of interest. We introduce dynamic discretization discovery algorithms to efficiently solve such time-dependent shortest path problems with piecewise linear arc travel time functions. The algorithms operate on partially time-expanded networks in which arc costs represent lower bounds on the arc travel time over the subsequent time interval. A shortest path in this partially time-expanded network yields a lower bound on the value of an optimal path. Upper bounds are easily obtained as by-products of the lower bound calculations. The algorithms iteratively refine the discretization by exploiting breakpoints of the arc travel time functions. In addition to time discretization refinement, the algorithms permit time intervals to be eliminated, improving lower and upper bounds, until, in a finite number of iterations, optimality is proved. Computational experiments show that only a small fraction of breakpoints must be explored and that the fraction decreases as the length of the time horizon and the size of the network increases, making the algorithms highly efficient and scalable. Summary of Contribution: New data collection techniques have increased the availability and fidelity of time-dependent travel time information, making the time-dependent variant of the classic shortest path problem an extremely relevant problem in the field of operations research. This paper provides novel algorithms for the time-dependent shortest path problem with both the minimum duration and minimum travel time objectives, which aims to address the computational challenges faced by existing algorithms. A computational study shows that our new algorithm is indeed significantly more efficient than existing approaches.

Keywords: minimum duration paths; time-dependent travel times; fastest paths; time-expanded networks; time discretization; dynamic discretization discovery (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1084 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:2:p:1086-1114

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().