Using Knowledge to Isolate Search in Route Finding

Abstract

Traveling is a part of every person's day-to-day life. With the massive and complicated road network of a modem city (or country), fmding a good route to travel from one place to another is not a simple task. 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 fmding task. They may also produce solutions that are not suitable for human drivers. In this paper, we present an approach that uses knowledge about the road network to substantially reduce the time and space required in computation, and to ensure human oriented solutions. Within this framework, three alternative methods are proposed, which may be used in different situations. A system has also been implemented for route fmding in Singapore.