Xiao, Jade

Towards Faster Multi-Objective Shortest Path Queries

Jiantao Shen, Jade Xiao, and Andrea Raith

Department of Engineering Science, University of Auckland

Optimisation problems frequently have multiple conflicting objectives and no single solution. In the context of shortest paths, one might wish to simultaneously minimise travel time, fuel consumption, and the number of transits on a transportation network. Existing algorithms for the multi-objective shortest path problem are not fast enough, or else sacrifice correctness for speed. This motivates extending powerful speed-up techniques for the standard shortest path problem into the multi-objective domain. We present our adaptations of the algorithms based on landmarks, reach, arc flags, and contraction hierarchies, followed by the results of computational experiments. This research contributes to our understanding of the effectiveness of existing speed-up techniques in the multi-objective context.

This presentation is eligible for the ORSNZ Young Practitioners Prize.