Back to results
US 6,732,048 B2Granted
Alternate routes generation
AssigneeMaptuit Corporation
InventorRonal L. Blewitt
Life of this patent
Estimating the term…
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.
Claims6
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 more elements
Dependencies are inferred from the claim text.