-

 

 

 




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 )

Citation:

Download: [PDF]

Entry Submitted: 02/21/2019
Entry Accepted: 02/21/2019
Entry Last Modified: 07/26/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
Mathematical Optimization Society