Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives

Abstract

In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) — a very powerful speed-up technique originally developed for standard shortest path queries (Geisberger et al. 2008) — can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case. This is an extended abstract of the full paper published in (Funke and Storandt 2013).