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

DOI10.1007/978-3-319-53925-6_15zbMATH Open1485.68301arXiv1604.08147OpenAlexW2964179139MaRDI QIDQ2980909FDOQ2980909

Fritz Bökler, Petra Mutzel

Publication date: 5 May 2017

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms

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)