RELATED WORK

Shortest path problem has been an active area of research in network theory over the past three decades. Many algorithms have proposed. Their emphasis has been on using topographic and geographic knowledge and reasoning to solve the problem. The major concern in AI are spatial knowledge representation and reasoning. [8] proposed a technique to use level structure of the road network to help searching for a path efficiently. This is similar to our minor and major road structure and it can be extended to any number of levels. We will explain inefficiency of this algorithm by an example. Let us suppose that source and the destination nodes are on the minor roads. Then, the algorithm proposed in [8] will search for shortest path to a node in the major road network from the source node . It will then do again like this for the destination node to find a node on the major road network. Then it uses Dijkstra's algorithm for shortest path between and in the major road network.

This technique minimizes the time travelling on minor roads and also reduces the search space. However, the problem is that the two nodes and could be on the wrong major roads. Then the path found will not be shortest path. Figure 5 explains this situation. The path searched by this technique for source and destination is: . But, it is clear form the figure that it is a longer path than the shortest path searched by our technique. Therefore, it is not a good solution. Our approach solved this problem by using the minor and major road networks in the source and the destination neighbourhood and only the major road network in the container geo-object containing both the neighbourhood. There is no chance of landing on wrong major roads.

Another advantage of our approach is that it partitions the whole network into smaller subnetworks contained in prefectures, cities and neighbourhood. This is important for a large road network.

Another related AI-based system is proposed in [6]. In this approach the major road network is not pruned off and therefore, after deciding the grid sub-networks the shortest path algorithm searches in all the major road network with minor road networks in grid networks. But, in our approach we also prune off the search space in major road network and give a substantially reduced major road network to the shortest path algorithm for search (see problem solving algorithm). This part of the major road network may be in a city containing source and destination neighbourhood or a prefecture or a country at the highest level.