Information Technology Reference
In-Depth Information
AntScout consists of two parts:
1. A preprocessing unit that extracts data from OpenStreetMap in order to
enable the functionalities of the run time unit
2. A run time unit providing two functionalities:
user functionality: performing navigation queries on the preprocessed map
operator functionality: changing the feasible speed of selected road
segments
The user functionality of the run time unit is the benchmark for the ant
colony solution and the main part to be evaluated. The operator functionality
corresponds to a trac simulator and resembles dynamic behaviour, because
this is the purpose for which we are using ant colonies.
3.1 Software Environment
As programming environment we used Scala which is a language integrating the
principles of object-oriented and functional programming. The compiler pro-
duces Java byte code which may be executed on a Java Virtual Machine. Thus,
Scala bears all advantages of Java as a programming language.
The reason for applying rather Scala than Java is its ability to provide paral-
lelization: In contrast to Java's thread concept, Scala provides the actor concept
of Erlang which is specially designed for parallelization. Originally, Scala had
got an own actor library for that, but we rather used an open source framework
called Akka 4 . In the meantime, Akka has been integrated in Scala's next version.
Thus, our implementation is safe for future extensions. The strength of Akka is
the smooth support of distributing parallel processes to several computers which
enables cloud computing.
3.2 Preprocessing Functionality
The aim of the preprocessing functionality is to extract a network of nodes
and links that is eligible for routing. In principle, each OpenStreetMap node
that is part of a road segment may be a network node. But in order to reduce
the complexity of the run time component, we reduce the number of nodes
considerably by the following:
1. If an OpenStreetMap node is in between a road segment or connecting ex-
actly two road segments, routing does not have a choice between alternatives.
This is why we omit all such nodes and only consider nodes which are part
of at least three road segments. Using graph terminology, we only consider
nodes of degree at least 3.
2. We restrict to certain geographic areas using a rectangle placed upon Open-
StreetMap data: Only nodes within this rectangle are considered, and only
links between such nodes are considered, i.e., links stretching out of the
rectangle are not considered.
3. We confine to predefined categories of road segments: Only road segments
of this category or higher are considered.
4 http://akka.io/
 
Search WWH ::




Custom Search