Navigation device and guide route search method

• US 8,977,487 B2
• Filed: 03/11/2011
• Issued: 03/10/2015
• Est. Priority Date: 04/12/2010
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Doi, Shinobu
• Primary Examiner(s): Algahaim, Helal A
• Assistant Examiner(s): Hilgendorf, Dale W
• Application Number:
  US13/046,231
• Publication Number:
  US 20110251783A1
• Time in Patent Office: 1,460 Days
• Field of Search: 701/408, 701/409, 701/410, 701/411, 701/420, 701/532, 701/533
• US Class Current: 701/411
• 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/096827 where the route is computed onboard

Abstract

A navigation device and a guide route search method prevents searching for a detour route, and shortens the time required for setting an eventual guide route. A first partial route is extracted from a first guide route found in accordance with map data divided into three hierarchical levels, based on information about a road network. The first guide route is the route from the current location to a destination. A second partial route is obtained by performing a route search between the nodes at opposite ends of the first partial route, based on the map data containing the lowest level. A second guide route is obtained by replacing the first partial route in the first guide route with the second partial route, and is set as the eventual guide route.

Claims

1. A navigation device comprising:

a vehicle location detecting unit having a CPU, and configured to receive distance or speed information from one or more sensors;

a map data storage unit operatively coupled to the vehicle detecting unit and CPU to store map data, the map data divided into a plurality of hierarchical levels based on an amount of information about a road network, wherein the amount of information is greater at a lower level of the hierarchical levels than at a higher level of the hierarchical levels;

a first guide route search unit operatively coupled to the vehicle detecting unit and CPU, to search for a first guide route from a departure point to a destination point by using the map data of the lowest level corresponding to an area surrounding the departure point and the destination point, respectively, and using the map data of levels higher than the lowest level corresponding to an intermediate region outside the area surrounding the departure point and the destination point, respectively;

a partial route extracting unit operatively coupled to the vehicle detecting unit and CPU, to extract a first partial route from the first guide route, the first partial route having a ratio between a straight-line distance and a distance measured between nodes at opposite ends thereof being greater than a predetermined value, the partial route extracting unit further including;

a first node identifying unit configured to identify a first node that is closest to one end of the first guide route among nodes forming the first guide route, wherein levels of the map data are changed at the first node;

a second node identifying unit configured to identify a second node that is closest to the other end of the first guide route, wherein levels of the map data are changed at the second node, wherein the partial route extracting unit is configured to extract the first partial route from the higher search route formed by nodes between the first node and the second node;

a second guide route search unit operatively coupled to the vehicle detecting unit and CPU, to generate a second partial route by performing a route search between nodes at opposite ends of the first partial route using the map data including the lowest level;

a guide route setting unit operatively coupled to the vehicle detecting unit and CPU, to set an eventual guide route representing a second guide route formed by replacing the first partial route of the first guide route with the second partial route;

a node number determining unit operatively coupled to the vehicle detecting unit and CPU, to determine whether the number of nodes between the nodes at opposite ends of the first partial route is less than a predetermined number to facilitate the route search between the nodes at opposite ends of the first partial route by the second guide route search unit; and

a straight-line distance determining unit operatively coupled to the vehicle detecting unit and CPU, to determine whether the straight-line distance between nodes at opposite ends of the first partial route is shorter than a predetermined distance, and wherein, if the straight-line distance between the nodes at opposite ends of the first partial route is less than the predetermined distance, the second guide route search unit performs the route search between the nodes at opposite ends of the first partial route by using only the map data of the lowest level.

2. The navigation device according to claim 1, wherein the partial route extracting unit extracts the first partial route from a higher search route found from the first guide route, based on the map data of the higher levels of the hierarchical levels.

3. The navigation device according to claim 2, wherein

the partial route extracting unit further includes a third node identifying unit configured to sequentially determine whether a ratio between a straight-line distance between the first node and each of a plurality of determination object nodes, and a distance measured along the higher search route between the first node and the corresponding determination object node, is larger than the predetermined value,

wherein a determination object node farthest from the first node is selected as the first node to be subjected to the determination among the plurality of determination object nodes forming the higher search route,

the third node identifying unit configured to identify a third node that is a determination object node first determined to have a larger difference value than the predetermined value, and

wherein the partial route extracting unit is configured to extract a route between the first node and the third node as the partial route among the nodes forming the higher search route.

4. The navigation device according to claim 2, wherein

the partial route extracting unit further includes:

a third node identifying unit configured to sequentially determine whether a ratio between a straight-line distance between the first node and each determination object node, and a distance measured along the higher search route between the first node and the determination object node, is larger than a second predetermined value, wherein the second predetermined value is less than the predetermined value;

wherein a determination object node farthest from the first node is selected as the first node to be subjected to the determination among the determination object nodes forming the higher search route;

the third node identifying unit identifying a third node that is a determination object node first determined to have a larger difference value than the second predetermined value; and

a fourth node identifying unit configured to sequentially determine whether a ratio between a straight-line distance between the third node and each determination object node, and a distance measured along the higher search route between the third node and the determination object node, is larger than the predetermined value;

wherein a determination object node farthest from the third node is selected as the first node to be subjected to the determination among the determination object nodes between the first node and the third node of the nodes forming the higher search route;

the fourth node identifying unit configured to identify a fourth node that is a determination object node first determined to have a larger difference value than the predetermined value, and

wherein the partial route extracting unit is configured to extract a route between the third node and the fourth node as the partial route from the higher search route.

5. The navigation device according to claim 1, further comprising:

the node number determining unit configured to determine whether the number of nodes between the nodes at opposite ends of the first partial route is less than a predetermined number; and

wherein, if the number of nodes between the nodes at opposite ends of the first partial route is less than the predetermined number, the second guide route search unit performs the route search between the nodes at opposite ends of the first partial route using only the map data of the lowest level.

6. The navigation device according to claim 1, wherein,

when the second partial route is found by the second guide route search unit using the map data of the higher levels, the partial route extracting unit extracts a third partial route from the second partial route, wherein a difference between a straight-line distance and a distance measured along the second partial route between nodes at opposite ends of the third partial route is greater than the predetermined value,

the second guide route search unit generates a fourth partial route by performing a route search between the nodes at opposite ends of the third partial route using map data containing the lowest level, and

the guide route setting unit sets an eventual guide route representing a third guide route formed by replacing the third partial route of the second guide route with the fourth partial route.

7. The navigation device according to claim 1, wherein

the partial route extracting unit further extracts a fifth partial route from a route formed by subtracting the second partial route from the second guide route, wherein a ratio between a straight-line distance, and a distance measured along the second guide route between nodes at opposite ends of the fifth partial route is greater than a predetermined value;

the second guide route search unit generates a sixth partial route by performing a route search between the nodes at opposite ends of the fifth partial route extracted by the partial route extracting unit, using the map data including the lowest level; and

the guide route setting unit sets an eventual guide route representing a fourth guide route formed by replacing the fifth partial route in the second guide route with the sixth partial route.

8. The navigation device according to claim 1, further comprising:

a first required time calculating unit configured to calculate a first required time required for traveling on the first partial route;

a second required time calculating unit configured to calculate a second required time by dividing the straight-line distance between the nodes at opposite ends of the first partial route by a predicted travel speed in accordance with a type of road included only in map data one level lower than the map data used in the search for the first partial route;

a time determining unit configured to determine whether the second required time is greater than the first required time; and

wherein the second guide route search unit performs the route search between the nodes at opposite ends of the first partial route by using the map data including the lowest level, only when the time determining unit determines that the second required time is not greater than the first required time.

9. A guide route search method in a navigation device having a vehicle location detecting unit and CPU, and receiving distance or speed information from one or more sensors, the method comprising:

storing map data, by a map data storage unit, the map data divided into a plurality of hierarchical levels based on an amount of information about a road network, wherein the amount of information is greater at a lower level of the hierarchical levels than at a higher level of the hierarchical levels; and

searching, by a first guide route search unit operatively coupled to the vehicle detecting unit and CPU, for a first guide route from a departure point to a destination point by using the map data of the lowest level corresponding to an area surrounding the departure point and the destination point, respectively, and using the map data of levels higher than that of the lowest level, corresponding to an intermediate region outside the area surrounding the departure point and the destination point, respectively;

extracting a first partial route from the first guide route, the first partial route having a ratio between a straight-line distance and a distance measured between nodes at opposite ends thereof being greater than a predetermined value, wherein extracting the first partial route further includes;

identifying a first node that is closest to one end of the first guide route among nodes forming the first guide route, wherein levels of the map data are switched at the first node;

identifying a second node that is closest to the other end of the first guide route, wherein levels of the map data are switched at the second node; and

extracting the first partial route from the higher search route formed by nodes between the first node and the second node;

generating a second partial route by performing a route search between nodes at opposite ends of the first partial route using the use of the map data including the lowest level;

setting an eventual guide route representing a second guide route formed by replacing the first partial route of the first guide route with the second partial route; and

determining, using a node number determining unit operatively coupled to the vehicle detecting unit and CPU, whether the number of nodes between the nodes at opposite ends of the first partial route is less than a predetermined number to facilitate the route search between the nodes at opposite ends of the first partial route; and

determining, using a straight-line distance determining unit operatively coupled to the vehicle detecting unit and CPU, whether the straight-line distance between nodes at opposite ends of the first partial route is shorter than a predetermined distance, and wherein, if the straight-line distance between the nodes at opposite ends of the first partial route is less than the predetermined distance, the performing the route search between the nodes at opposite ends of the first partial route by using only the map data of the lowest level.

10. The guide route search method according to claim 9, wherein the extracting the first partial route includes extracting the first partial route from a higher search route found from the first guide route, based on the map data of the higher levels of the hierarchical levels.

11. The guide route search method according to claim 10, wherein

the extracting the first partial route further includes:

sequentially determining whether a difference between a straight-line distance between the first node and each determination object node, and a distance measured along the higher search route between the first node and the determination object node, is larger than the predetermined value;

wherein a determination object node farthest from the first node is selected as the first node to be subjected to the determination among the determination object nodes forming the higher search route;

identifying a third node that is a determination object node first determined to have a larger difference value than the predetermined value; and

extracting a route from the first node to the third node as the first partial route among the nodes forming the higher search route.

12. The guide route search method according to claim 10, wherein

the extracting the first partial route further includes:

sequentially determining whether a difference between a straight-line distance between the first node and each determination object node, and a distance measured along the higher search route between the first node and the determination object node, is larger than a second predetermined value smaller than the predetermined value;

wherein a determination object node farthest from the first node is selected as the first node to be subjected to the determination among the determination object nodes forming the higher search route;

identifying a third node that is a determination object node first determined to have a larger difference value than the second predetermined value;

sequentially determining whether a difference between a straight-line distance between the third node and each determination object node, and a distance measured along the higher search route between the third node and the determination object node, is larger than the predetermined value, wherein a determination object node farthest from the third node is selected as the first node to be subjected to the determination among the determination object nodes between the first node and the third node forming the higher search route;

identifying a fourth node that is a determination object node first determined to have a larger difference value than the predetermined value; and

extracting a route between the third node and the fourth node as the first partial route from the higher search route.

13. The guide route search method according to claim 9, wherein

extracting the first partial route includes determining whether the straight-line distance between the nodes at opposite ends of the first partial route is shorter than a predetermined distance, and

generating the second partial route includes performing the route search between the nodes at opposite ends of the first partial route using only the map data of the lowest level, when the straight-line distance between the nodes at opposite ends of the first partial route is determined to be shorter than the predetermined distance.

14. The guide route search method according to claim 9, wherein

extracting the partial route includes determining whether the number of nodes between the nodes at opposite ends of the first partial route is less than a predetermined number, and

generating the second partial route includes performing the route search between the nodes at opposite ends of the first partial route by using only the map data of the lowest level, when the number of nodes between the nodes at opposite ends of the first partial route is determined to be less than the predetermined number.