Abstract
We consider a time-dependent network with a continuous-time variable, in which time constraints are imposed both on the arrival times and on the waiting times at the nodes. Under certain continuity assumptions, we prove the existence of optimal paths, and we show that the optimal value function is lower-semicontinuous. We present an exact solution algorithm, which computes both the optimal value function and the corresponding optimal paths. This algorithm is based on a Dijkstra-like interpretation of a decreasing order of time algorithm, which allows the generalization of this method to a heuristic search algorithm. Moreover, we present an approximation procedure for the computation of the optimal value function and the corresponding optimal paths in a time-dependent first-in first-out (FIFO) network. This method allows for the iterative construction of paths of monotone decreasing cost, starting from a path that is computable in polynomial time. We prove the correctness and termination of both algorithms.
Original language | English |
---|---|
Pages (from-to) | 105-124 |
Number of pages | 20 |
Journal | Networks |
Volume | 62 |
Issue number | 2 |
DOIs | |
State | Published - Sep 2013 |
Keywords
- analysis of algorithms
- approximation algorithm
- deterministic network models
- dynamic programming
- shortest path problem