Škálovatelná navigace vozidel na dynamických grafech
| Název práce v češtině: | Škálovatelná navigace vozidel na dynamických grafech |
|---|---|
| Název v anglickém jazyce: | Scalable dynamic graph-based vehicular routing |
| Klíčová slova: | směrování vozidel, navigace, grafové algoritmy, hledání nejkratší cesty |
| Klíčová slova anglicky: | vehicle routing, navigation, graph algorithms, shortest-path finding |
| Akademický rok vypsání: | 2019/2020 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra softwarového inženýrství (32-KSI) |
| Vedoucí / školitel: | RNDr. Miroslav Kratochvíl, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 14.12.2019 |
| Datum zadání: | 29.12.2019 |
| Datum potvrzení stud. oddělením: | 16.03.2020 |
| Datum a čas obhajoby: | 02.07.2021 09:00 |
| Datum odevzdání elektronické podoby: | 27.05.2021 |
| Datum odevzdání tištěné podoby: | 27.05.2021 |
| Datum proběhlé obhajoby: | 02.07.2021 |
| Oponenti: | RNDr. Jiří Švancara, Ph.D. |
| Zásady pro vypracování |
| Vehicle routing is a complex problem with many applications in car navigation, train routing and traffic optimization. The available algorithms are able to handle various subtleties of inhomogenous and dynamically changing networks, as well as of various routing-induced effects, including congestion prediction and avoidance. The thesis will review the available algorithms and provide an overview of the currently used methods. The findings will then be used to design a simple graph-based path-finding and congestion-avoidance algorithm that approximates the optimal routing using a dynamically simplified graph, in order to improve performance and scalability. Several variants of the algorithm will be compared to the naive algorithms in terms of performance, scalability, and traffic throughput achieved in a simulated network. |
| Seznam odborné literatury |
| Daniel Delling a Dorothea Wagner. Landmark-based routing in dynamic graphs. In: International Workshop on Experimental and Efficient Algorithms. Springer. 2007, 52–65.
Norulhidayah Isa, Azlinah Mohamed a Marina Yusoff. Implementation of dynamic traffic routing for traffic congestion: A review. In: International Conference on Soft Computing in Data Science. Springer. 2015, 174–186. Eiichi Taniguchi a Hiroshi Shimamoto. Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times. In: Transportation Research Part C: Emerging Technologies 12.3-4, 2004, 235–250. Shen Wang, Soufiene Djahel a Jennifer McManis. A hybrid vehicular re-routing strategy with dynamic time constraints for road traffic congestion avoidance. 2013. |