Engineering Multiobjective Shortest Path Heuristics

Multiobjective shortest path is a core problem within multiobjective optimization, appearing in applications such as QoS routing in communication networks, traffic equilibria, transport optimization as well as route and itinerary planning. It is an extension of the single criterion shortest path problem using a cost vector (instead of a scalar) per network edge, representing multiple (often conflicting) objectives or criteria. Even though numerous efficient algorithms exist for the single criterion shortest path problem, the multiobjective counterpart of the problem is much harder (NP-hard), since the optimal solution (captured by the well-known concept of the Pareto set) is typically exponential in size.  

Two main approaches are followed in order to reduce the computation effort for solving the multiobjective shortest path problem. The first one uses approximation and computes optimal solutions up to a certain factor. Approximation techniques do not necessarily yield exact solutions, but are adequately fast to be used in practice. The second approach uses heuristic improvements to speed-up existing algorithms. Such techniques yield exact solutions, but it is considerably more difficult to achieve good performance.

In this work we focus on the latter approach, motivated by the great demand in practical applications to achieve efficient and exact multiobjective shortest paths. Building upon a new graph structure specifically suited for large-scale networks, we present new implementations of heuristic algorithms (including NAMOA*, the currently best such heuristic) for the solution of the multiobjective shortest path problem. We enhance the heuristics with further optimizations and experimentally evaluate the performance of our enhanced implementation on real world road networks achieving 10 times better performance with respect to the best previous study.