Approximating Multiobjective Shortest Path in Practice
Fritz Bökler, Markus Chimani · Society for Industrial and Applied Mathematics eBooks · 2019
We consider the multiobjective shortest path (MOSP) problem. While known approximation algorithms allow a polynomial running time, the degrees of these polynomials are dependent on the number of objective functions. Unfortunately, this also holds true for their best-case. Exact algorithms, while attaining an exponential worst-case running time even in the number of nodes, allow for far better best-case performance and are thus preferred in practice. We introduce a new general approximation framework for MOSP. It aims at combining strong worst-case guarantees with practically useful performance. It allows for various labeling strategies as employed by exact algorithms; thus, decades of research can be utilized. We conduct a comprehensive computational study to compare our framework to known approximations and exact algorithms. For many, this is their first practical investigation. Furthermore, this is the first time that graphs of practically relevant sizes as well as real-world instances are considered in the context of MOSP approximation. The results show that our framework is superior to the known approximation methods in running time and quality. They also demonstrate the usefulness and limits of approximations compared to exact methods.