Computation of the optimal value function in time-dependent networks

Sebastian Kluge, Konrad Reif, Martin Brokate

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 languageEnglish
Pages (from-to)105-124
Number of pages20
JournalNetworks
Volume62
Issue number2
DOIs
StatePublished - Sep 2013

Keywords

  • analysis of algorithms
  • approximation algorithm
  • deterministic network models
  • dynamic programming
  • shortest path problem

Fingerprint

Dive into the research topics of 'Computation of the optimal value function in time-dependent networks'. Together they form a unique fingerprint.

Cite this