  


Dynamic Discretization Discovery Algorithms for TimeDependent Shortest Path Problems
Edward He (edwardhegatech.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 timedependent shortest path problems with piecewise linear arc travel time functions. The algorithms operate on partially timeexpanded networks in which arc costs represent lower bounds on the arc travel time over the subsequent time interval. A shortest path in this partially timeexpanded 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, timedependent travel times, fastest paths, timeexpanded networks, time discretization, dynamic discretization discovery Category 1: Network Optimization Category 2: Applications  OR and Management Sciences (Transportation ) Citation: Download: [PDF] Entry Submitted: 02/21/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  