Škálovatelná navigace vozidel na dynamických grafech

• Thesis title in Czech: Škálovatelná navigace vozidel na dynamických grafech
• Thesis title in English: Scalable dynamic graph-based vehicular routing
• Key words: směrování vozidel, navigace, grafové algoritmy, hledání nejkratší cesty
• English key words: vehicle routing, navigation, graph algorithms, shortest-path finding
• Academic year of topic announcement: 2019/2020
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Software Engineering (32-KSI)
• Supervisor: RNDr. Miroslav Kratochvíl, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 14.12.2019
• Date of assignment: 29.12.2019
• Confirmed by Study dept. on: 16.03.2020
• Date and time of defence: 02.07.2021 09:00
• Date of electronic submission: 27.05.2021
• Date of submission of printed version: 27.05.2021
• Date of proceeded defence: 02.07.2021
• Opponents: RNDr. Jiří Švancara, Ph.D.

Guidelines

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.

References

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.