Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
From MaRDI portal
Publication:3477968
DOI10.1145/79147.214078zbMath0699.68074OpenAlexW2089338760MaRDI QIDQ3477968
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/79147.214078
functionalcomplexitywaiting timesshortest pathsgraph algorithmsnetwork algorithmstime dependencycomputations on discrete structurescircuit problemspath and
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (77)
Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem ⋮ The time-dependent shortest path and vehicle routing problem ⋮ Bidirectional A* search on time-dependent road networks ⋮ Distance oracles for time-dependent networks ⋮ The fastest itinerary in time-dependent decentralized travel information systems ⋮ Scheduling algorithms for procrastinators ⋮ Formal language constrained path problems ⋮ On continuous network flows ⋮ Dynamic shortest path problems with time-varying costs ⋮ A Dimension-Reduction Algorithm for Multi-Stage Decision Problems with Returns in a Partially Ordered Set ⋮ Solving the time varying postman problems with timed automata ⋮ Minimum cost paths over dynamic networks ⋮ Path Problems in Complex Networks ⋮ Routing of a hazmat truck in the presence of weather systems ⋮ Minimizing the fuel consumption and the risk in maritime transportation: a bi-objective weather routing approach ⋮ Decremental algorithm for adaptive routing incorporating traveler information ⋮ Time-dependent routing problems: a review ⋮ Data-driven approaches for emissions-minimized paths in urban areas ⋮ Intelligent transportation systems -- Enabling technologies ⋮ On computing Pareto optimal paths in weighted time-dependent networks ⋮ Computation of shortest path in cellular automata ⋮ Locations on time-varying networks ⋮ Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting ⋮ Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems ⋮ Point-to-point shortest paths on dynamic time-dependent road networks ⋮ Time depending shortest-path problems with applications to railway networks ⋮ A concise guide to existing and emerging vehicle routing problem variants ⋮ A destination-preserving model for simulating Wardrop equilibria in traffic flow on networks ⋮ Minimum‐cost flow problems having arc‐activation costs ⋮ FREIGHT TRAIN ROUTING AND SCHEDULING IN A PASSENGER RAIL NETWORK: COMPUTATIONAL COMPLEXITY AND THE STEPWISE DISPATCHING HEURISTIC ⋮ A polynomial algorithm for minimizing travel time in consistent time‐dependent networks with waits ⋮ Bidirectional A ∗ Search for Time-Dependent Fast Paths ⋮ The piecewise constant/linear solution for dynamic user equilibrium ⋮ Shortest paths in time-dependent FIFO networks ⋮ Optimising waiting at nodes in time-dependent networks: cost functions and applications ⋮ Determining time-dependent minimum cost paths under several objectives ⋮ Time-Dependent SHARC-Routing ⋮ Distributed shortest-path protocols for time-dependent networks ⋮ Shortest paths in a network with time-dependent flow speeds ⋮ On the complexity of time-dependent shortest paths ⋮ The time-dependent vehicle routing problem with time windows and road-network information ⋮ Processing time-dependent shortest path queries without pre-computed speed information on road networks ⋮ Algorithms for time-dependent bicriteria shortest path problems ⋮ Continuous-time shortest path problems with stopping and starting costs ⋮ Finding rectilinear least cost paths in the presence of convex polygonal congested regions ⋮ Flows over time in time-varying networks: optimality conditions and strong duality ⋮ Vehicle routing under time-dependent travel times: the impact of congestion avoidance ⋮ Time-dependent SHARC-routing ⋮ Multicriteria adaptive paths in stochastic, time-varying networks ⋮ Dynamic shortest paths minimizing travel times and costs ⋮ Unnamed Item ⋮ Temporal cliques admit sparse spanners ⋮ Shortest paths in piecewise continuous time-dependent networks ⋮ How to find good night train connections ⋮ Efficient Computation of Time-Dependent Centralities in Air Transportation Networks ⋮ Computation of the optimal value function in time-dependent networks ⋮ Core Routing on Dynamic Time-Dependent Road Networks ⋮ A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem ⋮ Engineering Route Planning Algorithms ⋮ Shortest paths on dynamic graphs ⋮ Efficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks ⋮ Temporal Cliques Admit Sparse Spanners ⋮ Locomotive assignment and freight train scheduling using genetic algorithms ⋮ A directed hypergraph model for random time dependent shortest paths ⋮ An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem ⋮ Shortest path with acceleration constraints: complexity and approximation algorithms ⋮ The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks ⋮ Fast Computation of Point-to-Point Paths on Time-Dependent Road Networks ⋮ Queueing networks of random link topology: stationary dynamics of maximal throughput schedules ⋮ NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times ⋮ Time-dependent shortest paths through a fixed sequence of nodes: application to a travel planning problem ⋮ An integer programming approach for the Chinese postman problem with time-dependent travel time ⋮ The time-dependent rural postman problem: polyhedral results ⋮ Location of central nodes in time varying computer networks ⋮ Vehicle dispatching with time-dependent travel times ⋮ Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks ⋮ An axiomatic approach to time-dependent shortest path oracles
This page was built for publication: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
