Alternate routes generation

• US 6,732,048 B2
• Filed: 04/02/2002
• Issued: 05/04/2004
• Est. Priority Date: 04/02/2001
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Maptuit Corp. (Verizon Communications Inc.)
• Inventors: Blewitt, Ronal L.
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US10/114,839
• Publication Number:
  US 20020143464A1
• Time in Patent Office: 763 Days
• Field of Search: 701/201, 701/209, 701/210, 340/995.19
• US Class Current: 701/210
• 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
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

An improved method to automatically generate one or more useful alternatives to the least-cost point-to-point route on a road network. The method discourages reuse of road sections that have been previously used by inflating the costs associated with these road sections before the recalculation of the search algorithm.

Claims

1. A route-finding method that automatically constructs an optimal route and one or more route alternatives to the optimal route from Point A to Point B, each route composed of a sequence of route components with associated costs as follows:

a) a first route is constructed using a method that identifies the route, for which the sum of the component costs is minimum,

b) an initial cost inflation factor is applied to the costs associated with the components of the first route, after which an interim route is constructed by reapplying the method of step a in the presence of those inflated component costs,

c) if an acceptably small fraction of the components of the interim route are re-used components of the first route, the interim route becomes the first alternate route,

d) if an unacceptably large fraction of the components of the interim route are re-used components of the first route, the cost inflation factor is increased, the increase being proportional to the extent to which the interim route re-uses components of the first route; and

then reapplying step a with this larger cost inflation factor to produce the first alternate route.

2. The method of claim 1 wherein a second alternate route is constructed by:

e) creating a first cost inflation factor for a second alternate route, increased over the cost inflation factor used for the first alternate route in proportion to the extent to which the first alternate route re-uses components of the first route,

f) applying the first cost inflation factor of step e to the original component costs of both the first route and the first alternate route,

g) constructing a second interim route by reapplying step a using the inflated component costs of step f to identify a route with a minimum sum of component costs.

h) reapplying step c and determining if the second interim route becomes a second alternate route,

i) if an unacceptably large fraction of the components of the second interim route are re-used components of the first route and the first alternate route, a second cost inflation factor is increased over the first cost inflation cost factor of step e, the increase being proportional to the extent to which the second interim route re-uses components of the first route and the first alternate route, and then reapplying step f and g using the second cost inflation factor, to determine a second alternate route.

3. The method of claim 2 wherein additional alternate routes are created by applying the inflated cost factor used in calculation of the immediately preceding alternate routes route to any components that are used in any prior alternate routes.

4. The method of claim 1 wherein the cost inflation factor is selectively applied to some, rather than all, components of the previous route or routes, based on their relative remoteness from Points A and B.

5. The method of claim 1 wherein the cost increase is attenuated or amplified for some previously used components, based on relative proximity to, or relative remoteness from Points A and B.

6. The method of claim 5 wherein the cost increase is amplified for those previously used components that have been used and then re-used.