As was explained in Section 2.4, planning an optimum route on a real-world road
network containing millions of nodes and edges, takes too long if a standard shortest
path algorithm, such as Dijkstra’s algorithm [Dijkstra, 1959] is used. The number of
edges that have to be examined in order to plan an optimum route is just too large.

In this chapter, we discuss an approach that enables us to reduce the size of the road-
graph used for planning routes, while it remains possible to plan an optimum route
between any two nodes in the road network. This approach is based on the con-
struction of a so-called partition.

The A*-algorithm is a shortest path algorithm that is based on Dijkstra’s algorithm [Dijk-
stra, 1959]. In order to reduce the number of evaluated edges, the A*-algorithm [Hart,
Nilsson & Raphael, 1968] uses an estimation of the cost from a node to the des-
tination, which is called the h-value. The minimum cost from the start node to a
node is called the g-value. The A*-algorithm selects a node with minimum expected
cost from the start node to the destination, i.e. a node with minimum g h-value.
Subsequently, all the adjacent nodes of the selected node are determined and their
minimum expected costs are updated. The process is repeated until no better route
from start node s to destination node d can be found. As explained a modified A*-
algorithm [Hart, Nilsson & Raphael, 1968] can be used to plan an optimum route in
a roadgraph with turn restrictions. Because of these turn restrictions, we select the
edge with minimum expected cost from the start node to the destination.