Method and apparatus for finding shortest overall path of multiple destinations by navigation system

• US 6,691,027 B1
• Filed: 06/15/2002
• Issued: 02/10/2004
• Est. Priority Date: 06/15/2002
• Status: Expired due to Fees

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Tu, Ihung S.
• Primary Examiner(s): NGUYEN, THU V
• Application Number:
  US10/174,697
• Time in Patent Office: 605 Days
• Field of Search: 701/200, 701/201, 701/208, 701/211, 701/213, 340/990, 340/995, 342/357, 342/457
• US Class Current: 701/202
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A method for finding a shortest overall path length from the start to the final destination when a user of a navigation system wants to visit many intermediate destinations before the final destination. The method includes the steps of calculating a route to all of the destinations and tentatively determining an overall route specifying an order of tour destination where the overall route includes two or more route segments each connecting two destinations, checking the overall route as to whether any two route segments intersect with one another, and identifying the destinations of the route segments intersecting one another and reversing the order of destinations so that the two route segments no longer intersect one another.

Claims

1. A navigation method for finding an optimum route of tour having multiple destinations, comprising the following steps of:

specifying two or more intermediate destinations to visit before a final destination;

calculating a route to all of the destinations and tentatively determining an overall route specifying an order of tour of the intermediate destinations before reaching the final destination, said overall route including two or more route segments each connecting two destinations;

checking the overall route as to whether any two route segments intersect with one another; and

identifying the destinations of the route segments intersecting one another and reversing the order of destinations of the intersecting route segments so that the two route segments no longer intersect with one another.

2. A navigation method as defined in claim 1, wherein said step of checking the overall route includes a step of calculating and varying X-Y coordinates of any route segments to find if there is any intersecting point between the two route segments.

3. A navigation method as defined in claim 1, wherein said step of reversing the order of destinations includes a step of detecting a first route segment and a second route segment intersecting with one another where the first route segment comes before the second route segment in the overall route, and a step of identifying a second destination of the first route segment and a first destination of the second route segment.

4. A navigation method as defined in claim 3, wherein said step of reversing the order of destination includes a step of reversing the order of the second destination of the first route segment and the first destination of the second route and any destinations therebetween.

5. A navigation method as defined in claim 1, wherein said step of reversing the order of destination includes a step of identifying a first route segment R_{(i, i+1)} and a second route segment R_{(j, j+1)} intersecting with one another where the first route segment comes earlier than the second route segment in the overall route, and reversing the order of a second destination i+1 of the first route segment R_{(i, i+1)} and a first destination j of the second route segment R_{(j, j+1)} and any destinations between the destinations i+1 and i.

6. A navigation system for finding an optimum route of tour having multiple destinations, comprising:

means for specifying two or more intermediate destinations to visit before a final destination;

means for calculating a route to all of the destinations and tentatively determining an overall route specifying an order of tour of the intermediate destinations before reaching the final destination, said overall route including two or more route segments each connecting two destinations;

means for checking the overall route as to whether any two route segments intersect with one another; and

means for identifying the destinations of the route segments intersecting one another and reversing the order of destinations of the intersecting route segments so that the two route segments no longer intersect with one another.

7. A navigation system as defined in claim 6, wherein said means for checking the overall route includes means for calculating and varying X-Y coordinates of any route segments to find if there is any intersecting point between the two route segments.

8. A navigation system as defined in claim 6, wherein said means for reversing the order of destinations includes means for detecting a first route segment and a second route segment intersecting with one another where the first route segment comes before the second route segment in the overall route, and means for identifying a second destination of the first route segment and a first destination of the second route segment.

9. A navigation system as defined in claim 8, wherein said means for reversing the order of destination includes means for reversing the order of the second destination of the first route segment and the first destination of the second route and any destinations therebetween.

10. A navigation method as defined in claim 6, wherein said means for reversing the order of destination includes means for identifying a first route segment R_{(i, i+1)} and a second route segment R_{(j, j+1)} intersecting with one another where the first route segment comes earlier than the second route segment in the overall route, and reversing the order of a second destination i+1 of the first route segment R_{(i, i+1)} and a first destination j of the second route segment R_{(j, j+1)} and any destinations between the destinations i+1 and i.