Optimization Online


Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems

Edward He (edwardhe***at***gatech.edu)
Natashia Boland (natashia.boland***at***isye.gatech.edu)
George Nemhauser (george.nemhauser***at***isye.gatech.edu)
Martin Savelsbergh (martin.savelsbergh***at***isye.gatech.edu)

Abstract: Finding a shortest path in a network is an iconic 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 sink as early as possible is not the only objective of interest. Minimizing the duration of the path, i.e., the difference between the arrival time at the sink and the departure from the depot, and minimizing the travel time along the path from source to sink, 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 byproducts 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.

Keywords: minimum duration paths, time-dependent travel times, fastest paths, time-expanded networks, time discretization, dynamic discretization discovery

Category 1: Network Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )


Download: [PDF]

Entry Submitted: 02/21/2019
Entry Accepted: 02/21/2019
Entry Last Modified: 03/20/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society