Fast One-to-Many Multicriteria Shortest Path Search
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00367770" target="_blank" >RIV/68407700:21230/23:00367770 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1109/TITS.2023.3282069" target="_blank" >https://doi.org/10.1109/TITS.2023.3282069</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/TITS.2023.3282069" target="_blank" >10.1109/TITS.2023.3282069</a>
Alternative languages
Result language
angličtina
Original language name
Fast One-to-Many Multicriteria Shortest Path Search
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
IEEE Transactions on Intelligent Transportation Systems
ISSN
1524-9050
e-ISSN
1558-0016
Volume of the periodical
24
Issue of the periodical within the volume
10
Country of publishing house
DE - GERMANY
Number of pages
10
Pages from-to
10410-10419
UT code for WoS article
001012409900001
EID of the result in the Scopus database
2-s2.0-85162640507