An Experimental Study on Exact Multi-constraint Shortest Path Finding

Given a directed graph with each edge has a weight and several criteria, a multi-constraint shortest path query (CSP) asks for the shortest path that satisfies the constraints on these criteria. It is a general routing problem and can be used to customise user’s routing requirements. However, only the single-constraint version has been well studied while the multi-constraint version is ignored due to its complexity. In this paper, we explore the multi-CSP problem by extending three existing single-CSP algorithms (Skyline-Dijkstra, sKSP, and eKSP) and experimentally study their performance and behaviours. Experiment results provides insights of how the query distance, constraint ratio, criteria number, strictness, and correlation influence the query performance.