Route searching method

• US 6,263,277 B1
• Filed: 08/07/2000
• Issued: 07/17/2001
• Est. Priority Date: 08/07/2000
• Status: Expired due to Term

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Tanimoto, Satoshi, Endo, Koichi, Hayes, David
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US09/633,244
• Time in Patent Office: 344 Days
• Field of Search: 701/200, 701/207, 701/208, 701/209, 701/211, 701/212, 701/210, 701/201, 340/988, 340/990, 340/995, 731/78.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

Abstract

A method of route searching in a navigation apparatus used to search out a route leading to a destination. Map information is produced by having the nodes on both ends of a link, the length of the link, the speed limit in the link, and the functional class of the link included in the link information. In making the route search, the speed limit in the link is corrected on the basis of the straight line distance to the destination and the functional class of the link, the time for traveling a link is calculated on the basis of the corrected speed limit and the link length, and the route minimizing the time required for reaching a destination is searched out on the basis of the link passing time. In the described case, the functional class is determined using road factors such as the width, speed limit, and type of the road. Correction is made such that the speed limit on higher class links becomes larger and the speed limit on lower class links becomes smaller. Also, the time necessary to pass through an intersection is estimated based on the functional classes of the traveled and intersecting links.

Claims

1. A method of route searching in a navigation apparatus for searching out a route leading to a destination comprising the steps of:

providing map information having the nodes on both ends of a link, the length of the link, the speed limit of the link, and the functional class of the link included in the link information;

correcting, in making the route search, the speed limit in said link on the basis of a straight line distance to a destination and the functional class of the link;

calculating the time for traveling on a link on the basis of the corrected speed limit and the link length; and

searching, on the basis of the link travel time, for a route minimizing the time required for reaching a destination.

2. A method of route searching according to claim 1, further comprising the steps of:

determining said functional class using functional factors of the road, including at least one from the group of width, speed limit, and type of road; and

setting a speed correcting value so that the speed limit in a higher class link becomes larger and the speed limit in a lower class link becomes smaller.

3. A method of route searching according to claim 2, further comprising the step of:

making the correcting value larger as the straight-line distance to the destination gets longer.

4. A method of route searching according to claim 3, further comprising the steps of:

providing a table for storing speed limit correcting values based on the combination of the straight line distance to a destination and the functional class of a link; and

correcting the speed limit of a link using the correcting value obtained from said table.

5. A method of route searching according to claim 1, further comprising the steps of:

estimating the time for passing through a node by considering the functional classes of an intersecting road and the vehicle'"'"'own link; and

correcting said link passing time by adding in said node passing time.

6. A method of route searching according to claim 5, further comprising the steps of:

determining said functional class using functional factors of the road, including at least one from the group of width, speed limit, and type of road; and

setting a speed correcting value so that the speed limit in a higher class link becomes larger and the speed limit in a lower class link becomes smaller.

7. A method of route searching according to claim 6, further comprising the step of:

making the correcting value larger as the straight-line distance to the destination gets longer.

8. A method of route searching according to claim 7, further comprising the steps of:

providing a table for storing speed limit correcting values based on the combination of the straight line distance to a destination and the functional class of a link; and

correcting the speed limit of a link using the correcting value obtained from said table.

9. A method of route searching in a navigation apparatus for searching out a route leading to a destination comprising the steps of:

providing map information having the nodes on both ends of a link, the length of the link, the speed limit of the link, and the functional class of the link included in the link information;

correcting, in making the route search, the speed limit in said link on the basis of the straight line distance to a destination and the functional class of the link;

calculating the time for traveling on a link on the basis of the corrected speed limit and the link length;

searching, on the basis of the link travel time, for a route minimizing the time required for reaching a destination;

performing a route search using links of the same class as the functional class of the link to which the start point belongs from said starting point toward a destination until a higher class link is reached;

performing a route search by using links of the same class as the functional class of the link to which the destination belongs from said destination toward the starting point until a higher class link is reached;

setting the node of the higher class link reached in the search from said starting point as a new starting point and setting the node of the higher class link reached in the search from said destination as a new destination, and thereupon repeating said processing by using said higher class links; and

connecting, when the destination is reached, the routes of each class obtained in the search from the side of the starting point and the routes of each class obtained in the search from the side of the destination, sequentially, thereby forming a guided route.

10. A method of route searching according to claim 9, further comprising the step of:

making identical the class of the link having said new starting point as the node and the class of the link having said new destination as the node.

11. A method of route searching according to claim 10, further comprising the steps of:

determining said functional class using functional factors of the road, including at least one from the group of width, speed limit, and type of road; and

setting a speed correcting value so that the speed limit in a higher class link becomes larger and the speed limit in a lower class link becomes smaller.

12. A method of route searching according to claim 11, further comprising the step of:

making the correcting value larger as the straight-line distance to the destination gets longer.

13. A method of route searching according to claim 12, further comprising the steps of:

providing a table for storing speed limit correcting values based on the combination of the straight line distance to a destination and the functional class of a link; and

correcting the speed limit of a link using the correcting value obtained from said table.

14. A method of route searching according to claim 9, further comprising the steps of:

estimating the time for passing through a node by considering the functional classes of an intersecting road and the vehicle'"'"'s own link; and

correcting said link passing time by adding in said node passing time.

15. A method of route searching according to claim 14, further comprising the step of:

making identical the class of the link having said new starting point as the node and the class of the link having said new destination as the node.

16. A method of route searching according to claim 15, further comprising the steps of:

determining said functional class using functional factors of the road, including at least one from the group of width, speed limit, and type of road; and

setting a speed correcting value so that the speed limit in a higher class link becomes larger and the speed limit in a lower class link becomes smaller.

17. A method of route searching according to claim 16, further comprising the step of:

making the correcting value larger as the straight-line distance to the destination gets longer.

18. A method of route searching according to claim 17, further comprising the steps of:

providing a table for storing speed limit correcting values based on the combination of the straight line distance to a destination and the functional class of a link; and

correcting the speed limit of a link using the correcting value obtained from said table.

19. A method of route searching in a navigation apparatus for searching out a route leading to a destination comprising the steps of:

providing map information having the speed limit and functional class of each link included in the link information;

performing a route search using links of the same class as the functional class of the link to which the start point belongs from said starting point toward a destination until a higher class link is reached;

performing a route search by using links of the same class as the functional class of the link to which the destination belongs from said destination toward the starting point until a higher class link is reached;

setting the node of the higher class link reached in the search from said starting point as a new starting point and setting the node of the higher class link reached in the search from said destination as a new destination, and thereupon repeating said processing by using said higher class links; and

connecting, when the destination is reached, the routes of each class obtained in the search from the side of the starting point and the routes of each class obtained in the search from the side of the destination, sequentially, thereby forming a guided route.

20. A method of route searching according to claim 19, further comprising the step of:

making identical the class of the link having said new starting point as the node and the class of the link having said new destination as the node.

21. A method of route searching according to claim 20, further comprising the steps of:

determining said functional class using functional factors of the road, including at least one from the group of width, speed limit, and type of road; and

setting a speed correcting value so that the speed limit in a higher class link becomes larger and the speed limit in a lower class link becomes smaller.

22. A method of route searching according to claim 21, further comprising the step of:

making the correcting value larger as the straight-line distance to the destination gets longer.

23. A method of route searching according to claim 22, further comprising the steps of:

providing a table for storing speed limit correcting values based on the combination of the straight line distance to a destination and the functional class of a link; and

correcting the speed limit of a link using the correcting value obtained from said table.

24. A method of route searching according to claim 19, further comprising the steps of:

estimating the time for passing through a node by considering the functional classes of an intersecting road and the vehicle'"'"'s own link; and

calculating a link passing time including said node passing time.

25. A method of route searching according to claim 24, further comprising the step of:

making identical the class of the link having said new starting point as the node and the class of the link having said new destination as the node.

26. A method of route searching according to claim 25, further comprising the steps of:

determining said functional class using functional factors of the road, including at least one from the group of width, speed limit, and type of road; and

setting a speed correcting value so that the speed limit in a higher class link becomes larger and the speed limit in a lower class link becomes smaller.

27. A method of route searching according to claim 26, further comprising the step of:

making the correcting value larger as the straight-line distance to the destination gets longer.

28. A method of route searching according to claim 27, further comprising the steps of:

providing a table for storing speed limit correcting values based on the combination of the straight line distance to a destination and the functional class of a link; and

correcting the speed limit of a link using the correcting value obtained from said table.