Computation of the optimal value function in time‐dependent networks
Sebastian Kluge, Konrad Reif, Martin Brokate · Networks · 2013
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. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013