Information Technology Reference
In-Depth Information
allows to easily swap the applied search algorithm and to compare the efficiency of
different routing solutions. Based on our experiences, we integrated A* search as it
perfectly complies with our requirements.
Another benefit of using the OSM data is the semantic enrichment of the provided
data. The parsing process is not limited to retrieving information on length and
geographical positions of the streets and junctions, but also stores information about
speed limits, street names and street types. This enables the routing algorithm to
distinguish between different means of transportation, e.g., vehicles, bicycles, or
regular walking, to name a few.
As mentioned above, routing is done by means of A* search. We implemented
the algorithm to calculate path costs based on the required time to reach a given
target location (fastest way). Estimates about the cruising speed of vehicles are done
based on the speed limits which are provided by the OSM framework. In the case
that routes are done on foot, we use fixed speed values.
As a utility, all street names are also parsed and stored in memory. This makes
it possible to search for street names and to retrieve associated nodes on the graph,
rather than specifying an exact geographical coordinate. To find street names quickly,
available data is stored in a dedicated data structure, namely a “ternary search tree.”
This structure allows us to search for strings in a space and time efficient manner, as
retrieving a specific street can be managed with almost constant complexity.
5
Both
the search tree and the search graph which is used for the routing are instantiated
simultaneously.
A major challenge was the integration of the traffic data into the map. The main
requirement was the possibility to dynamically include information about traffic
incidents (e.g., congestion or accidents) and to account for the volatile nature of
these incidents. The premise was to include this information without instantiating
the graph structures again. We approached this problem by parsing the traffic data
into a separate graph which contains only those parts of the map which are directly
affected. Whenever the search algorithm arrives at positions in the graph where
additional information is available, the newly created graph fragment is favored over
the static structure. This mechanism also accounts for situations in which additional
information has to be stored while the
Plain Routing Bean
is operating.
The traffic situation itself is represented by a number of incidents. We distinguish
between
Point-Incidents
and
Edge-Incidents
. The Point-Incidents are traffic distur-
bances which are limited to particular locations or small area on the map, e.g., smaller
construction sites and erroneous traffic lights. These incidents are integrated into the
map by searching for all nodes within a certain range of this point. All edges reaching
to one of these nodes are then assigned the
Incident-Coefficient
which determines
the extent of the delay that occurs if one travels on affected edges. These are stored in
the above-mentioned sub-graph. Contrary, Edge-Incidents are these incidents which
affect a segment of a road and are processed as follows: an Edge-Incident is given
by a start and an end location-provided as nodes. The application uses these start
5
More precisely, retrieving a street name has a time complexity in
O
(
l
)
,where
l
is the number of
characters in the longest street name.
Search WWH ::
Custom Search