Identifying a route configured to travel through multiple points of interest

• US 8,467,959 B2
• Filed: 03/01/2011
• Issued: 06/18/2013
• Est. Priority Date: 05/05/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/037,602
• Publication Number:
  US 20120059584A1
• Time in Patent Office: 840 Days
• Field of Search: 701/400, 701408-411, 701/425, 701/426, 701/438, 340/990, 340/995.17, 340/995.21, 340/995.23, 340/995.24, 340/988
• US Class Current: 701/410
• 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 comprising:

identifying, using at least one processor, a preliminary travel route between a first location and a second location, wherein the preliminary travel route travels through a plurality of intermediate locations;

determining a first travel commitment associated with the preliminary travel route;

rearranging, using the at least one processor, an order of the plurality of intermediate locations to form a modified travel route;

determining a second travel commitment associated with the modified travel route;

determining if the second travel commitment is less than the first travel commitment; and

selecting the modified travel route when it is determined that the second travel commitment is less than the first travel commitment.

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

determining if the second travel commitment is less than a threshold commitment level; and

selecting the modified travel route when it is determined that the second travel commitment is less than the threshold commitment level.

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

determining if the second travel commitment exceeds a threshold commitment level;

rearranging, when it is determined that the second travel commitment exceeds the threshold commitment level, the plurality of intermediate locations to form a different modified travel route;

determining a third travel commitment associated with the different modified travel route;

determining if the third travel commitment is less than the threshold commitment level; and

selecting the different modified travel route when it is determined that the third travel commitment is less than the threshold commitment level.

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

repeatedly determining modified travel routes and associated travel commitments until a travel commitment associated with a modified travel route is below a threshold commitment level; and

selecting the modified travel route for which the associated travel commitment is below the threshold commitment level.

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

repeatedly determining modified travel routes;

determining travel commitments associated with the modified travel routes;

determining if a predetermined period of time has expired;

ending the repeated determining of modified travel routes when it is determined that the predetermined period of time has expired; and

selecting the modified travel route with the lowest determined travel commitment.

6. The computer-implemented method of claim 5, wherein none of the determined travel commitments is lower than a threshold commitment level.

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

repeatedly determining modified travel routes;

determining travel commitments associated with the modified travel routes;

determining the relative improvement in travel commitment associated with the modified travel routes;

determining if the relative improvement in travel commitments is marginal;

ending the repeated determining of modified travel routes when it is determined that the relative improvement in travel commitments is marginal; and

selecting the modified travel route associated with the lowest determined travel commitment.

8. The computer-implemented method of claim 1, wherein rearranging an order of the plurality of intermediate locations comprises randomly rearranging the plurality of intermediate locations.

9. The computer-implemented method of claim 1, wherein the first travel commitment and the second travel commitment are expressed in units of time.

10. The computer-implemented method of claim 1, wherein the first travel commitment and the second travel commitment are expressed in units of distance.

11. The computer-implemented method of claim 1, wherein the plurality of intermediate locations are user identified.

12. The computer-implemented method of claim 11, wherein the plurality of intermediate locations comprise a first location of a first category and a second location of a second category.

13. The computer-implemented method of claim 12, wherein the first category comprises one of banks, restaurants, gas stations, or stores.

14. The computer-implemented method of claim 12, wherein rearranging the order of the plurality of intermediate locations comprises selecting a third location of the first category, and replacing the first location with the third location.

15. A computer-based system comprising one or more processors and a non-transitory storage medium storing a plurality of instructions, the plurality of instructions being executable by at least one processor for:

identifying a preliminary travel route between a first location and a second location, wherein the preliminary travel route travels through a plurality of intermediate locations;

determining a first travel commitment associated with the preliminary travel route;

rearranging an order of the plurality of intermediate locations to form a modified travel route;

determining a second travel commitment associated with the modified travel route;

determining if the second travel commitment is less than the first travel commitment; and

selecting the modified travel route when it is determined that the second travel commitment is less than the first travel commitment.

16. The computer-based system of claim 15, further comprising:

determining if the second travel commitment is less than a threshold commitment level; and

selecting the modified travel route when it is determined that the second travel commitment is less than the threshold commitment level.

17. The computer-based system of claim 15, further comprising instructions for:

determining if the second travel commitment exceeds a threshold commitment level;

rearranging, when it is determined that the second travel commitment exceeds the threshold commitment level, the plurality of intermediate locations to form a different modified travel route;

determining a third travel commitment associated with the different modified travel route;

determining if the third travel commitment is less than the threshold commitment level; and

selecting the different modified travel route when it is determined that the third travel commitment is less than the threshold commitment level.

18. The computer-based system of claim 15, further comprising instructions for:

repeatedly determining modified travel routes and associated travel commitments until a travel commitment associated with a modified travel route is below a threshold commitment level; and

selecting the modified travel route for which the associated travel commitment is below the threshold commitment level.

19. The computer-based system of claim 15, further comprising instructions for:

repeatedly determining modified travel routes;

determining travel commitments associated with the modified travel routes;

determining if a predetermined period of time has expired;

ending the repeated determining of modified travel routes when it is determined that the predetermined period of time has expired; and

selecting the modified travel route with the lowest determined travel commitment.

20. The computer-based system of claim 19, wherein none of the determined travel commitments is lower than a threshold commitment level.

21. The computer-based system of claim 15, further comprising instructions for:

repeatedly determining modified travel routes;

determining travel commitments associated with the modified travel routes;

determining the relative improvement in travel commitment associated with the modified travel routes;

determining if the relative improvement in travel commitments is marginal;

ending the repeated determining of modified travel routes when it is determined that the relative improvement in travel commitments is marginal; and

selecting the modified travel route associated with the lowest determined travel commitment.

22. The computer-based system of claim 15, wherein rearranging the order of the plurality of intermediate locations comprises randomly rearranging the plurality of intermediate locations.

23. The computer-based system of claim 15, wherein the first travel commitment and the second travel commitment are expressed in units of time.

24. The computer-based system of claim 15, wherein the first travel commitment and the second travel commitment are expressed in units of distance.

25. The computer-based system of claim 15, wherein the plurality of intermediate locations are user identified.

26. The computer-based system of claim 25, wherein the plurality of intermediate locations comprise a first location of a first category and a second location of a second category.

27. The computer-based system of claim 26, wherein the first category comprises one of banks, restaurants, gas stations, or stores.

28. The computer-based system of claim 26, wherein rearranging the order of the plurality of intermediate locations comprises selecting a third location of the first category, and replacing the first location with the third location.