Information Technology Reference
In-Depth Information
2.3 OpenStreetMap
OpenStreetMap
1
is the largest free geographic database of the world which is
rapidly growing. OpenStreetMap gathers and updates its content from volunteer
helpers throughout the world. Thus, it applies the same principle as wikipedia.
The number of registered helpers is almost 1 million already. This makes Open-
StreetMap the most accurate geographic database among all digital maps at least
in countries with a lot of digitally oriented people, e.g., in most areas of Europe.
Unlike other maps like GoogleMaps, OpenStreetMap has a specific strength also
in foot paths and areas beyond roads.
Unlike other free maps like GoogleMaps, OpenStreetMap does not only pro-
vide the maps, but also the geodata themselves for free use. This makes it very
prone for applying new technologies which is the main reason why we chose this
map. Meanwhile, several routing providers are linked to at least the German
version of OpenStreetMap
2
. However, they deal with static routing only.
The data of OpenStreetMap is provided in XML which makes it very conve-
nient to be processed by any programming language with a web service interface.
Open StreetMap provides the concepts of
node
and
way
:A
node
is an arbitrary
point defined by its geographic coordinates. A
way
is defined by a sequence of
nodes. This is used to model roads, borders and rivers and any other object of
1 dimension.
Road segments
are a special kind of
way
s. They are classified in several cat-
egories: The highest category is
motorway
and the lowest
residential
.Inbe-
tween there are the categories
primary
,
secondary
,
tertiary
and some more
categories.
2.4 Conceptual Challenges
Ant systems are based on the eager computation principle: Each route query is
computed in advance. Since the system must be prepared to answer any query,
it must continuously update the best route between any two query points. This
results in a number of queries that is quadratic in the number of nodes of the
underlying graph. In order to ensure fast convergence of the pheromones to any
dynamic situation, this quadratic number of queries must be repeated frequently
within a minute.
In principle, this results in a run time that is a quadratic multiple of the run
time of a single query. But there is hope to reduce this by parallelization and
reduction of query nodes.
3 AntScout - Applying Ant Colonies on OpenStreetMap
AntScout is an open source software
3
published under the apache license version
2.0.
