In this paper, solutions to the representation and storage of road network are presented toward the route planning for vehicle navigation system. In respect to the representation of road network, the principle of defining nodes is presented, i.e., node is a "strategy point" or a "control point" where the travel route may be changed. According to this principle, nodes are classified into six types. The corresponding representation methods for some special or complex cases in urban road network in China are given. As far as the road network for route planning is concerned, the connectivity has two senses, i.e., the physical adjacency and the accessibility in practical travel. In addition, the connectivity of road network is described completely by means of constructing dual network. As to the storage structure of road network, two solutions are proposed. One is to store the dual network of road network with the forward star structure, which is a compact network storage structure satisfying the needs of route planning. The other one is to straight store road network with the generalized forward star structure, which can represent turn restrictions and intersection delays.
Abstract