Method and apparatus for searching a route

• US 5,899,955 A
• Filed: 12/24/1996
• Issued: 05/04/1999
• Est. Priority Date: 12/28/1995
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Fushimi, Makoto, Ueyama, Yoshiki, Yagyu, Takeshi
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/774,322
• Time in Patent Office: 861 Days
• Field of Search: 701/200, 701/201, 701/202, 701/208, 701/209, 701/210, 701/25, 701/23, 701/211, 701/212, 701/213, 340/460, 340/988, 340/990, 340/995, 73/178 R
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/0969 having a display in the form of a map

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.

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.

2. The route searching method according to claim 1, wherein said correspondence data includes:

first correspondence data indicating that a node included in the road network data on the lower hierarchical level is a node located on said upper hierarchical level existing link, and

second correspondence data indicating a position on the corresponding upper hierarchical level existing link for the node located on said upper hierarchical level existing link,

wherein said second step selects the node located on said upper hierarchical level existing link on the basis of said first correspondence data, and

said third step obtains the arrival cost to said common node on the basis of said second correspondence data.

3. The route searching method according to claim 2, wherein said first correspondence data includes parent link data for specifying a corresponding upper hierarchical level existing link.

4. The routs searching method according to claim 2, wherein said second correspondence data includes a ratio of occupation of the arrival cost from the node located on said upper hierarchical level existing link to a node at an end of the corresponding upper hierarchical level existing link in a cost of the entirety of the corresponding upper hierarchical level existing link.

5. The route searching method according to claim 2, wherein sad second correspondence data includes an arrival cost from the node located on said upper hierarchical level existing link to the node at the end of the corresponding upper hierarchical level existing link.

6. The route searching method according to claim 2, wherein said second step selects a node located on said upper hierarchical level existing link and located in the vicinity of said predetermined search area from among the nodes for which the minimum arrival costs have been obtained in said first step.

7. The route searching method according to claim 1, wherein said correspondence data includes:

first correspondence data indicating whether a link included in the lower hierarchical level road network data is a link existing also on the upper hierarchical level road network data, and

second correspondence data indicating that a node included in the lower hierarchical level road network data is a common node which exists also in the upper hierarchical level road network data,

wherein said second step selects the node located on said upper hierarchical level existing link on the basis of said first correspondence data, and

said third step performs an external search in an extended search area by using the upper hierarchical level existing link until a common node specified by said second correspondence data is found for each node selected in said second step to obtain the arrival cost to each common node.

8. The route searching method according to claim 7, wherein said second step selects the node located on said upper hierarchical level existing link and located in the vicinity of said predetermined search area from among the nodes for which the minimum arrival costs have been obtained in said first step.

9. The route searching method according to claim 7, wherein said plurality of hierarchical road network data are divided into a plurality of units,

each unit of said road network data records an adjacent node for indicating correspondence between connecting parts of adjacent units for a road divided at a connecting part between the adjacent units,

said correspondence data further includes third correspondence data indicating the position on the corresponding upper hierarchical level existing link for said adjacent node located on said upper hierarchical level existing link,

wherein said third step obtains the arrival cost to said common node on the basis of said third correspondence data when said adjacent node appears in said external search.

10. The route searching method according to claim 9, wherein said correspondence data further includes parent node data for specifying a node at an end of the corresponding upper hierarchical level existing link for said adjacent node located on said upper hierarchical level existing link.

11. The route searching method according to claim 1, wherein said correspondence data includes parent link data indicating a link on the upper hierarchical level road network data corresponding to a link included in the lower hierarchical level road network data,

said second step selects the node located on said upper hierarchical level existing link on the basis of said parent link data, and

said third step performs an external search in an extended search area using the upper hierarchical level existing link for each node selected in said second step to a node immediately before a change in said parent link data to obtain an arrival cost to each common node.

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.