Αλγόριθμοι Για Γραφήματα Εναλλακτικών Διαδρομών Σε Οδικά Δίκτυα : Επισκόπηση Και Αξιολόγηση

Abstract

Nowadays, mobility has gained great importance. People travel daily either for their works or for pleasure making route planning a significant aspect of their everyday life. Although first algorithms solving this kind of problem, such as Dijkstra and Bellman-Ford, are quite old, the new circumstances require more efficient solutions taking into account various parameters related to driver’s preferences, environmental conditions, financial conditions, traffic congestions and many other aspects.Under these new requirements and needs, algorithmic engineering exhibited an impressive surge of interest during the last years in the field of route planning, developing new algorithmic approaches that solve more sophisticated variants of the shortest path problem. For example, researchers developed speed-up techniques computing queries in large-scale networks with great time efficiency, introduced new concepts of multi-modal and multi-objective routing etc.In this thesis, we focus on a variant of the shortest path problem that aims to find multiple alternative routes from source to target, apart from the single shortest path. Research on this field is very important since finding a set of alternatives can be useful for various reasons. For example, the need to avoid costly roads, the increasing occurrence of traffic congestions, driver’s preferences to avoid some streets are cases that a single route would not be enough.So, we present plateau method which is a significant approach on this field of interest based on paths with constant distances from source and target, along them (plateaux). We analyze step by step its stages, we understand the methodology and we implement it in our own C++ program. We further combine our plateau approach with penalty algorithm which, as its name states, penalizes the edges already belonging in an alternative. Apart from the two interesting implementations, we aim to evaluate the resulting alternative routes so as to choose the best ones. The superiority of each single alternative is examined on the basis of specific criteria we introduce. These criteria check the quality of the candidate plateaux, the amount of disjointness between the paths, the average length, the local optimality. These criteria are incorporated in the C++ implementations. Last but not least, in order to examine the efficiency of these algorithms, we conduct an experimental study for various values of the parameters in large-scale road networks, we export statistical data and we draw conclusions.