# US 6,732,048 B2 · Alternate routes generation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,732,048 B2
- Document ID: US6732048B2
- Status: Granted
- Kind: B2
- Application number: 10/114,839
- Filed: 2002-04-02
- Published: 2002-10-03
- Granted: 2004-05-04
- Earliest claimed: 2001-04-02
- Assignees: Maptuit Corporation
- Inventors: Ronal L. Blewitt
- Web page: https://patentgrep.com/patent/US6732048B2

## CPC

- G01C 21/3461: {Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries}
- G01C 21/3484: {Personalized, e.g. from learned user behaviour or user-defined profiles}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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