All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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