Název: Škálovatelná navigace vozidel na dynamických grafech
Překlad názvu: Scalable dynamic graph-based vehicular routing
Autoři: Polický, Adam ; Kratochvíl, Miroslav (vedoucí práce) ; Švancara, Jiří (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2021
Jazyk: cze
Abstrakt: [cze] [eng]
Algoritmy pro hledání nejkratších cest ve velkých grafech tvoří nezbytnou část mnoha moderních navigačních systémů. Tento problém je ale při navigaci vozidel komplikovaný dynamičností silniční sítě, především uzavírkami a změnami v provozu, což omezuje ap- likaci mnoha bězných optimalizací. Cílem této práce je navrhnout algoritmus pro hledání cest ve velkých grafech, který je škálovatelný a efektivní díky tomu, že minimalizuje počet navštívených, v paměti uložených objektů. Docílilo se toho iterativním zjednodušováním grafu do vrstevnaté aproximativní struktury a vyvinutím modifikované verze Dijkstrova algoritmu, která na ní umožnuje efektivní navigaci. Výsledky ukazují, že navrhovaný algoritmus prozkoumá 4× méně grafových objektů než A* a 14× méně než Dijkstra. Dosahuje tak lepšího výkonu na úkor o něco delších nalezených cest. Kromě toho je tato vrstevnatá struktura schopna přizpůsobit se změnám v původním grafu, což umožňuje algoritmu pracovat i na měnící se síti bez náročných přepočtů. 1 Algorithms for finding shortest paths in large graphs form an essential part of many modern navigation and routing systems. In vehicular navigation, the problem is compli- cated by dynamic nature of the network caused by road closures and changes in traffic, preventing application of many common speed-up techniques. The aim of this thesis is to design an algorithm for finding paths in large graphs that gains efficiency and scalability by minimizing the number of visited graph objects in storage. This was achieved by itera- tively simplifying the graph into a multi-layered approximative structure, and developing a modification of Dijkstra's algorithm that allow efficient navigation in the structure. The results show that the proposed method examines 4× less graph objects than A* and 14× less than Dijkstra, achieving better performance at the cost of slightly longer discovered paths. Additionally, the layered structure is able to accommodate changes in the base graph, allowing the algorithm to work on a changing network without costly recomputations. 1
Klíčová slova: grafové algoritmy; hledání nejkratší cesty; navigace; směrování vozidel; graph algorithms; navigation; shortest-path finding; vehicle routing

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/127942

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-448113


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce