Information Technology Reference
In-Depth Information
In order to eciently reduce the number of nodes, the preprocessing unit com-
bines these three principles simultaneously, i.e. it uses a predefined admissible
rectangle and a predefined admissible lowest category and considers as admissi-
ble nodes only the nodes that are part of at least three road segments of that
category or higher. A link in our graph is identified with a sequence of OSM road
segments of the admissible categories. Note that the network obtained from this
also contains nodes of degree 1 and 2, because some of the links incident to ad-
missible nodes (which originally were all of degree at least 3) may stretch out of
the admissible rectangle and, thus, have to be removed. For further reduction,
we also merge two links meeting at a node of degree 2, thus avoiding nodes of
degree 2. However, we leave nodes of degree 1 in the network which are dead
ends.
The admissible rectangle may be arbitrarily chosen, and the admissible low-
est categories are
motorway
,
motorway-link
,
trunk
,
trunk-link
,
primary
,
primary-link
,
secondary
,
secondary-link
and
tertiary
.
We applied the preprocessing to several areas of the town of Hamburg which
is a densely populated city. Our reduction principles above applied to rectangles
with areas up to 50
km
2
. Using tertiary roads as lowest admissible categories
provided a maximum of 150 nodes.
In off-city areas the area covered may be much higher, but we wanted to
demonstrate that our dynamic routing software may even be applied in cities
which we consider the hardest task due to the density of alternatives and the
need for fast reaction to dynamic changes.
3.3 Run Time Functionality
Since our system should show how ant systems react to spontaneous trac
changes, we considered it crucial to integrate user and operator mode in the
same interface, i.e., there should be no explicit switching between them: An op-
erator action should be executed at any time, and also a user query should be
specified at any time. Both types may be interweaved in an arbitrary order. The
operator action referring to some road segment remains valid until a new action
is executed for the same road segment. A user query is valid until a new query
is asked.
AntScout always displays the route using the best pheromones between the
currently valid source and target. This is considered the currently suggested
route.
This gave us an easy method to measure the response time to any dynamic
change represented by an operator action: We simply needed to measure the
time between operator entry and visible route change.
Note that a car driver who is identified with the user of our setting has nothing
to do with the individual ants of the colony system which are anonymous software
units and not displayed at the interface at all: The car drivers always get the
currently best answer, but the ants make a probabilistic decision for their route.
The latter guarantees that there will always be ants using unfavourable routes
which is important for the quick detection of dynamic changes.
