Computation of the optimal value function in time-dependent networks

DOI10.1002/NET.21501MaRDI QIDQ2811299zbMATH OpenOpenAlexFDO

Authors Sebastian Kluge, Konrad Reif, Martin Brokate

Publication date 10 June 2016

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.21501

zbMATH Keywords

analysis of algorithmsapproximation algorithmdeterministic network modelsdynamic programmingshortest path problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35) Dynamic programming (90C39) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Algorithms for minimum-cost paths in time-dependent networks with waiting policies
• Minimum weight paths in time-dependent networks
• On the complexity of time-dependent shortest paths
• Shortest paths in time-dependent FIFO networks
• Improved approximation for time-dependent shortest paths

Cites work

• A finite-time algorithm for shortest path problems with time-varying costs
• A note on two problems in connexion with graphs
• A set oriented approach to global optimal control
• Algorithms for minimum-cost paths in time-dependent networks with waiting policies
• Bidirectional A  ∗  Search for Time-Dependent Fast Paths
• Consensus and Cooperation in Networked Multi-Agent Systems
• Continuous-Time Shortest Path Problems and Linear Programming
• Continuous-time shortest path problems with stopping and starting costs
• Dynamic flows in time-varying networks.
• Dynamic shortest paths minimizing travel times and costs
• Engineering Route Planning Algorithms
• Generalized best-first search strategies and the optimality of A*
• scientific article; zbMATH DE number 48687 (Why is no real title available?)
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• Minimum weight paths in time-dependent networks
• Multiobjective A*
• New complexity results for time-constrained dynamical optimal path problems
• On a routing problem
• Piecewise-linear programming: The compact (CPLP) algorithm
• Shortest paths in a network with time-dependent flow speeds
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Time-dependent route planning
• Time-varying shortest path problems with constraints

Cited in

(3)

• A path-based gradient projection algorithm for the cost-based system optimum problem in networks with continuously distributed value of time
• Optimum departure times for commuters in congested networks
• Minimum cost paths over dynamic networks

This page was built for publication: Computation of the optimal value function in time-dependent networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811299)