Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
1999-06-25
2001-01-30
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
C701S026000, C701S201000, C701S208000, C701S209000, C340S990000, C073S17800T
Reexamination Certificate
active
06182008
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computerized mapping software programs, and more specifically, to computerized mapping software programs that calculate a route between multiple destinations and allow alterations to the calculated route.
BACKGROUND OF THE INVENTION
Computerized mapping products are achieving widespread use today. Such mapping programs are commonly used to automate the task of calculating a route from a starting destination to an ending destination. In addition, most mapping programs allow a user to include additional destinations to be visited along the route. Developers of computerized mapping programs are plagued by the problem of ordering the destinations to be visited along the route. More specifically, in the past, developers of computerized mapping programs have had problems providing a mechanism for determining the order in which destinations are visited along the route prior to calculating a route that visits all of the destinations. This problem is sometimes referred to as the “traveling salesman” problem.
In the past, some mapping programs have avoided the problem altogether. Those mapping programs simply calculate a route that visits each destination in the order in which the destinations are provided by a user. That solution is the least optimal because a user rarely provides destinations along a route in an optimal sequence. More likely, a user will simply provide destinations to be visited in a stream-of-consciousness manner. The result may be that the calculated route is substantially longer than optimal.
Other mapping programs address the problem by not ordering the destinations until all of the destinations are input, and then calculating an optimal order for all of the destinations. There are several problems with this approach as well. For example, calculating the true optimal order for the destinations requires comparing each and every possible order of the destinations. That calculation is manageable with three or four destinations, but as the number of destinations increases, the number of calculations necessary quickly overwhelms the computing power of any conventional computer. Consequently, many techniques have been developed to approximate the true optimal solution, such as simulated annealing and other such techniques that result in a highly optimal order for the destinations.
Unfortunately, those techniques still have the disadvantage that they are computationally intensive. The number of computations required to solve the travelling salesman problem still grows rapidly (non-linearly) with the number of destinations. Users of mapping programs do not typically like to wait long periods of time while a mapping program simply orders destinations to be visited even prior to calculating the optimal route. For that reason, if a user inputs several destinations to be visited, using a technique that calculates a highly-optimal order for the destinations introduces unwanted delay.
That undesirable feature of prior mapping programs is particularly undesirable to users that remove or add destinations to an existing list because existing mapping programs, which operate on all of the destinations at once, require a complete reorder of all destinations each time a single new destination is added.
These and other problems render the existing systems and methods less than satisfactory. Until now, a solution to those problems has eluded those skilled in the art. Accordingly, there is a need for a system or method of ordering destinations to be visited that is computationally efficient and achieves an acceptable order based on the total length of a route connecting all of the destinations.
SUMMARY OF THE INVENTION
The present invention overcomes the problems identified above by providing a computer-implementable method of ordering destinations to be visited in a manner that is computationally-efficient and provides an acceptable level of optimization. This is achieved by building the route one destination at a time. As each destination to be visited is added, the method positions it within an existing order of destinations such that the new order results in the shortest increase to the straight-line length of the route. More specifically, a single, continuous line connects each of the destinations to be visited. The continuous line is composed of multiple “links.” Each link is a straight line connecting two destinations. The total length of the continuous line is the sum of the lengths of each link. The order of the destinations defines the order in which the continuous line visits each destination.
A list is maintained that includes all of the existing destinations sorted in the order in which each destination is to be visited. When a new destination to be visited is added, a new list is generated that includes the new destination. Preferably, the new list orders all the destinations, including the new destination, such that the new destination is visited in an efficient manner along the route. The present invention overcomes the limitations of the prior art by inserting the new destination between two existing destinations without otherwise reordering the existing destinations. Then the existing link between a first existing destination and a second existing destination is replaced with two new links: (1) one link from the first existing destination to the new destination, and (2) a second link from the new destination to the second existing destination. This method results in essentially a single change (replacing only one existing link) to the existing order of destinations. By only making this single change, the present invention drastically reduces the computational time required for the reordering of destinations. In this manner, the present invention overcomes many of the problems identified in the prior art.
The present invention identifies which existing link to replace in the following manner. When the new destination is input, the present invention calculates the straight-line lengths of two new links: (1) a first new link from the currently-first destination in the list of existing destinations, and (2) a second new link from the new destination to the currently-second destination in the list of existing destinations. That value is stored for comparison.
Next, the present invention replaces the link between the currently-second existing destination and the currently-third existing destination with two other new links: (1) a new first link between the second existing destination and the new destination, and (2) a new second link from the new destination to the third existing destination. Again, the invention subtracts from the sum of those two lengths the length of a straight line connecting the currently-second destination with the currently-third destination. The value of that subtraction represents the straight-line impact on the route of inserting the new destination between the currently-second destination and the currently-third destination. If that calculated value is shorter than the value stored during the previous iteration, then the current iteration is identified as preferable.
Those computations are repeated for each subsequent link between existing destinations. When all of the links between existing destinations have been tested, the present invention has identified as preferable one existing link which, when replaced with two links to and from the new destination, results in a shortest total length for the continuous line that connects all of the destinations. Finally, the present invention creates a new order for all the destinations by inserting the new destination between existing destinations identified as preferable. In this manner, a new list is created that orders each of the destinations, including the new destination, such that the continuous line visiting the destinations in the listed order is the shortest.
Additionally, the present invention may evaluate whether it would be preferable to insert the new destination at either the beginning of the list or at the end of the list. In other wo
Berry Nicholas
Nikiel Mark A.
Beaulieu Yonel
Christensen O'Connor Johnson & Kindness PLLC
Cuchlinski Jr. William A.
Microsoft Corporation
LandOfFree
Ordering destinations along a route using a shortest line... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ordering destinations along a route using a shortest line..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ordering destinations along a route using a shortest line... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2450540