An algorithm for the ranking of shortest paths

DOI10.1016/0377-2217(93)90095-5zbMath0782.90091OpenAlexW2030169809MaRDI QIDQ1309941

José Augusto Azevedo, Ernesto Q. Vieira Martins, Maria Emília O. Santos Costa, Joaquim João E. R. Silvestre Madeira

Publication date: 28 February 1994

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(93)90095-5

zbMATH Keywords

principle of optimalityshortest paths algorithmlabelling algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (28)

Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach ⋮ A computational improvement for a shortest paths ranking algorithm ⋮ Considering en-route choices in utility-based route choice modelling ⋮ The fastest itinerary in time-dependent decentralized travel information systems ⋮ Shortest route computation in distributed systems ⋮ Finding \(K\) shortest looping paths in a traffic-light network ⋮ Exploring trust region method for the solution of logit-based stochastic user equilibrium problem ⋮ DTA2012 symposium: Combining disaggregate route choice estimation with aggregate calibration of a dynamic traffic assignment model ⋮ Finding the \(K\) shortest paths in a time-schedule network with constraints on arcs ⋮ Congestion avoiding heuristic path generation for the proactive route guidance ⋮ An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem ⋮ Multiobjective routing problems ⋮ Accelerating the gradient projection algorithm for solving the non-additive traffic equilibrium problem with the Barzilai-Borwein step size ⋮ Efficient algorithms to find optimal paths in a public transportation network ⋮ Speeding up Martins' algorithm for multiple objective shortest path problems ⋮ Shortest path problems with partial information: Models and algorithms for detecting dominance ⋮ A self-adaptive gradient projection algorithm for the nonadditive traffic equilibrium problem ⋮ Ernesto de Queirós Vieira Martins (1945-2000): An appreciation by Mário S. Rosa ⋮ A bicriterion approach for routing problems in multimedia networks ⋮ Finding \(K\) shortest looping paths with waiting time in a time--window network ⋮ A modified truncated Newton algorithm for the logit-based stochastic user equilibrium problem ⋮ Interactive in-vehicle guidance through a multihierarchical representation of urban maps ⋮ A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs ⋮ Improving truncated Newton method for the logit-based stochastic user equilibrium problem ⋮ A multi-modal approach to the location of a rapid transit line ⋮ Strategy-based transit stochastic user equilibrium model with capacity and number-of-transfers constraints ⋮ DEVIATION ALGORITHMS FOR RANKING SHORTEST PATHS ⋮ Solving some lexicographic multi-objective combinatorial problems

Cites Work

• Unnamed Item
• Unnamed Item
• An algorithm for ranking paths that may contain cycles
• A bicriterion shortest path algorithm
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• A note on the constrained shortest-path problem
• Shortest-path algorithms: Taxonomy and annotation
• Shortest path methods: A unifying approach
• Shortest Path and Network Flow Algorithms
• Iterative methods for determining the k shortest paths in a network
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• The constrained shortest path problem
• An Appraisal of Some Shortest-Path Algorithms
• Finding the K Shortest Loopless Paths in a Network

This page was built for publication: An algorithm for the ranking of shortest paths