Edward He – Optimization Online

Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems

Published: 2019/02/21, Updated: 2022/08/06

Network Optimization, Transportation dynamic discretization discovery, fastest paths, minimum duration paths, time dependent travel times, time discretization, time-expanded networks

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. … Read more

Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting

Published: 2019/02/21, Updated: 2020/04/11

Network Optimization, Transportation complexity, shortest path, time-dependent travel time, time-expanded network

Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the … Read more