Being an NP-hard problem, multicriteria shortest path search is difficult to solve with speed satisfactory for real-world use. Therefore, this article examines the combination of t-discarding kPC-MLS [1] and multiple pruning heuristics. Apart from comparing the efficiency of the individual techniques, the research also evaluates the ability of $t$-discarding kPC-MLS to employ such heuristics. Since the experiments were conducted on country-size roadmaps, the results are expected to be relevant to real-world applications. According to the measurements, $t$-discarding kPC-MLS gains a higher speedup than standard MLS [2], operating on comparable roadmaps in a matter of seconds.
Heuristics for Fast One-to-Many Multicriteria Shortest Path Search
2022-10-08
653892 byte
Conference paper
Electronic Resource
English
Fast One-to-Many Multicriteria Shortest Path Search
IEEE | 2023
|Fast optical flow using 3D shortest path techniques
British Library Online Contents | 2002
|Flexible Bus Routing System with Shortest Path Search Algorithm
European Patent Office | 2020
|Urban K shortest path obtaining method based on shortest path tree
European Patent Office | 2024
|Parametric search for the bi-attribute concave shortest path problem
Online Contents | 2016
|