Implementing Optimal Traffic-Routing Service

OData support
Supervisor:
Dr. Heszberger Zalán Tamás
Department of Telecommunications and Media Informatics

Route planning problems have for long been researched within the field of algorithm theory. Number of routing services are available for the public providing very fast and exact solutions for route planning in road networks which had been considered a complex problem in the past. Although the majority of people have become everyday users of these services, planning and developing of them hasn't turned to as simple as it seems. In fact, building a custom routing service with great performance is rather a privilege for companies having an experience in algorithm theory and a powerful IT infrastructure. hardware infrastructure is mostly needed because today's widespread routing algorithms have very high processing and memory usage. In order to make it possible even for minor companies to create an environment providing routing services, we have to focus on researching algorithms with smaller time complexity. The requirement of short response times and user-friendliness also forces researchers to work on faster algorithms. It's apparently tough to remain in today's internet market with a service with slow response times.

Developers of route planning services often have to face that there is a significant contrast between the theoretical foundations and the real-life implementation of the chosen algorithm. A search algorithm may have proofs on the upper bound of running time and memory usage, but in most cases it doesn't performs as well in a real software and hardware context. According to these experiences we have to face again the fact that only those with a great amount of hardware can afford turning theory into practice. Therefore, having a lower-budget, the capabilities and limitations of the real implementation should be taken more seriously into consideration at the time of planning, beside theoretical and mathematical presumptions.

Traditional algorithms are defined as to solve the shortest path problem on an arbitrary graph. At the same time, every shortest path application has its specific requirements which require different search graph and search metrics. These specific requirements usually turn the problem space into a smaller one with significant improvements in performance. The positive effect of reduced problem-space size can be experienced in road networks very well, consequently it is advisable to investigate more into road-network-specific algorithms instead of reusing universal graph-algorithms.

Based on the considerations outlined above, the aim of this thesis is to develop a route planning service in road-networks including studying of the recent theoretic results, a planning phase and a result-oriented implementation. Studying of the available algorithms has the purpose of finding the most recent ones with the lowest hardware load and fastest run times. Iterative planning is intended to be done in accordance with the results of the implementation throughout the whole project cycle in order to make good decisions ensuring a long-term routing service-core. Implementation aims to achieve upper bounds on response time and hardware usage specified in the pre-requirements.

Downloads

Please sign in to download the files of this thesis.