A comparison of solution strategies for biobjective shortest path problems

DOI10.1016/j.cor.2008.02.002zbMath1162.90579OpenAlexW1993371203MaRDI QIDQ958463

Andrea Raith, Matthias Ehrgott

Publication date: 4 December 2008

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2008.02.002

zbMATH Keywords

label setting algorithmtwo phase methodbiobjective shortest path problemlabel correcting algorithmnear shortest path algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (55)

An approach to determine unsupported non-dominated solutions in bicriteria integer linear programs ⋮ Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem ⋮ Exact algorithms for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network ⋮ Multiobjective shortest path problems with lexicographic goal-based preferences ⋮ An exact method for the biobjective shortest path problem for large-scale road networks ⋮ Bi-objective robust optimisation ⋮ Pricing routines for vehicle routing with time windows on road networks ⋮ A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem ⋮ Path based algorithms for metro network design ⋮ Analysis of FPTASes for the multi-objective shortest path problem ⋮ An evolutionary approach to generalized biobjective traveling salesperson problem ⋮ A simulated annealing for multi-criteria network path problems ⋮ Dimensionality reduction in multiobjective shortest path search ⋮ An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem ⋮ A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games ⋮ Two-phase algorithm for solving the preference-based multicriteria optimal path problem with reference points ⋮ The energy-constrained quickest path problem ⋮ Bicriteria path problem minimizing the cost and minimizing the number of labels ⋮ An improved multiobjective shortest path algorithm ⋮ A discrete optimisation approach for target path planning whilst evading sensors ⋮ Accelerating the gradient projection algorithm for solving the non-additive traffic equilibrium problem with the Barzilai-Borwein step size ⋮ An aggregate label setting policy for the multi-objective shortest path problem ⋮ Two‐phase strategies for the bi‐objective minimum spanning tree problem ⋮ Finding shortest and dissimilar paths ⋮ Solving the multi‐objective bike routing problem by meta‐heuristic algorithms ⋮ Simple and efficient bi-objective search algorithms via fast dominance checks ⋮ The Steiner bi-objective shortest path problem ⋮ An exact approach for finding bicriteria maximally SRLG-disjoint/shortest path pairs in telecommunication networks ⋮ Targeted multiobjective Dijkstra algorithm ⋮ An exact method for binary fortification games ⋮ Generalized nash fairness solutions for bi‐objective minimization problems ⋮ Lower bound sets for biobjective shortest path problems ⋮ A comparison of heuristic best-first algorithms for bicriterion shortest path problems ⋮ An interactive algorithm for multi-objective route planning ⋮ An efficient time and space \(K\) point-to-point shortest simple paths algorithm ⋮ Speeding up Martins' algorithm for multiple objective shortest path problems ⋮ Tree-Deletion Pruning in Label-Correcting Algorithms for the Multiobjective Shortest Path Problem ⋮ Complexity of strict robust integer minimum cost flow problems: an overview and further results ⋮ A biobjective Dijkstra algorithm ⋮ Acceleration strategies for the weight constrained shortest path problem with replenishment ⋮ Solving multi-objective traffic assignment ⋮ Non-additive shortest path in the context of traffic assignment ⋮ Multicriteria path and tree problems: discussion on exact algorithms and applications ⋮ Range-constrained traffic assignment with multi-modal recharge for electric vehicles ⋮ A relation of dominance for the bicriterion bus routing problem ⋮ On algorithms for the tricriteria shortest path problem with two bottleneck objective functions ⋮ Path planning and vehicle scheduling optimization for logistic distribution of hazardous materials in full container load ⋮ Objectives and methods in multi-objective routing problems: a survey and classification scheme ⋮ Extensions of labeling algorithms for multi‐objective uncertain shortest path problems ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Colored-Edge Graph Approach for the Modeling of Multimodal Transportation Systems ⋮ A two-phase algorithm for the biobjective integer minimum cost flow problem ⋮ An algorithm for solving the bi-objective median path-shaped facility on a tree network ⋮ Multiobjective (Combinatorial) Optimisation—Some Thoughts on Applications ⋮ Shortest paths with ordinal weights

Uses Software

• MCF
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a multicriteria shortest path problem
• Shortest paths in networks with vector weights
• A parametric approach to solving bicriterion shortest path problems
• The shortest path problem with two objective functions
• A bicriterion shortest path algorithm
• A multicriteria Pareto-optimal path algorithm
• Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite
• An empirical investigation of some bicriterion shortest path algorithms
• A survey and annotated bibliography of multiobjective combinatorial optimization
• Shortest paths algorithms: Theory and experimental evaluation
• A label correcting approach for solving bicriterion shortest-path problems
• On the cardinality of the Pareto set in bicriteria shortest path problems
• Two phase algorithms for the bi-objective assignment problem
• New algorithms for multi objective shortest path problem.
• Shortest Path Algorithms: An Evaluation Using Real Road Networks
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• A network simplex method
• Near-shortest and K-shortest simple paths
• An algorithm for finding shortest routes from all source nodes to a given destination in general networks
• Label correcting methods to solve multicriteria shortest path problems

This page was built for publication: A comparison of solution strategies for biobjective shortest path problems