Performance Analysis for Route Planner Algorithms

OData support
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.


Please sign in to download the files of this thesis.