Alternate routes generation

• US 20020143464A1
• Filed: 04/02/2002
• Published: 10/03/2002
• Est. Priority Date: 04/02/2001
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Maptuit Corp. (Verizon Communications Inc.)
• Inventors: Blewitt, Ronald L.
• Granted Patent: US 6,732,048 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• 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 least-cost route from Point A to Point B, each route composed of a sequence of route components with associated costs as follows:

a) the 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 (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;

reapplying method 1a with this larger cost inflation factor produces the first alternate route.

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

a) increasing the cost inflation factor further, in proportion to the extent to which the first alternate route re-uses components of the first route,

b) applying this increased cost inflation factor to the original costs associated with components of both the first route and the first alternate route,

c) constructing the second alternate route by reapplying the steps of claim 1 (c &

d) in the presence of those inflated component costs,

3. The method of claim 2 wherein additional alternate routes are created by applying the inflated cost factor used in previous calculations of alternate routes 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.