Information Technology Reference
In-Depth Information
be described. Both, nodes and ways can be extended by custom tags. This mechanism
allows to enrich map data with semantic information. By means of tagging, arbitrary
information can be stored in OSM maps, e.g., different way-types (roads, sidewalks,
bicycle ways, seaways, metro lines, bus lines, etc.) or different points of interest,
such as shops, car parks, bus stops, telephone booths, restaurants, among others.
Both, OSM and A* search were used to implement the core functionality of our
OSM Routing Agent. As illustrated in Fig.
13.2
, the OSM Routing Agent comprises
two JIAC AgentBeans. We describe these agent components below in more detail.
13.3.1.2 The Plain Routing Bean
The
Plain Routing Bean
is central to the IMA routing system. It is the only com-
ponent which has direct access to the OSM-based map data. Therefore, routing was
implemented directly within this AgentBean. The map itself is parsed from an Open-
StreetMap input-file (based on XML) and translated into a more efficient internal
representation.
The parsing process was implemented with the help of the
Apache Xerces2 Java
Parser
4
as follows: Firstly, every node of the future search graph is extracted from
the XML-file. In doing so, only nodes that are not required for the routing process are
neglected (e.g., traffic lights or shop locations). Secondly, ways with the additional
description “highway” (identified by tag with the same name) are loaded from the
file. These ways and all remaining nodes are used to instantiate the digraph, which is
finally used for the routing. What happens next is that nodes which do not belong to a
highway are removed from the model (these nodes are not reachable). The resulting
data structure is tailored to the use in IMA. In order to avoid future import processes
the optimized data structure is persistently stored within a separate file.
Based on this mechanism, we were able to decrease the file size for an OSM-based
representation of Berlin (Germany) by more than 50 %, from roughly 130 MB to about
61 MB. This optimization was necessary, especially in the light of the complexity
of OSM data. As an example, the original OSM map for Berlin currently contains
573.397 nodes, while only 165.254 of these are located in a highway structure. Based
on our more efficient representation it was possible to decrease the time which is
required for the parsing by roughly 50 %.
Every time the system is started, available maps (in the optimized format) are
parsed anew. Information in these files are used to instantiate the internal routing
graph. This graph is designed as a digraph, where the weighted edges represent the
streets with their respective length. In order to access each node and edge quickly, both
are stored in a hash map where they are indexed by their respective OSM identifiers,
such that nodes only contain references to their neighbor nodes and edges that connect
these neighbors. Routing is done by means of A* search. In fact, the search algorithm
is included in a modular fashion, such that data which is required by the algorithm is
provided in a standardized way, which is described by an interface. This mechanism
4
The Apache Xerces Project website:
http://xerces.apache.org/
.
Search WWH ::
Custom Search