Matching stored routes to a required route

• US 6,751,548 B2
• Filed: 11/20/2001
• Issued: 06/15/2004
• Est. Priority Date: 11/20/2000
• Status: Active Grant

• Current Assignee: Isabelle Boulard, Max Fox
• Original Assignee: Isabelle Boulard, Max Fox
• Inventors: Boulard, Isabelle, Fox, Max
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US10/007,940
• Publication Number:
  US 20020069015A1
• Time in Patent Office: 938 Days
• Field of Search: 701/202, 701/201, 701/209, 701/210
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A computer-implementable method for identifying the preferred route to be used, or ordering a set of routes to be used in order of preferability, for a given route requirement, in a computationally efficient manner is disclosed. The computer-implementable method selects a subset of stored routes having origins within a configurable radius of the required origin and destinations within a configurable radius of the required destination, calculates the distances between the two origins, between the two destinations, and between each origin and its corresponding destination, to compute various indicators of the similarity between the required route and each stored route in the subset. The computer-implementable method presents the selected stored routes ordered by a selected route-similarity indicator. The first such ordered selected stored route is the preferred route.

Claims

1. In a computer mapping program, a method for identifying a stored route to be used for a given required route, comprising:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein the preferable route minimizes the difference from the required route to the stored route, calculated by the method of;

calculating the distance between the required route origin and the stored route origin to achieve a first value;

calculating the distance between the stored route origin and the stored route destination to achieve a second value;

calculating the distance between the stored route destination and the required route destination to achieve a third value;

adding the first value and the second value and the third value to achieve a fourth value;

calculating the distance between the required route origin and the required route destination to achieve a fifth value; and

subtracting the fifth value from the fourth value to determine the difference from the required route to the stored route.

2. The method of claim 1, wherein all stored routes are evaluated and ordered by the difference from the required route to each stored route, this ordered list then being identified as the ordered most preferable routes by detour from the required route to the stored routes.

3. In a computer mapping program, a method for identifying a stored route to be used for a given required route, comprising:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein the preferable route minimizes the difference from the stored route to the required route, calculated by the method of;

calculating the distance between the stored route origin and the required route origin to achieve a first value;

calculating the distance between the required route origin and the required route destination to achieve a second value;

calculating the distance between the required route destination and the stored route destination to achieve a third value;

adding the first value and the second value and the third value to achieve a fourth value;

calculating the distance between the stored route origin and the stored route destination to achieve a fifth value; and

subtracting the fifth value from the fourth value to determine the difference from the stored route to the required route.

4. The method of claim 3, wherein all stored routes are evaluated and ordered by the difference from each stored route to the required route, this ordered list then being identified as the ordered most preferable routes by detour from the stored routes to the required route.

5. In a computer mapping program, a method for identifying a stored route to be used for a given required route, comprising:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein the preferable route minimizes the difference from the stored route to the required route and the difference from the required route to the stored route, calculated by the method of;

determining the difference from the required route to the stored route to achieve a first value;

determining the difference from the stored route to the required route to achieve a second value; and

selecting the lower of the first and second values to determine the minimum route difference.

6. The method of claim 5, wherein all stored routes are evaluated and ordered by the minimum route difference, this ordered list then being identified as the ordered most preferable routes by the minimum route difference.

7. In a computer mapping program, a method for identifying a stored route to be used for a given required route, comprising:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein a plurality of required routes are each processed individually and sequentially by the steps described.

8. A computer-readable medium have computer executable instructions for identifying a stored route to be used for a given route requirement, which when executed, comprise:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein the preferable route minimizes the difference from the required route to stored route, calculated by the method of;

calculating the distance between the required route origin and the stored route origin to achieve a first value;

calculating the distance between the stored route origin and the stored route destination to achieve a second value;

calculating the distance between the stored route destination and the required route destination to achieve a third value;

adding the first value and the second value and the third value to achieve a fourth value;

calculating the distance between the required route origin and the required route destination to achieve a fifth value; and

subtracting the fifth value from the fourth value to determine the difference from the required route to the stored route.

9. The computer-readable medium of claim 8, wherein all stored routes are evaluated and ordered by the difference from the required route to each stored route, this ordered list then being identified as the ordered most preferable routes by detour from the required route to the stored routes.

10. A computer-readable medium have computer executable instructions for identifying a stored route to be used for a given route requirement, which when executed, comprise:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein the preferable route minimizes the difference from the stored route to the required route, calculated by the method of;

calculating the distance between the stored route origin and the required route origin to achieve a first value;

calculating the distance between the required route origin and the required route destination to achieve a second value;

calculating the distance between the required route destination and the stored route destination to achieve a third value;

adding the first value and the second value and the third value to achieve a fourth value;

calculating the distance between the stored route origin and the stored route destination to achieve a fifth value; and

subtracting the fifth value from the fourth value to determine the difference from the stored route to the required route.

11. The computer-readable medium of claim 10, wherein all stored routes are evaluated and ordered by the difference from each stored route to the required route, this ordered list then being identified as the ordered most preferable routes by detour from the stored routes to the required route.

12. A computer-readable medium have computer executable instructions for identifying a stored route to be used for a given route requirement, which when executed, comprise:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein the preferable route minimizes the difference from the stored route to the required route and the difference from the required route to the stored route, calculated by the method of;

determining the difference from the required route to the stored route to achieve a first value;

determining the difference from the stored route to the required route to achieve a second value; and

selecting the lower of the first and second values to determine the minimum route difference.

13. The computer-readable medium of claim 12, wherein all stored routes are evaluated and ordered by the minimum route difference, this ordered list then being identified as the ordered most preferable routes by the minimum route difference.

14. A computer-readable medium have computer executable instructions for identifying a stored route to be used for a given route requirement, which when executed, comprise:

receiving a new required route; and

identifying a preferable stored route in a plurality of stored routes, the preferable stored route minimizing the sum of the length of a line connecting the origins of the stored route and the required route and the length of a line connecting the destinations of the stored route and the required route, wherein a plurality of required routes are each processed individually and sequentially by the computer-executable instructions described.