NAVIGATION DEVICE AND GUIDE ROUTE SEARCH METHOD

• US 20110251783A1
• Filed: 03/11/2011
• Published: 10/13/2011
• 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
• Granted Patent: US 8,977,487 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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. Accordingly, a subsequent search operation is performed on a partial detour route in the first guide route, based on the map data containing the lowest level.

Claims

1. A navigation device comprising:

a map data storage unit configured 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 an 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 configured to search for a first guide route from a departure point to a destination by using the map data of the lowest level corresponding to an area surrounding the departure point and the destination, 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;

a partial route extracting unit configured to extract a first partial route from the first guide route, wherein a difference between a straight-line distance and a distance measured between nodes at opposite ends of the first partial route is greater than a predetermined value;

a second guide route search unit configured 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; and

a guide route setting unit configured 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.

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 includes:

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 switched 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 switched at the second node, and

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.

4. The navigation device according to claim 3, wherein

the partial route extracting unit further includes a third node identifying unit configured to sequentially determine 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,

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.

5. The navigation device according to claim 3, wherein

the partial route extracting unit further includes:

a third node identifying unit configured to sequentially determine 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, 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 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 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.

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

a straight-line distance determining unit configured 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.

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

a 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.

8. 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.

9. 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 difference 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.

10. 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.

11. A guide route search method in a navigation device, the navigation device including:

a map data storage unit configured 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 an amount of information is greater at a lower level of the hierarchical levels than at a higher level of the hierarchical levels; and

a first guide route search unit configured to search for a first guide route from a departure point to a destination by using the map data of the lowest level corresponding to an area surrounding the departure point and the destination, 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;

the guide route search method comprising;

extracting a first partial route from the first guide route, wherein a difference between a straight-line distance and a distance measured between nodes at opposite ends of the first partial route is greater than a predetermined value;

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; and

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.

12. The guide route search method according to claim 11, 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.

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

the extracting first the partial route 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.

14. The guide route search method according to claim 13, 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.

15. The guide route search method according to claim 13, 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.

16. The guide route search method according to claim 11, 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.

17. The guide route search method according to claim 11, 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.