The Shortest Path Problem on Real Road Networks: Theory, Algorithms and Computations
Henk Post · Research Repository (Delft University of Technology) · 2014
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.