Using knowledge about the road network for route finding

Imagine a tourist rents a car and plans to drive around a city. Before going from one place to another, he/she needs to know a good way. In network theory, this is the shortest path problem. Shortest path algorithms are often used to solve the problem. However, these algorithms are wasteful in terms of computation when applied to the route finding task. They may also produce solutions that are not appropriate for human drivers. In practice, knowledge about the road network can often be used to substantially reduce the time and space required in computation, and to produce solutions that are suitable for human users. In this project, we have explored the approach of combining a shortest path algorithm with knowledge about the road network to solve the problem. A system (called KB-RFinder) based on this approach has been implemented for route finding in Singapore