Identifying a route configured to travel through multiple points of interest

• US 8,781,729 B2
• Filed: 01/03/2012
• Issued: 07/15/2014
• Est. Priority Date: 12/29/2006
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Nesbitt, David W., Renner, W. Karl
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US13/342,436
• Publication Number:
  US 20120109509A1
• Time in Patent Office: 924 Days
• Field of Search: 701200-202, 701/209, 701/211, 701/400, 701408-410, 701/426, 340/988, 340/995.19, 34099524-99528
• US Class Current: 701/426
• 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 for determining a travel route, comprising:

identifying a first route between an origin and a destination;

identifying a first perimeter around the first route;

determining that there are less than a predetermined number of points of interest within the first perimeter;

identifying, in response to the determination that there are less than a predetermined number of points of interest within the first perimeter, a second perimeter around the first route, wherein the second perimeter is larger than the first perimeter;

identifying, within the second perimeter, a plurality of points of interest;

receiving a selection of a location from among the plurality of points of interest identified within the second perimeter; and

determining, using at least one processor, a second route between the origin and the destination, and comprising the selected location.

2. The method of claim 1, wherein the origin and the destination are selected by a user.

3. The method of claim 1, further comprising presenting to a user a categorized list of the points of interest identified within the second perimeter.

4. The method of claim 1, further comprising:

receiving a selection of two or more locations from among the plurality of points of interest identified within the second perimeter; and

determining a third route between the origin, the destination, and the selected locations.

5. The method of claim 4, wherein the third route is determined to minimize a travel commitment between the origin, the destination, and at least one of the selected locations.

6. The method of claim 5, further comprising:

determining a plurality of potential routes between the origin, the destination, and the selected locations;

determining travel commitments associated with the plurality of potential routes; and

selecting the potential route with the lowest determined travel commitment.

7. The method of claim 1, wherein identifying the first perimeter around the first route comprises:

multiplying a number (L) representing a distance between the origin and the destination by a factor (N) to produce a result (LN);

multiplying LN by a factor (I) to produce a result (LNI);

setting a first axis of the first perimeter based on LN; and

setting a second axis of the first perimeter based on LNI.

8. The method of claim 7, wherein determining that there are less than a predetermined number of points of interest within the first perimeter comprises determining that there are zero or less than a sufficient number of locations within the first perimeter;

and

wherein identifying the second perimeter comprises;

adjusting N; and

resetting at least one of the first perimeter'"'"'s first and second axes.

9. The method of claim 1, wherein determining that there are less than a predetermined number of points of interest within the first perimeter comprises:

determining that there are zero points of interest within the first perimeter.

10. A computer-based system for determining a travel route, the system comprising at least one processor and a storage medium that stores a plurality of instructions, the plurality of instructions being executable by the at least one processor for:

identifying a first route between an origin and a destination;

identifying a first perimeter around the first route;

determining that there are less than a predetermined number of points of interest within the first perimeter;

identifying, in response to the determination that there are less than a predetermined number of points of interest within the first perimeter, a second perimeter around the first route, wherein the second perimeter is larger than the first perimeter;

identifying, within the second perimeter, a plurality of points of interest;

receiving a selection of a location from among the plurality of points of interest identified within the second perimeter; and

determining a second route between the origin and the destination, and comprising the selected location.

11. The system of claim 10, wherein the origin and the destination are selected by a user.

12. The system of claim 10, further comprising instructions executable by the at least one processor for presenting to a user a categorized list of the plurality of points of interest identified within the second perimeter.

13. The system of claim 10, further comprising instructions executable by the at least one processor for:

receiving a selection of two or more locations from among the plurality of points of interest identified within the second perimeter; and

determining a third route between the origin, the destination, and the selected locations.

14. The system of claim 13, wherein the third route is determined to minimize a travel commitment between the origin, the destination, and at least one of the selected locations.

15. The system of claim 14, further comprising instructions executable by the at least one processor for:

determining a plurality of potential routes between the origin, the destination, and the selected locations;

determining travel commitments associated with the plurality of potential routes; and

selecting the potential route with the lowest determined travel commitment.

16. The system of claim 10, wherein the instructions for identifying the first perimeter around the first route comprise instructions for:

multiplying a number (L) representing a distance between the origin and the destination by a factor (N) to produce a result (LN);

multiplying LN by a factor (I) to produce a result (LNI);

setting a first axis of the first perimeter based on LN; and

setting a second axis of the first perimeter based on LNI.

17. The system of claim 16, wherein determining that there are less than a predetermined number of points of interest within the first perimeter comprises determining that there are zero or less than a sufficient number of locations within the first perimeter;

and

wherein identifying the second perimeter comprises;

adjusting N; and

resetting at least one of the first perimeter'"'"'s first and second axes.

18. The system of claim 10, wherein determining that there are less than a predetermined number of points of interest within the first perimeter comprises:

determining that there are zero points of interest within the first perimeter.