Performance Analysis for Route Planner Algorithms

OData support
Supervisor:
Dr. Juhász Sándor
Department of Automation and Applied Informatics

There are plenty of algorithms for searching the shortest path in graph. In my thesis, I describe and explain several graph search algorithms, and after I use these algorithms to plan routes on a real life map. I introduce a free map database then I show a method converting it to a weighted, directed graph. Some algorithms use heuristic functions to give a lower bound to the cost of a path, or precompute some data, which can be used during the path planning.

The way the map is stored is crucial concerning the performance of the algorithms. I compare the performance of a relational database stored on the hard drive to a complex data structure stored in the memory.

The algorithms showed in the first part of the thesis are tested on the Hungarian road network. To do this I generate random sources and destinations and I measure different aspects of the performance shown by the algorithms.

In the last chapter I show a few methods to parallelize the searches, and I propose a few ways to develop a more comlex, but faster algorithm.

Downloads

Please sign in to download the files of this thesis.