Method and apparatus for searching a route
First Claim
1. A method for selecting an optimum route on a map by using map data including a hierarchical structure of a plurality of road network data at different degrees of minuteness, said plurality of road network data are hierarchically structured so that the degree of minuteness becomes lower from a lower hierarchical level to an upper hierarchical level, and correspondence data showing correspondence with the road network data on the upper hierarchical level is previously recorded for the road network data on the lower hierarchical level, said route searching method comprising:
- a first step of obtaining minimum arrival costs from a starting point of a search about individual nodes existing in a predetermined search area, the predetermined search area extending from the starting point of the search on the road network data on the lower hierarchical level, the cost including distance and/or travel time;
a second step of selecting nodes located on an upper hierarchical level existing link, which is a link existing on the road network data on the lower hierarchical level that also exists on the upper hierarchical level, on the basis of said correspondence data from among the nodes for which the minimum arrival costs have been obtained in said first step,a third step of obtaining an arrival cost to a node in common with the upper hierarchical level which first appears when following said upper hierarchical level existing link on the basis of said correspondence data for each node selected in said second step, anda fourth step of obtaining a minimum arrival cost from the search starting point to each common node on the basis of the minimum arrival cost to the selected node obtained in said first step and the arrival cost to the common node obtained in said third step,wherein the optimum route is searched for on the road network data on the upper hierarchical level using the minimum arrival costs to individual said common nodes obtained in said fourth step as initial conditions.
1 Assignment
0 Petitions
Accused Products
Abstract
An optimum route searching device 5 conducts a search in a predetermined area on road network data on a lower hierarchical level to obtain minimum arrival costs to individual nodes in the search area and then selects a node located on an upper hierarchical level existing in from the search area. Then the optimum route searching device 5 obtains a remaining cost to a node common with the upper hierarchical level which first appears on the upper hierarchical level existing link. Then the optimum route searching device 5 obtains a minimum arrival cost from the starting point of the search to the common node on the basis of the minimum arrival cost to the selected node and the remaining cost to the common node. The minimum arrival cost to the common node obtained at this time is used as initial conditions for a route search performed on the road network data on the upper hierarchical level. This makes it possible to shift the search results on the lower hierarchical level to the upper hierarchical level without causing an abnormal route such as a U-turn path and a bypass path.
-
Citations
12 Claims
-
1. A method for selecting an optimum route on a map by using map data including a hierarchical structure of a plurality of road network data at different degrees of minuteness, said plurality of road network data are hierarchically structured so that the degree of minuteness becomes lower from a lower hierarchical level to an upper hierarchical level, and correspondence data showing correspondence with the road network data on the upper hierarchical level is previously recorded for the road network data on the lower hierarchical level, said route searching method comprising:
-
a first step of obtaining minimum arrival costs from a starting point of a search about individual nodes existing in a predetermined search area, the predetermined search area extending from the starting point of the search on the road network data on the lower hierarchical level, the cost including distance and/or travel time; a second step of selecting nodes located on an upper hierarchical level existing link, which is a link existing on the road network data on the lower hierarchical level that also exists on the upper hierarchical level, on the basis of said correspondence data from among the nodes for which the minimum arrival costs have been obtained in said first step, a third step of obtaining an arrival cost to a node in common with the upper hierarchical level which first appears when following said upper hierarchical level existing link on the basis of said correspondence data for each node selected in said second step, and a fourth step of obtaining a minimum arrival cost from the search starting point to each common node on the basis of the minimum arrival cost to the selected node obtained in said first step and the arrival cost to the common node obtained in said third step, wherein the optimum route is searched for on the road network data on the upper hierarchical level using the minimum arrival costs to individual said common nodes obtained in said fourth step as initial conditions. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. An apparatus for selecting an optimum route on a map using map data including a hierarchical structure of a plurality of road network data at different degrees of minuteness, comprising:
-
map data storing means for storing the map data including the plurality of hierarchical road network data, said plurality of road network data being hierarchically structured so that the degree of minuteness becomes lower from a lower hierarchical level to an upper hierarchical level; correspondence data storing means for storing correspondence data showing correspondence between the road network data on the lower hierarchical level and the road network data on the upper hierarchical level; first cost obtaining means for obtaining minimum arrival costs from a starting point of a search for individual nodes existing in a predetermined search area, the predetermined search area extending from the starting point of the search on the road network data on the lower hierarchical level, the cost including distance and/or travel time; node selecting means for selecting a node located on an upper hierarchical level existing link, which is a link existing in the upper hierarchical level road network data, from among the nodes for which the minimum arrival costs have been obtained by said first cost obtaining means on the basis of said correspondence data; second cost obtaining means for obtaining an arrival cost to a node in common with the upper hierarchical level which first appears when following said upper hierarchical level existing link on the basis of said correspondence data for each node selected by said node selecting means; and third cost obtaining means for obtaining a minimum arrival cost from the search starting point to each common node on the basis of the minimum arrival cost obtained by said first cost obtaining means and the arrival cost obtained by said second cost obtaining means; wherein the optimum route is newly searched for on the road network data on the upper hierarchical level using the minimum arrival costs to individual common nodes obtained by said third cost obtaining means as initial conditions.
-
Specification