Fast One-to-Many Multicriteria Shortest Path Search

Shortest path problem has been successfully applied in numerous domains. Unfortunately, its complexity increases drastically when several objective criteria must be considered. Apart from the relatively slow classic search algorithms, attempts to accelerate multicriteria shortest path search are mostly represented by goal-directed one-to-one search methods and pruning heuristics. The one-to-many version of the problem is rarely addressed, though it arises in various scenarios, such as multi-stop planning and dynamic rerouting. This paper introduces a novel algorithm combination designed for fast one-to-many multicriteria shortest path search. A preprocessing algorithm excludes irrelevant vertices by building a smaller cover graph. A modified version of the multicriteria label-setting algorithm operates on the cover graph and employs a dimensionality reduction technique for swifter domination checks. While the method itself maintains solution optimality, it is able to additionally incorporate existing heuristics for further speedups. Additionally, its operation is not limited to bicriteria cases and requires no modifications to incorporate a higher number of criteria. The proposed algorithm was tested on multiple criteria combinations of varying correlation and compared to existing one-to-one shortest path search techniques. The results show the introduced approach provides a speedup of at least 3 times on simple criteria combinations and at least over 24 times on hard instances compared to standard multicriteria label-setting, while outperforming existing one-to-one algorithms in terms of scalability. Apart from the speedup provided, graph preprocessing also reduces memory requirements of queries by up to 13 times.

Automated summary

The shortest path problem is widely used in different fields, but becomes more complex when multiple objective criteria need to be considered. Existing methods for accelerating multicriteria shortest path search focus mostly on one-to-one search and heuristics pruning, while overlooking the one-to-many version. This paper proposes a novel algorithm combination that achieves fast one-to-many multicriteria shortest path search, utilizing a preprocessing algorithm and a modified label-setting algorithm. The proposed algorithm not only maintains solution optimality, but also incorporates heuristics and can handle a higher number of criteria. Experimental results demonstrate that the proposed approach outperforms existing techniques in terms of speed, scalability, and memory requirements reduction.