The Shortest Path Problem on Real Road Networks: Theory, Algorithms and Computations

The Shortest Path Problem on Real Road Networks: Theory, Algorithms and Computations

Post, H.N.

Aardal, K.I. (promotor)

Electrical Engineering, Mathematics and Computer Science

EWI

2014-02-26

This thesis contains the following subjects: - Several shortest path algorithms, both label-setting and label-correcting; - Unidirectional and bidirectional methods; - A* algorithms; - Symmetric and balanced estimators; - Preprocessing techniques. This thesis contains an elaborate, comparative evaluation of the various methods described. Bidirectional A* algorithms are commonly based on balanced heuristic estimators, since such estimators can easily be embedded in a bidirectional variant of Dijkstra's algorithm. In this thesis a check is provided, such that symmetric estimators can compete with balanced estimators. If these estimators are based on Euclidean distances, the work can be divided over the forward and backward searches with the use of scalar projections. This way, symmetric estimators are even prefered over balanced estimators. A well-known preprocessing technique includes the use of landmarks. If the estimators are based on landmarks, a balanced approach turns out to be faster than a symmetric approach. In this thesis, an initial step is proposed in a unidirectional A*-algorithm, which uses a landmark-based estimator, in order to decrease the running time of that algorithm. For one of the preprocessing techniques described, unidirectional methods are preferred over bidirectional methods. It is that particular preprocessing technique where the proposed initial step will prove an additional value.

shortest path
bidirectional search
preprocessing techniques

https://doi.org/10.4233/uuid:891f90a4-d4a3-4644-b35e-224440e47dba

2014-02-26

9789461862709

Institutional Repository

doctoral thesis

(c) 2014 Post, H.N.