Information Technology Reference
In-Depth Information
been put into the algorithmic processing of the data available: The algorithms
used work fairly well on present hardware even for big networks.
However, in the dynamic case, the situation is much different. By dynamic
routing we understand the problem to find the best path between arbitrarily
chosen points in the network considering the current quality of the road segments
which is subject to dynamic and not predictable change. The major focus of
application is to consider the current penetrability of the road as quality measure.
The objective for this case is to find the shortest path considering the highest
feasible speed for each road segment.
The question how to get the dynamic information for all road segments is
not solved yet. Current technological approaches are Floating Car Data (FCD),
Floating Phone Data (FPD) and Trac Message Channel (TMC).
This work does not address the question how to get the dynamic data. The
cited technologies make rapid progress. As an example, we refer to the Google
FPD approach which shows a partially rather up-to-date trac situation even for
city streets. We assume that this problem will be solved with sucient accuracy
within a couple of years. Instead, we ask a different question: How do we process
the huge amount of dynamic data such that we always have an up-to-date answer
for the currently best route?
Note that the answer to this problem is not trivial, even if dynamic infor-
mation is readily available for each road segment because the answer for the
currently best route may be influenced by any road segment “between” start
and destination where “between” may even consider deviations towards a differ-
ent direction.
Ant algorithms have been specially designed to answer routing problems for
such dynamic scenarios. They have already been successfully applied to computer
networks and logistic problems. This work investigates how they behave in real
road scenarios.
Also other work (e.g. [11]) has already investigated this question. However, the
other authors did not work with real digital maps, but artificial maps. We decided
to use OpenStreetMap (OSM) data, because the open standard of OSM makes
it easy to extract the data we need and to insert any new dynamic information.
Furthermore, the wiki approach of OSM gives hope that OSM will also solve
the entry question addressed above with best quality, that is, how to keep the
digital map up-to-date with reality.
2 State-of-the-Art and Its Limitations
2.1 Routing in State-of-the-Art Navigation Systems
Routing in static navigation systems is usually performed on a map which is
available on-board. The algorithms used follow the basic idea of Dijkstra's algo-
rithm which is easy to implement (the original is found in [6]). That algorithm
is even theoretically optimal for networks with a constantly bounded number of
neighbors for each junction (which is a realistic assumption).
