Polynomial-time Construction of Contraction Hierarchies for Multi-criteria Objectives
Stefan Funke, Sabine Storandt · Society for Industrial and Applied Mathematics eBooks · 2013
We consider multicriteria shortest path problems and show that contraction hierarchies — a very powerful speed-up technique originally developed for standard shortest path queries in [7] — can be constructed efficiently for the case of arbitrary conic combinations of the edge costs. This extends previous results in [5] which considered only the bicriteria case and discrete weights for the objective functions. On the theory side we prove a polynomial time bound for determining whether a path π is part of the lower envelope of all pareto-optimal paths via some polyhedral arguments. Experiments complement these results by showing the practicability of our approach.