Intermodal Mobility Assistance for Megacities - Smart Information Systems: Computational Intelligence for Real-Life Applications - page 346

13.3.1 The OSM Routing Agent

The OSM Routing Agent implements the fundamental routing functionality of the
IMA Routing System. The agent aims at providing a fast and reliable path finding
solution, which is able to integrate the gathered traffic data into its worldview in real-
time and to find efficient routes, which are tailored to the current traffic situation.
Due to the volatile nature of traffic environments, it was necessary to store
available traffic information in a manner which accounts for dynamic changes. We
designed this data structure in a graph-like fashion, including subgraphs in order to
store changing states of the system. Another issue was to account for the connection
to external services (and to respectively store their information). Such mechanism
was included as well. In order to explain implementation details, we continue by
presenting related work. Subsequently, we present the OSM Routing Agent in detail.

13.3.1.1 Related Work

For the implementation we mainly applied two mechanisms, a specialization of
a best-first search algorithm, namely A* search [ 22 , pp. 97-101], and the Open-
StreetMap ,or OSM framework [ 21 ], which provides free map material for traffic
systems all over the world.
A* search [ 22 , pp. 97-101] is an algorithm which can be used to find paths
through graph structures. A* search evaluates nodes of the graph by combining the
costs to reach a given node and the cost to get from this node to the target location.
To this end, A* “expands,” i.e., starts at a source location and explores the graph,
by respectively moving to the neighbor node with the lowest sum of costs that are
necessary to reach the node and expected costs to reach the target location from
this node. While the former costs have been calculated during the expansion, the
latter costs are estimated. This estimation significantly determines the quality of A*
search. In the case of route finding, one particular heuristic is commonly applied,
namely the beeline distance. We applied this heuristic, such that the assessment of
the quality of a node n complies with:

estimated_costs ( n ) = cost ( s , n ) + beeline ( n , t ),

where s is the source location, beeline: node is the function which

returns the geographical distance between two nodes, and t is the source location.
We implemented this algorithm to be compatible with OSM data.
Map material, which is provided by OSM, is available in several formats.
The most common format being XML . 3 The syntax of XML-based OSM maps is
rather simple. Basically, these files contain only two categories of entry types, namely
node and way . While nodes can be considered as elementary building blocks, ways
are basically collections of nodes. Based on this mechanism, entire traffic systems can

× node → R

3

XML is the abbreviation for Extensible Markup Language .