Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14287
For citation please use:
Main Title: Acceleration of Shortest Path and Constrained Shortest Path Computation
Author(s): Köhler, Ekkehard
Möhring, Rolf H.
Schilling, Heiko
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15514
http://dx.doi.org/10.14279/depositonce-14287
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We study acceleration methods for point-to-point shortest path and constrained shortest path computations in directed graphs, in particular in road and railroad networks. Our acceleration methods are allowed to use a preprocessing of the network data to create auxiliary information which is then used to speed-up shortest path queries. We focus on two methods based on Dijkstra's algorithm for shortest path computations and two methods based on a generalized version of Dijkstra for constrained shortest paths. The methods are compared with other acceleration techniques, most of them published only recently. We also look at appropriate combinations of different methods to find further improvements. For shortest path computations we investigate hierarchical multiway-separator and arc-flag approaches. The hierarchical multiway-separator approach divides the graph into regions along a multiway-separator and gathers information to improve the search for shortest paths that stretch over several regions. A new multiway-separator heuristic is presented which improves the hierarchical separator approach. The arc-flag approach divides the graph into regions and gathers information on whether an arc is on a shortest path into a given region. Both methods yield significant speed-ups of the plain Dijkstra's algorithm. The arc flag method combined with an appropriate partition and a bi-directed search achieves an average speed-up of up to 1,400 on large networks. This combination narrows down the search space of Dijkstra's algorithm to almost the size of the corresponding shortest path for long distance shortest path queries. For the constrained shortest path problem we show that goal-directed and bi-directed acceleration methods can be used both individually and in combination. The goal-directed search achieves the best speed-up factor of 110 for the constrained problem.
Subject(s): shortest path
constrained shortest path
Dijkstra's algorithm
acceleration method
road network
Issue Date: 2004
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 05C85 Graph algorithms
05C20 Directed graphs, tournaments
90B20 Traffic problems
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2004, 42
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-042-2004.pdf
Format: Adobe PDF | Size: 274.15 kB
DownloadShow Preview
Thumbnail
Report-042-2004.ps.gz
Format: Unknown | Size: 212.62 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.