Fast One-to-Many Multicriteria Shortest Path Search

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Fast One-to-Many Multicriteria Shortest Path Search

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Fast One-to-Many Multicriteria Shortest Path Search

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

IEEE Transactions on Intelligent Transportation Systems

ISSN

1524-9050

e-ISSN

1558-0016

Svazek periodika

24

Číslo periodika v rámci svazku

10

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

10

Strana od-do

10410-10419

Kód UT WoS článku

001012409900001

EID výsledku v databázi Scopus

2-s2.0-85162640507