Tree-deletion pruning in label-correcting algorithms for the multiobjective shortest path problem

DOI10.1007/978-3-319-53925-6_15MaRDI QIDQ2980909zbMATH OpenOpenAlexFDO

Authors Fritz Bökler, Petra Mutzel

Publication date 5 May 2017

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.08147

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05)

Abstract: In this paper, we re-evaluate the basic strategies for label correcting algorithms for the multiobjective shortest path (MOSP) problem, i.e., node and label selection. In contrast to common believe, we show that---when carefully implemented---the node-selection strategy usually beats the label-selection strategy. Moreover, we present a new pruning method which is easy to implement and performs very well on real-world road networks. In this study, we test our hypotheses on artificial MOSP instances from the literature with up to 15 objectives and real-world road networks with up to almost 160,000 nodes.

Recommendations

• An improved multiobjective shortest path algorithm
• Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms
• A new approach for the multiobjective minimum spanning tree
• A multi-objective shortest path problem
• Speeding up Martins' algorithm for multiple objective shortest path problems

Cites work

• A comparison of solution strategies for biobjective shortest path problems
• A multicriteria Pareto-optimal path algorithm
• An empirical investigation of some bicriterion shortest path algorithms
• Label correcting methods to solve multicriteria shortest path problems
• Multicriteria path and tree problems: discussion on exact algorithms and applications
• Multiple criteria decision analysis. State of the art surveys. In 2 volumes
• On a multicriteria shortest path problem
• Parallel asynchronous label-correcting methods for shortest paths
• Shortest paths algorithms: Theory and experimental evaluation

Cited in

(3)

• MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
• Targeted multiobjective Dijkstra algorithm
• An improved multiobjective shortest path algorithm

This page was built for publication: Tree-deletion pruning in label-correcting algorithms for the multiobjective shortest path problem

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