ROUTE FINDING BY USING KNOWLEDGE ABOUT ROAD NETWORKS

Abstract

In recent years, automatic route searching in road maps has become a main feature in modern vehicle navigation systems. This search for optimal routes is the shortest path problem. But maps are generically large, they contain huge amount of information such as turn restrictions, topologies, etc. Searching for optimal routes is both time and resource consuming even for the best shortest path algorithms. Furthermore, without taking motorists' route preferences into account, solutions produced are likely to be impractical. In this project, we have taken up the challenge to solve these problems via the use of knowledge-based technique, good data structure (data structure consists of data format and data organisation) and a good searching strategy. We started off our project by searching for a good data format that we could use to represent road maps. Our data format must capture the huge amount of information that resides in road networks efficiently and effectively. A correct and precise road network representation is crucial to route searching so as to avoid generating routes that are impossible to follow. To be efficient and effective, a good data format must satisfy a few points. Firstly, the data format must not in any way complicate route searching process Secondly, it must avoid redundancy and duplication of data. And finally, it must be open enough so that any changes to road networks will not cause major restructuring of the database. In the second part of our research, we study the use of knowledge-based technique in our application. Researches done in the past to determine motorists' route preferences have shown that motorists' prefer routes that are convenient and offer the shortest travelling times to those that offer the shortest distances. Coupling this knowledge of motorists' route preferences with our knowledge about road networks and their characteristics, we propose all organisation or road network database and a route searching strategy that would help us develop a route searching system that is more time efficient and uses considerably less resource. In addition, this system also generates routes that are more human oriented. Our emphasis on data structure of road database and our proposed route searching strategy has enabled us to develop a Knowledge-Based Route Searching System prototype based on Singapore road network. We tested the time performance of this prototype and the quality of the routes found with a set of 3 hundred test data that is randomly generated. The results were encouraging and these led us to believe that such systems can be of great use in an in-vehicle navigational system.