Modeling and Simulation by Hans-Joachim Bungartz Stefan Zimmer Martin Buchholz & Dirk Pflüger

Author:Hans-Joachim Bungartz, Stefan Zimmer, Martin Buchholz & Dirk Pflüger
Language: eng
Format: epub
Publisher: Springer Berlin Heidelberg, Berlin, Heidelberg

Route Planning

The selection of the route can occur statically or ad hoc. To statically compute a route before departure and only update the route for unforeseen events such as big traffic jams or road blocks is a typical procedure that is simpler than making a new ad-hoc decision at every intersection. The goal for most traffic participants is to use the fastest route or, increasingly the case, the shortest route in order to minimize gas costs. Algorithms used to calculate the route are easily extended to include additional criteria, typically concerns such as the avoidance of toll roads.

Most likely the best known algorithm to search for a shortest path from a start vertex s to an end vertex z using edge-weighted graphs is the Dijkstra algorithm (after Edsger Dijkstra, 1930–2002). The prerequisites requiring a connected graph with nonnegative edge weights are satisfied for the traffic graph (lengths of roads should never be negtive!). The algorithm is based on the idea that starting at vertex s, proceed next to the vertex who has the smallest total weight and continue repeatedly until we reach the end vertex z. The weight g(a) of a vertex a is, for example, the length of the shortest known path from s to a in the traffic graph.

Somewhat more formally, we define three vertex sets: The set of vertices B that have already been visited, the set of boundary vertices R which contains all vertices that can be reached from the visited vertices within one step (via an edge), and the remaining set of the unknown vertices U (all others). For every vertex a considered, we store in pred(a) the information describing the vertex that was used to reach a and the total length of the shortest known route from the beginning vertex, i.e., g(a).

Algorithm 8.3 (Dijkstra).

To initialize, we set B = ∅, R = { s}, U = V ∖ R and g(s) = 0. Logically, the start vertex has no predecessor. Repeat: 1.Remove vertex a (active vertex) from set R having smallest total weight. If it is the end vertex z, then we are done. Otherwise, add it to set B.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.