Ordering destinations along a route using a shortest line approximation

• US 6,182,008 B1
• Filed: 06/25/1999
• Issued: 01/30/2001
• Est. Priority Date: 06/25/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nikiel, Mark A., Berry, Nicholas
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Beaulieu, Yonel
• Application Number:
  US09/344,437
• Time in Patent Office: 585 Days
• Field of Search: 701/202, 701/208, 701/25, 701/26, 701/201, 701/209, 340/990, 340/995, 707/1, 707/100, 731/78.R
• US Class Current: 701/202
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A computer-implementable method for ordering destinations to be visited in a computationally-efficient manner and which achieves an acceptable level of optimization of the order for those destinations is disclosed. The computer-implementable method orders destinations to be visited by identifying the position in an existing order of destinations where the insertion of a new destination will result 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 new destination is added at a position in the existing order of destinations that results in the shortest increase to the straight-line length of the continuous line.

Claims

1. In a computer mapping program, a method for identifying an order for destinations to be visited by a route, comprising:

receiving an indication that a new destination is to be added to the route;

identifying a preferable position in a plurality of possible positions in a list of existing destinations to insert the new destination, the list of existing destinations being sorted in the order in which the route visits each destination, the preferable position minimizing the length of a continuous line connecting all the destinations to be visited along the route; and

inserting the new destination in the identified position.

2. The method of claim 1, wherein identifying the position comprises:

evaluating each pair of destinations in the list of destinations to determine the impact on the length of the continuous line resulting from inserting the new destination between each pair of destinations; and

identifying the pair of destinations having the lowest impact on the length of the continuous line as the preferable position.

3. The method of claim 2, wherein the impact of inserting the new destination between one pair of destinations comprises a length by which the continuous line connecting all the destinations would be extended if the new destination were inserted between the one pair of destinations.

4. The method of claim 3, wherein the impact of inserting the new destination between the one pair of destinations is calculated by the method of:

calculating a distance from a first existing destination in the one pair of destinations to the new destination to achieve a first value;

calculating a distance from a second existing destination in the one pair of destinations to the new destination to achieve a second value;

calculating a distance between the first existing destination and the second existing destination to achieve a third value; and

subtracting the third value from the sum of the first value and the second value to determine the impact of inserting the new destination between the first existing destination and the second existing destination.

5. The method of claim 2, wherein identifying the position comprises:

evaluating a terminal position in the list of destinations to determine an impact on the length of the continuous line of inserting the new destination at the terminal position;

determining if the impact of the terminal position on the length of the continuous line is preferable to the impact of the pair of destinations on the length of the continuous line; and

if the impact of the terminal position on the length of the continuous line is preferable to the impact of the pair of destinations on the length of the continuous line, identifying the terminal position as the preferable position.

6. The method of claim 5, wherein the terminal position includes a beginning position located prior to a first existing destination in the list of existing destinations.

7. The method of claim 5, wherein the terminal position includes an ending position located after a last existing destination in the list of existing destinations.

8. The method of claim 5, wherein:

evaluating the terminal position comprises calculating the distance from the new destination to an existing terminal position in the list of existing destinations; and

determining if the impact of the terminal position is preferable to the impact of the pair of destinations comprises comparing the distance from the new destination to the existing terminal position to the impact of the pair of destinations on the length of the continuous line.

9. The method of claim 1, wherein the plurality of possible positions includes a beginning position located prior to a first existing destination in the list of existing destinations.

10. The method of claim 1, wherein the plurality of possible positions includes an ending position located after the last existing destination in the list of existing destinations.

11. The method of claim 1, wherein each possible position in the plurality of possible position is a position located between subsequent destinations in the plurality of possible destinations.

12. In a computer mapping program having a plurality of destinations and a plurality of links, each link being a straight line joining two consecutive destinations in the plurality of destinations, the plurality of destinations being ordered sequentially from a first destination to a last destination, the order of the plurality of destinations corresponding to the order in which a continuous line visits each destination, a method of adding a new destination to the plurality of destinations, comprising:

(a) identifying a link in the plurality of links as a current link to be tested;

(b) calculating the impact of inserting the new destination between the two consecutive destinations joined by the current link, by;

(i) calculating a distance from one of the two consecutive destinations to the new destination to achieve a first value;

(ii) calculating a distance from the other consecutive destination to the new destination to achieve a second value;

(iii) calculating a distance between the two consecutive destinations to achieve a third value; and

(iv) subtracting the third value from the sum of the first value and the second value to achieve the impact of inserting the new destination between the two consecutive existing destinations;

(c) if any links have not been tested in the plurality of links, identifying an untested link as the current link and repeating (b); and

(d) when all of the links have been tested, identifying the link resulting in the lowest impact as a replaceable link.

13. The method of claim 12, further comprising:

(e) inserting the new destination in the plurality of destinations between the two destinations joined by the replaceable link.

14. The method of claim 12, further comprising:

(e) calculating an impact of inserting the new destination at a terminal position in the order of the plurality of destinations by calculating the distance from the new destination to the existing destination at the terminal position in the order of the plurality of destination; and

(f) if the impact of inserting the new destination at the terminal position is less than the lowest impact of inserting the new destination between two consecutive destinations, inserting the new destination at the terminal position in the order of the plurality of destinations.

15. The method of claim 14, wherein the terminal position comprises a beginning position prior to the first destination in the plurality of destinations.

16. The method of claim 14, wherein the terminal position comprises an ending position after the last destination in the plurality of destinations.

17. A computer-readable medium having computer executable instructions for ordering a list of destinations to be visited along a route in response to a new destination being provided, which when executed, comprise:

receiving an indication that a new destination is to be added to the route;

identifying a preferable position in the list of destinations to insert the new destination, the list of existing destinations being sorted in the order in which the route visits each destination, the preferable position minimizing the length of a continuous line connecting all the destinations to be visited along the route; and

inserting the new destination in the identified position.

18. The computer-readable medium of claim 17, wherein identifying the preferable position comprises:

if the list of destinations comprises two or more existing destinations, evaluating each pair of destinations in the list of destinations to determine, for each pair of destinations, an impact on the route of inserting the new destination between each pair of destinations; and

identifying the pair of destinations having the lowest impact on the route as the preferable position.

19. The computer-readable medium of claim 18, wherein if the list of destinations comprises fewer than two existing destinations, adding the new destination to a terminal position in the list of destinations.

20. The computer-readable medium of claim 18, wherein the impact on the route of inserting the new destination between one pair of destinations comprises a straight-line distance by which the distance between the one pair of destinations is exceeded by the sum of a distance from the new destination to one destination in the pair of destinations and a distance from the new destination to the other destination in the pair of destinations.

21. The computer-readable medium of claim 18, further comprising:

determining if inserting the new destination at a terminal position in the list of destinations results in a lesser impact on the route; and

if inserting the new destination at the terminal position results in a lesser impact on the route, inserting the new destination at the terminal position.

22. The computer-readable medium of claim 21, further comprising, if inserting the new destination at the terminal position results in a greater impact on the route, inserting the new destination at the preferable position.

23. The computer-readable medium of claim 22, wherein the terminal position comprises a beginning position prior to a first destination in the list of destinations.

24. The computer-readable medium of claim 22, wherein the terminal position comprises an ending position after a last destination in the list of destinations.