ROUTE FINDING ALGORITHM

This section presents the problem solving method in the proposed approach. It consists of four main steps. Below is the algorithm.

Step 1. Get the type of the road on which source node ($S$) is located by invoking appropriate method
in source node.

if this type matches with the major road

then goto step 2

else

1. Find the index number of the neighbourhood in which $S$ is located by invoking appropriate method in source node. ( we call this neighbourhood as source neighbourhood )
2. Retrieve the road network in the source neighbourhood.

Step 2. Get the type of the road on which destination node ($D$) is located by invoking appropriate method in destination node.

if this type matches with the major road

then goto step 3

else

1. Find the index number of the neighbourhood in which $D$ is located by invoking appropriate method in the destination node. (we call this neighbourhood as destination neighbourhood)
2. Retrieve the road network in the destination neighbourhood.

Step 3.

if Both, the source and the destination nodes, are on minor roads.

then

1. Find the name of the the container geo-object containing source neighbourhood and destination neighbourhood.
2. Retrieve the major road network in the container geo-object.
3. goto step 4.

else if Both, the source and the destination nodes, are on major roads.

then

1. Find the name of the the container geo-object containing $S$ and $D$.
2. Retrieve the major road network in the container geo-object.
3. goto step 4.

else if One (S or D) of the source or destination nodes is on the minor road and the other is on major road.

then

1. Find the name of the container geo-object containing neighbourhood that contains the node which is on the minor road, and the other node that is on major road.
2. Retrieve the major road network in the container geo-object

Step 4. Run the shortest path algorithm such as Dijkstra's algorithm, with this augmented road network.

Now, let us do analysis of the complexity of the algorithm. When all the network is in the hard disk then road network in the source and the destination neighbourhood is transferred into the main memory in a constant time. (1) and (2) in step 1 and 2 can be done in a constant of time because each node has an index number of the neighbourhood containing it. (1) in step 3 is also done in a constant of time because each neighbourhood or container geo-object also knows the name of it's container geo-object. Retrieving road network in neighbourhood and container geo-object is also done in a constant of time as we have designed our road network in such a way that it contains the road network at each level as a group of links. Main computation is done in step 4. Since the number of nodes and arcs (links) have been substantially reduced, it will run much faster.

Now, we will present a complete example of problem solving in our proposed approach. Suppose a user would like to go from source $S$ to destination $D$ shown in Figure 5. The road network (thin dotted lines are minor roads and thin solid lines are boundaries of container geo-objects) is retrieved in neighbourhood containing $S$ and $D$ and major road network is retrieved in the geo-object containing source and destination neighbourhood. And then this augmented road network with knowledge such as, peak hours, road construction, road facilities, etc., in the source and destination neighbourhood and the geo-object containing these neighbourhood is used to search the shortest path between $S$ and $D$ i.e. .

Figure 5: A Route Finding Example