The ε-approximation of the Label Correcting Modification of the Dijkstra's Algorithm

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F19%3A43956499" target="_blank" >RIV/49777513:23520/19:43956499 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.scitepress.org/PublicationsDetail.aspx?ID=3Yjqni%2fbuu4%3d&t=1" target="_blank" >https://www.scitepress.org/PublicationsDetail.aspx?ID=3Yjqni%2fbuu4%3d&t=1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5220/0007658200260032" target="_blank" >10.5220/0007658200260032</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The ε-approximation of the Label Correcting Modification of the Dijkstra's Algorithm

Popis výsledku v původním jazyce

This paper is focused on searching the shortest paths for all departure times (profile search). This problem is called a time-dependent shortest path problem (TDSP) and is important for optimization in transportation. Particularly this paper deals with the ε-approximation of TDSP. The proposed algorithm is based on a label correcting modification of Dijkstra&apos;s algorithm (LCA). The main idea of the algorithm is to simplify the arrival function after every relaxation step so that the maximum relative error is maintained. When the maximum relative error is 0.001, the proposed solution saves more than 95% of breakpoints and 80% time compared to the exact version of LCA. A more efficient precomputation step for another time-dependent routing algorithms can be built using the developed algorithm.

Název v anglickém jazyce

The ε-approximation of the Label Correcting Modification of the Dijkstra's Algorithm

Popis výsledku anglicky

This paper is focused on searching the shortest paths for all departure times (profile search). This problem is called a time-dependent shortest path problem (TDSP) and is important for optimization in transportation. Particularly this paper deals with the ε-approximation of TDSP. The proposed algorithm is based on a label correcting modification of Dijkstra&apos;s algorithm (LCA). The main idea of the algorithm is to simplify the arrival function after every relaxation step so that the maximum relative error is maintained. When the maximum relative error is 0.001, the proposed solution saves more than 95% of breakpoints and 80% time compared to the exact version of LCA. A more efficient precomputation step for another time-dependent routing algorithms can be built using the developed algorithm.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

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 statě ve sborníku

GISTAM 2019 - Proceedings of the 5th International Conference on Geographical Information Systems Theory, Applications and Management2019

ISBN

978-989-758-371-1

ISSN

—

e-ISSN

—

Počet stran výsledku

7

Strana od-do

26-32

Název nakladatele

SciTePress

Místo vydání

Heraklion

Místo konání akce

Heraklion, Crete, Greece

Datum konání akce

3. 5. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000570535400002