Realtime computation of the optimum path between an origin and destination in a large network requires high-performance hardware resources, as it is a compute intensive process. Hierarchical searching techniques have proven to be able to reduce the search space while providing near optimum solutions. In order to implement route computations based on such searching techniques, an equivalent hierarchical database must be developed. In this paper, a multilevel hierarchical map representation has been proposed by incorporating the most desirable route planning considerations. Techniques for the efficient modelling of the roadway network have also been devised to ensure that prohibited turns can be represented accurately. A systematic procedure to map a physical roadway network into a digital hierarchical database as well as techniques to better manage the database of a large network (i.e. one with more than 10,000 nodes) during realtime computations have also been presented.
Samenvatting