IDENTIFYING A ROUTE CONFIGURED TO TRAVEL THROUGH MULTIPLE POINTS OF INTEREST

• US 20150081206A1
• Filed: 11/21/2014
• Published: 03/19/2015
• Est. Priority Date: 05/05/2006
• Status: Abandoned Application

• 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
• Application Number:
  US14/550,446
• Publication Number:
  US 20150081206A1
• Time in Patent Office: Days
• US Class Current: 701/408
• 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 identifying a route that is configured to travel through multiple points of interest, the method comprising:

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;

in response to receiving the query, identifying a perimeter that surrounds the received origin and destination locations;

using the identified perimeter as a basis for identifying a first set of potential locations that corresponds to the received first point of interest and that represents less than all potential locations corresponding to the first point of interest;

using the identified perimeter as a basis for identifying a second set of potential locations that corresponds to the received second point of interest and that represents less than all potential locations corresponding to the second point of interest;

selecting, from the first and second set of locations, respectively, a single first potential location corresponding to the received first point of interest and a single second potential location corresponding to the received second point of interest; and

displaying, as an advanced route, a route from the origin location to the destination location that travels through the selected single first potential location corresponding to the received first point of interest and the selected single second potential location corresponding to the received second point of interest.

2. The computer implemented method of claim 1 wherein the first point of interest and the second point of interest each include an indication of an establishment having multiple locations associated therewith.

3. The computer-implemented method of claim 1 wherein identifying the perimeter that surrounds the received origin and destination locations includes identifying an elliptical perimeter.

4. The computer-implemented method of claim 1 further comprising:

determining whether each of the first and second points of interest include at least one location within the perimeter; and

expanding parameters of the perimeter if it is determined that at least one of the first or second point of interest does not include the at least one location within the perimeter.

5. The computer-implemented method of claim 4 wherein identifying the perimeter that surrounds the received origin and destination locations includes identifying an elliptical perimeter.

6. The computer-implemented method of claim 1 wherein selecting the single first potential location corresponding to the received first point of interest and the single second potential location corresponding to the received second point of interest further includes:

identifying a preliminary route as an starting solution that includes one first location associated with the first point of interest and one second location associated with the second point of interest, wherein the first and second locations are selected from the first and second sets of potential locations;

identifying a travel commitment for the preliminary route;

storing the preliminary route as a preferred route;

altering the preferred route to identify a new route;

identifying a travel commitment associated with the new route;

comparing the travel commitment associated with the new route with the travel commitment associated with the preferred route; and

if the travel commitment associated with the new route is less than the travel commitment associated with preferred route, storing the new route as the preferred route.

7. The computer-implemented method of claim 6 wherein the travel commitment includes travel time or a travel distance.

8. The computer-implemented method of claim 6 wherein altering the preferred route to identify the new route includes rearranging the order in which the locations associated with the first and second points of interest are visited in the preferred route.

9. The computer-implemented method of claim 6 wherein altering the preferred route to identify the new route includes selecting a new location associated with at least one of the first or second point of interest, and including the newly selected location and at least one location that appears in the preferred route within the new route.

10. The computer-implemented method of claim 9 wherein including the newly selected location within the new route includes displacing one of the locations associated with either the first or second point of interest within the preferred route with the newly selected location.

11. The computer-implemented method of claim 9 wherein the new location supplements the locations associated with the first and second points of interest within the preferred route.

12. The computer-implemented method of claim 9 wherein selecting the new location includes selecting the new location from the first or the second set of potential locations.

13. The computer-implemented method of claim 6 further comprising:

determining whether a time limitation has been reached; and

displaying the preferred route to the user if it is determined that the time limitation has been reached.

14. The computer-implemented method of claim 13 wherein the time limitation begins to expire from a time the process of selecting the single first potential location corresponding to the received first point of interest and the single second potential location corresponding to the received second point of interest begins and the time limitation expires at a pre-defined expiration time;

thus, enabling the user to identify the advanced route within a reasonable time frame.

15. The computer-implemented method of claim 14 wherein the pre-defined expiration time is defined by the user or a host.

16. The computer-implemented method of claim 6 further comprising displaying the new route to the user if it is determined that the travel commitment of the new route is less than the threshold.

17. The computer-implemented method of claim 1 wherein selecting the single first potential location corresponding to the received first point of interest and the single second potential location corresponding to the received second point of interest further includes:

identifying co-located locations associated with the first and second points of interest within the first and second sets of potential locations;

identifying a route associated with each of the co-located locations, the route configured to travel through the co-located locations;

identifying a travel commitment associated with each identified route; and

comparing the travel commitment of the identified routes to identify an advanced route with a minimized travel commitment.

18. The computer-implemented method of claim 17 wherein identifying co-located locations includes:

searching, within the second set of potential locations, for a location that appears close to each location appearing in the first set of potential locations;

as a result of the search, identifying one or more co-located locations associated with the first and second points of interest.

19. The computer-implemented method of claim 17 wherein co-located locations include location that appear within a pre-defined time or distance from each other.

20. The computer-implemented method of claim 17 wherein the travel commitment includes travel time or a travel distance.