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.
Article
View Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting