A polynomial algorithm for minimizing travel time in time-dependent networks with waits
We consider a time-dependent shortest path problem with possible waiting at each node and a global bound $W$ on the total waiting time. The goal is to minimize only the time travelled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when … Read more