Patent ID: 6732048
Filing Date: 2004-05-04
Classification: G01C

Abstract:
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.