Identifying a route configured to travel through multiple points of interest

• US 8,095,303 B1
• Filed: 04/29/2008
• Issued: 01/10/2012
• Est. Priority Date: 12/29/2006
• Status: Active Grant

• Current Assignee: AOL Inc. (Apollo Global Management, Inc.), Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: MapQuest, Inc. (System1 LLC)
• Inventors: Nesbitt, David W., Renner, W. Karl
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US12/111,657
• Time in Patent Office: 1,351 Days
• Field of Search: 701200-202, 701/209, 701/211, 340/988, 340/995.19, 34099524-99528
• US Class Current: 701/202
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

A computer-implemented method for identifying a route that is configured to travel through multiple points of interest includes receiving a query that includes an origin location, a destination location, and at least a first point of interest and a second point of interest. The method also includes identifying a perimeter that surrounds the received origin and destination locations in response to the query. The perimeter is then used to identify a set of locations for each of the first and second points of interest.

Claims

1. A computer-implemented method of evaluating locations to be included in a route that extends between a selected origin and a selected destination, and that passes through at least two additional locations corresponding to selected points of interest, the method comprising:

receiving an indication of a selected origin;

receiving an indication of a selected destination;

receiving selection of multiple points of interest;

determining a preliminary route between the selected origin and destination locations;

identifying a first set of locations corresponding to a first of the multiple points of interest;

identifying, from among the first set of locations corresponding to the first of the multiple points of interest, a first location that has a relatively short travel commitment to the preliminary route;

identifying a second set of locations corresponding to a second of the multiple points of interest;

identifying, from among the second set of locations corresponding to the second of the multiple points of interest, a second location that has a relatively short travel commitment to the preliminary route;

determining a travel commitment between the second location and the preliminary route;

identifying, from among the second set of locations corresponding to the second of the multiple points of interest, a third location that has a relatively short travel commitment to the first location;

determining a travel commitment between the first location and the third location;

determining whether the travel commitment determined between the first location and the third location is less than the travel commitment determined between the second location and the preliminary route; and

if the travel commitment determined between the first location and the third location is determined to be less than the travel commitment determined between the second location and the preliminary route, ranking a combination of the first and third locations higher than the first and second locations when evaluating locations to be included in the route.

2. The method of claim 1 further comprising:

identifying a perimeter surrounding the preliminary route,

wherein identifying the first set of locations corresponding to the first of the multiple points of interest comprises identifying, within the perimeter, a first set of locations corresponding to the first of the multiple points of interest; and

wherein identifying the second set of locations corresponding to the second of the multiple points of interest comprises identifying, within the perimeter, a second set of locations corresponding to the second of the multiple points of interest.

3. The method of claim 2 wherein the perimeter includes an elliptical shape.

4. The method of claim 2 further comprising determining an order in which the first point of interest or the second point interest are selected for purposes of identifying a set of locations, within the perimeter, for each based on which one of the first or second points of interest are least common point of interest.

5. The method of claim 1 wherein identifying the first set of locations corresponding to the first of the multiple points of interest includes first randomly selecting the first point of interest from among the multiple points of interest and then identifying the first set of locations corresponding to the first point of interest.

6. The method of claim 1 wherein identifying the first set of locations corresponding to the first of the multiple points of interest includes selecting the first point of interest based on presence or lack thereof of the first point of interest between the origin and destination locations and then identifying the first set of locations corresponding to the first point of interest.

7. The method of claim 1 wherein the travel commitment includes travel time or a travel distance.

8. The method of claim 7 wherein the travel commitment includes shortest travel time or shortest travel distance.

9. The method of claim 7 wherein the travel commitment includes travel distance along a road accessible to the preliminary route.

10. The method of claim 1 wherein identifying the second set of locations corresponding to the second of the multiple points of interest includes first randomly selecting the second point of interest from among the multiple points of interest and then identifying the second set of locations corresponding to the second point of interest.

11. The method of claim 1 wherein identifying the second set of locations corresponding to the second of the multiple points of interest includes selecting the second point of interest based on presence or lack thereof of the second point of interest between the origin and destination locations and then identifying the second set of locations corresponding to the second point of interest.

12. A computer-implemented method of evaluating locations to be included in a route that extends between a selected origin and a selected destination, and that passes through at least two additional locations corresponding to selected points of interest, the method comprising:

receiving an indication of a selected origin;

receiving an indication of a selected destination;

receiving selection of multiple points of interest;

determining a preliminary route between the selected origin and destination locations;

identifying a set of locations corresponding to a first and second of the multiple points of interest;

identifying, from among the set of locations, a first location corresponding to the first of the multiple points of interest and a second location corresponding to a second of the multiple points of interest, where the first location and second location collectively yield a shortest aggregated round-trip travel commitment from the preliminary route to the first location, from the first location to the second location, and back to the preliminary route; and

selecting a route based on the locations that were used to compute the shortest aggregated round-trip travel commitment.

13. The method of claim 12 further comprising:

identifying a perimeter surrounding the preliminary route;

wherein identifying the set of locations corresponding to the first and second of the multiple points of interest comprises identifying, within the perimeter, a set of locations corresponding to the first and second of the multiple points of interest.

14. The method of claim 13 wherein the perimeter includes an elliptical shape.

15. The method of claim 12 wherein the travel commitment includes travel time or a travel distance.

16. The method of claim 15 wherein the travel commitment includes shortest travel time or shortest travel distance.

17. The method of claim 15 wherein the travel commitment includes travel distance along a road accessible to the preliminary route.

18. The method of claim 12 further comprising:

determining a first round-trip travel commitment to/from a location corresponding to the first selected point of interest that has a shortest travel commitment to the preliminary route, among the locations corresponding to the first selected point of interest;

determining a second round-trip travel commitment to/from a location corresponding to the second selected point of interest that has a shortest travel commitment to the preliminary route, among the locations corresponding to the second selected point of interest;

determining whether the shortest aggregated round-trip travel commitment is greater or lesser than a summation of the first and second round-trip travel commitments;

if lesser, select the route based on the locations that were used to compute the shortest aggregated round-trip travel commitment; and

if greater, however, select the route based on the locations used to determine the first and second round-trip travel commitment.

19. At least one computer-readable storage medium storing instructions that, when executed, perform operations comprising:

receiving an indication of a selected origin;

receiving an indication of a selected destination;

receiving selection of multiple points of interest;

determining a preliminary route between the selected origin and destination locations;

identifying a first set of locations corresponding to a first of the multiple points of interest;

identifying, from among the first set of locations corresponding to the first of the multiple points of interest, a first location that has a relatively short travel commitment to the preliminary route;

identifying a second set of locations corresponding to a second of the multiple points of interest;

identifying, from among the second set of locations corresponding to the second of the multiple points of interest, a second location that has a relatively short travel commitment to the preliminary route;

determining a travel commitment between the second location and the preliminary route;

identifying, from among the second set of locations corresponding to the second of the multiple points of interest, a third location that has a relatively short travel commitment to the first location;

determining a travel commitment between the first location and the third location;

determining whether the travel commitment determined between the first location and the third location is less than the travel commitment determined between the second location and the preliminary route; and

if the travel commitment determined between the first location and the third location is determined to be less than the travel commitment determined between the second location and the preliminary route, ranking a combination of the first and third locations higher than the first and second locations when evaluating locations to be included in the route.

20. At least one computer-readable storage medium storing instructions that, when executed, perform operations comprising:

receiving an indication of a selected origin;

receiving an indication of a selected destination;

receiving selection of multiple points of interest;

determining a preliminary route between the selected origin and destination locations;

identifying a set of locations corresponding to a first and second of the multiple points of interest;

identifying, from among the set of locations, a first location corresponding to the first of the multiple points of interest and a second location corresponding to a second of the multiple points of interest, where the first location and second location collectively yield a shortest aggregated round-trip travel commitment from the preliminary route to the first location, from the first location to the second location, and back to the preliminary route; and

selecting a route based on the locations that were used to compute the shortest aggregated round-trip travel commitment.