7971
2021
2021
eng
reportzib
0
2021-06-18
2021-06-18
--
An Improved Multiobjective Shortest Path Algorithm
We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is $\times2$ to $\times9$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.
1438-0064
urn:nbn:de:0297-zib-79712
yes
publish
Pedro Maristany de las Casas
Pedro Maristany de las Casas
Antonio Sedeno-Noda
Ralf BorndÃ¶rfer
ZIB-Report
20-26
eng
uncontrolled
Multiobjective Shortest Path Problem
eng
uncontrolled
Output-Sensitive Multiobjective Combinatorial Problems
eng
uncontrolled
Network Optimization
DISCRETE MATHEMATICS
Graph algorithms [See also 68R10, 68W05]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Research exposition (monographs, survey articles)
Mathematical Optimization
Mathematics of Transportation and Logistics
BorndÃ¶rfer, Ralf
LHS-ATN
Maristany de las Casas, Pedro
MODAL-Gesamt
Network Optimization
MODAL-MobilityLab
https://opus4.kobv.de/opus4-zib/files/7971/main.pdf