Alternate routes generation

Details Alternate routes generation Alternate routes generation

2002-04-02

2004-05-04

Zanelli, Michael J. (Department: 3661)

Data processing: vehicles, navigation, and relative location

Navigation

Employing position determining equipment

C701S209000

Reexamination Certificate

active

06732048

ABSTRACT:

AREA OF THE INVENTION
The present invention relates to generation of point-to-point routes on a transportation network. More specifically, the invention provides various methods and apparatus for automatic construction of suboptimal routes that are useful alternatives to the optimal route.
BACKGROUND OF THE INVENTION
The standard approach for generating optimal point-to-point routes is to utilize Dijkstra's algorithm [see Introduction To Algorithms, Thomas H. Cormen et al, 1990; ISBN 0-07-013143-0, Chap. 25, incorporated herein by reference] to find the route for which the overall travel cost (travel distance, travel time, etc.) is a minimum. Dijkstra's algorithm does this by systematically exploring a large number of possible routes, which can easily number in the billions. Ultimately, the algorithm constructs the least-costroute, discarding all of the other routes along the way.
Frequently, however, one wishes to construct other routes that have costs that approach the low cost of the optimal route and that also differ significantly from the optimal route and from one other. For example, a nearly optimal route that uses highways B and C rather than highways A and C can be most useful, particularly if the user has an aversion to using highway A(frequent delays, high tolls, etc.) or a preference for highway B (light traffic, few boulevard stops, etc.). In contrast, a nearly optimal route that represents only a slight departure from the optimal route (turning one block earlier or later, for instance) provides very little additional information to the user, since minor route departures generally produce minor consequences.
There are ways to construct useful alternative routes manually. One can, for instance, prohibit use of one or more key street segments on the original route, by deleting them from the street network or by setting their costs to some very large value. One can also force the route to use some other route by judiciously selecting a waypoint on that other route, then generating the alternate route in two pieces (origin to waypoint, waypoint to destination). Since both approaches yield results that depend greatly upon the skill of the operator, neither approach is amenable to automation.
Of these types of methods the patent of DeGraaf (U.S. Pat. No. 5,878,368) makes use of these methods. User selects and designates as preferred or to be avoided specific sections or areas of a map or alters the costs of certain streets.
Hayami (U.S. Pat. No. 5,369,588) makes use of the way point method of altering a route selection process. By choosing a specific way point, it creates a bias toward some specific route alternative.
Okazaki (U.S. Pat. No. 5,684,704) uses heuristic methods of route selection combined with varying ranges for suitable searches depending on the rank, speed or other attribute of the street or roadway.
All of these use the individual's input to alter or affect the route choices. Thus, the skill and experience of the operator is essential.
SUMMARY OF THE INVENTION
The present invention provides methods and apparatus for automatically generating useful alternatives to the least-cost route from some origin point A to some destination point B. Each alternate route is generated, using the same method employed to obtain initial least-cost route, after first discouraging re-use of most street segments used by the least-cost route and all previously-generated alternate routes. The mechanism for discouraging re-use is to artificially inflate the costs associated with using those previously-used street segments.
An essential feature of the present invention is that the magnitude of the cost inflation is adjusted automatically so that: (1) as a rule, each alternate route requested differs significantly from both the original route and also differs significantly from every other alternate route generated so far, but route duplication is never prohibited outright; (2) significant route-to-route duplication is tolerated, but route-to-route duplication seldom exceeds 70%(or some other threshold value preselected by the designer or user) until all viable route alternatives have been generated. To accomplish this behavior, the magnitude of the cost inflation is initialized to a relatively small value (20%, or some other threshold value preselected by the designer or user), then is automatically increased in response to the amount of route duplication encountered as alternate routes are generated. If many near-optimal alternate routes exist, very little route duplication is encountered, and the cost inflation remains near its initial value. If instead few near-optimal alternate routes exist, much route duplication occurs, and the cost inflation is quickly increased to where significantly suboptimal alternate routes are generated. In the extreme case where no near-optimal alternate routes exist, the first attempt to generate an alternate route can produce total route duplication. At that point, the cost inflation is doubled (to 40%), and the alternate route is then regenerated using that higher cost inflation. All of this is accomplished without user feedback.
In the preferred embodiment, cost inflation is uniformly applied to previously used street segments, except that it is not applied to street segments in the proximity of the route origin and route destination. Specifically, it is imposed upon the middle 90% of the street segments used by the original route (and any earlier alternate route), leaving the first 5% and the last 5% of the street segment costs unchanged. The rationale for not including street segments near the origin and destination is that street segment re-use near the origin and destination is generally inconsequential, and is often unavoidable as well.
In another embodiment, cost inflation is applied non-uniformly to previously-used street segments. For example, to discourage what might be regarded as excessive re-use of some street segments, a higher amount of cost inflation can be applied to street segments that have been used more than once by the original and earlier alternate routes.
In another embodiment, an alternate route may be regenerated two or more times when route duplication exceeding 70% (relative to the original route and earlier alternate routes) persists, so that route duplication exceeding 70% is precluded altogether.


REFERENCES:
patent: 5220507 (1993-06-01), Kirson
patent: 5369588 (1994-11-01), Hayami et al.
patent: 5467276 (1995-11-01), Tsuyuki
patent: 5508930 (1996-04-01), Smith, Jr.
patent: 5521826 (1996-05-01), Matsumoto
patent: 5638280 (1997-06-01), Nishimura et al.
patent: 5684704 (1997-11-01), Okazaki
patent: 5878368 (1999-03-01), DeGraaf
patent: 6321161 (2001-11-01), Herbst et al.

Affiliated with

Also associated with

Rating

Alternate routes generation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Alternate routes generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alternate routes generation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3235426