Identifying a route configured to travel through multiple points of interest

• US 7,920,965 B1
• Filed: 12/29/2006
• Issued: 04/05/2011
• Est. Priority Date: 05/05/2006
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: MapQuest, Inc. (Apollo Global Management, Inc.)
• Inventors: Nesbitt, David W., Renner, W. Karl
• Primary Examiner(s): Tran; Dalena
• Application Number:
  US11/617,874
• Time in Patent Office: 1,558 Days
• Field of Search: 701/209, 701/200, 701/211, 701/201, 340/988, 340/995.19, 34099524-99528
• US Class Current: 701/209
• 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 origin and destination locations, the perimeter limiting a number of potential locations corresponding to the first point of interest and the second point of interest;

using the identified perimeter as a basis for identifying a first set of potential locations that corresponds to the 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 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 first point of interest and a single second potential location corresponding to the 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 first point of interest and the selected single second potential location corresponding to the 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 origin and destination locations comprises:

determining a distance between the origin and destination locations;

multiplying the determined distance by a first factor to compute a distance of a perimeter'"'"'s major axis; and

multiplying the distance of the perimeter'"'"'s major axis by a factor to compute a distance of a perimeter'"'"'s minor axis.

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 points of interest does not include the at least one location within the perimeter.

5. The computer-implemented method of claim 1 wherein identifying the perimeter that surrounds the 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 first point of interest and the single second potential location corresponding to the second point of interest further includes:

identifying a preliminary route as a 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 a 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 points 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 first point of interest and the single second potential location corresponding to the second point of interest begins and the time limitation expires at a pre-defined expiration time.

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 a predetermined threshold.

17. The computer-implemented method of claim 1 wherein selecting the single first potential location corresponding to the first point of interest and the single second potential location corresponding to the 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 searching, 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 locations 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 a travel time or a travel distance.

21. The computer-implemented method of claim 1 wherein receiving the query includes receiving multiple keywords, each identifying one of the origin location, the destination location, and at least the first point of interest and the second point of interest.

22. The computer-implemented method of claim 21 wherein receiving the multiple keywords includes receiving the multiple keywords concurrently.

23. The computer-implemented method of claim 21 wherein receiving the multiple keywords includes receiving each one of the multiple keywords at a different time.

24. The computer-implemented method of claim 1 wherein the origin location, the destination location, and the first point of interest and the second point of interest forming the query are each received from a different source.

25. 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;

determining a preliminary route from the origin location to the destination location;

determining a perimeter that surrounds the origin and destination locations, the perimeter limiting a number of potential destinations corresponding to the first point of interest and the second point of interest;

identifying a first set of potential destinations that corresponds to the first point of interest and that represents less than all potential destinations corresponding to the first point of interest, the potential destinations within the first set being identified based on a relatedness of the potential destinations to the first point of interest and also based on the potential destinations being located within the perimeter;

identifying a second set of potential destinations that corresponds to the second point of interest and that represents less than all potential destinations corresponding to the second point of interest, the potential destinations within the second set being identified based on a relatedness of the potential destinations to the second point of interest and also based on the potential destinations being located within the perimeter;

among the first and second sets of potential destinations identified, respectively selecting a single first potential destination corresponding to the first point of interest and a single second potential destination corresponding to the second point of interest; and

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

26. The computer-implemented method of claim 25 wherein identifying the first and the second sets of potential destinations is further based on a geographic proximity of the potential destinations to the preliminary route.

27. The computer-implemented method of claim 26 wherein identifying the first and the second sets of potential destinations based on the geographic proximity of the potential destinations to the preliminary route includes identifying the first and the second sets of potential destinations based on estimated time of travel from the preliminary route to the potential destinations.

28. The computer-implemented method of claim 25 wherein identifying the first set of potential destinations includes identifying the first set of potential destinations representing at least multiple locations for the first point of interest.

29. The computer-implemented method of claim 25 wherein selecting the single first and second potential locations further includes:

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

identifying a travel commitment associated with the preliminary route;

storing the preliminary route as a preferred route;

altering the preferred route to identify a new route;

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

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

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

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

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

33. The computer-implemented method of claim 32 wherein including the newly selected destination within the new route includes displacing one of the destinations associated with either the first or second point of interest within the preferred route with the newly selected destination.

34. The computer-implemented method of claim 32 wherein the new destination supplements the destinations associated with the first and second points of interest within the preferred route.

35. The method of claim 25 wherein identifying the perimeter that surrounds the origin and destination locations comprises:

determining a distance between the origin and destination locations;

multiplying the determined distance by a first factor to compute a distance of a perimeter'"'"'s major axis; and

multiplying the distance of the perimeter'"'"'s major axis by a factor to compute a distance of a perimeter'"'"'s minor axis.

36. The method of claim 35 wherein the perimeter has an elliptical shape.

37. The method of claim 35 further comprising:

determining that at least one of the first and second points of interest does not include a location within the first perimeter;

identifying a second perimeter formed around and outside of the first perimeter; and

identifying a set of locations for the at least one of the first and second points of interest that is within the second perimeter.

38. 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;

identifying a perimeter that surrounds the origin and destination locations;

identifying a first location associated with the first point of interest and a second location associated with the second point of interest, wherein the first location and the second location are located within the perimeter;

displaying, as a first advanced route, a route from the origin location to the destination location that travels through the identified first location and the identified second location;

identifying a different first location associated with the first point of interest and a different second location associated with the second point of interest, wherein the different first location and the different second location are located within the perimeter;

displaying, as a second advanced route, a route from the origin location to the destination location that travels through the identified different first location and the identified different second location; and

enabling a user to select from among the first and second advanced routes.

39. The computer-implemented method of claim 38 wherein the first advanced route and the second advanced route are displayed concurrently.

40. The computer-implemented method of claim 38 wherein identifying the first location and the second location further includes:

determining a preliminary route from the origin location to the destination location;

identifying a first set of potential locations that corresponds to the first point of interest and that represents less than all potential locations corresponding to the first point of interest, the potential locations within the first set being identified based on a relatedness of the potential locations to the first point of interest and also based on a geographic proximity of the potential locations to the determined preliminary route;

identifying a second set of potential locations that corresponds to the second point of interest and that represents less than all potential locations corresponding to the second point of interest, the potential locations within the second set being identified based on a relatedness of the potential locations to the second point of interest and also based on a geographic proximity of the potential locations to the determined preliminary route; and

among the first and second sets of potential destinations identified, respectively selecting the first location and the second location.

41. The computer-implemented method of claim 40 wherein identifying the first different location and the second different location further includes selecting from among the first and second sets of potential destinations identified, respectively the first different location and the second different location.

42. The computer-implemented method of claim 38 wherein locations associated with the first and second points of interest include geographic locations or addresses.

43. The computer-implemented method of claim 38 wherein locations associated with the first and second points of interest include facility names of the first and second points of interest.

44. The computer-implemented method of claim 38 wherein the first and second points of interest include first and second establishments, respectively, wherein the first and second establishments each include one or more locations associated therewith.

45. The computer-implemented method of claim 44 wherein the first and second points of interest include first and second facility names, respectively.

46. The computer-implemented method of claim 44 wherein the first and second points of interest include first and second desired products or services, respectively, in which the user is interested.

47. The computer-implemented method of claim 46 wherein the first and second desired products or services include products or services associated with a particular activity.

48. The computer-implemented method of claim 44 wherein the first and second establishments are each associated with a particular location.

49. The computer-implemented method of claim 48 wherein the particular location includes a geographical location.

50. The computer-implemented method of claim 48 wherein the particular location associated with the first establishment includes a particular geographical location and the particular location associated with the second establishment includes a particular facility name.

51. The computer-implemented method of claim 38 further comprising:

identifying that the first advanced route is selected by the user;

in response to the user selecting the first advanced route, providing the user with point-to-point directions/maps for the first advanced route, wherein the point-to-point directions/maps begins at the origin location, passes through the first and second locations associated with the first and second points of interest, respectively, and ends at the destination location.

52. The computer-implemented method of claim 38 wherein the origin location and the destination location each include a geographical location.

53. The computer-implemented method of claim 38 wherein the origin location includes a geographical location and the destination location includes a facility name.