Navigating Objects - Programming GPS and OpenStreetMap Applications with Java - page 125

ˆ metric to optimize a route for (e.g., \most fuel ecient
route"),
ˆ finding places,
ˆ . . .

Alternatively, one can build one's own system by using the map compiler
and adding complexity step by step.

9.3 Route Calculation

The Origin
The initial task of a navigation system is to determine its current position.
Where am I with respect to the current route? What maneuver is next?
Today vehicle positioning has become much less complex, since the GPS
signals are very precise and digital maps supply a high density and cover-
age. Once the vehicle has determined its coordinates, the position can be
snapped to the road network. The closest map node relative to the cur-
rent position represents the origin , while a destination is provided by the
user/driver. In the roaf project, vehicle positioning does not really take
place, since the objects do not rely on satellite signals or any sensors. The
\signal" of the GPSunit is always available and always precise. Position and
heading are known at any instance in time.

The Route: origin - ( via[] ) - destination
With the origin and the destination, the system can begin to search for a
route on the given road network. A number of additional via points can be
formally treated as a number of routes combined on a higher level in the
system. The core process of a navigation system is the traversal of a graph
representing the network. While the graph is static, routing is dynamic
and re-routing can occur whenever the vehicle leaves the precalculated
way. Route calculation is based on a graph composed of nodes and edges.
Neighboring nodes or vertices are adjacent to each other. The number of
neighbors grows quickly and requires a search strategy to exclude nodes
as early as possible.

This can be achieved by defining a cost for every

connection.
The most widespread algorithm to search a graph is Dijkstra's shortest
path algorithm, which is used in navigation systems and in other applica-
tions, such as games. The A-star algorithm is a special implementation
of Dijkstra and makes additional use of the destination's coordinate. The