Optimization Online


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

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: 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 nodes. We show that some cases are NP-hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or is constrained, and on the magnitude of the penalty/waiting limit parameter.

Keywords: computational complexity, time-dependent travel time, shortest path, time-expanded network

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: 04/11/2020

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