Information Technology Reference
In-Depth Information
Dynamic Routing on OpenStreetMap
Using Ant Colonies
Alexander Bertram
1
,
and Sebastian Iwanowski
2
1
TXS GmbH, Sonninstrasse 28, 20097 Hamburg, Germany
alexander.bertram@txs.de
2
FH Wedel, University of Applied Sciences, Feldstr. 143, 22880 Wedel, Germany
iw@fh-wedel.de
Abstract.
This paper presents the software AntScout for dynamic road
navigation: The objective is to find the shortest path between arbitrarily
chosen nodes in a road network considering the current trac situation.
AntScout reacts immediately to any change in the query or in the cur-
rent trac situation. This is achieved by the continuous application of
ant colonies which are specially designed for problems with unexpected
dynamic input change. The navigation tasks are performed on Open-
StreetMap data which have been specially processed for that purpose.
AntScout provides an interface ready for use by third parties. It is
published under an open source license. Modern implementation tech-
niques such as the Scala actor concept are applied in order to make the
software applicable for real world situations. Conceptually, some deficien-
cies of ant algorithms have been detected and repaired. The experiments
with AntScout discovered the positive side effect that ant colony sys-
tems tend to toggle between several preferred routes nondeterministically
when these routes are of similar quality. Thus, ant based navigation can
also be used to distribute trac uniformly among such routes without
any further control actions.
Keywords:
ant colonies, probabilistic approach, dynamic routing, Open-
StreetMap, uniform trac distribution.
1 Motivation
Nowadays, it is standard that cars have got a navigation device on board. For
static conditions where the quality of roads is well-known and does not change
the systems work fairly well.
Perhaps the greatest challenge is to keep the digital maps up-to-date with
the real world. Another interesting topic of investigation is the question how to
measure the quality of roads. This need not necessarily be the highest feasible
maximum speed, but may also consider other criteria like road comfort, economic
evaluations, interesting scenery, etc. In recent years, least effort of research has
This work was done while the author was working on his Master's degree at FH
Wedel.
