Point of interest search along a route with return

• US 9,791,284 B2
• Filed: 10/06/2016
• Issued: 10/17/2017
• Est. Priority Date: 04/01/2009
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Poppen, Richard F., Tang, Weidong
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US15/286,562
• Publication Number:
  US 20170023374A1
• Time in Patent Office: 376 Days
• Field of Search: None
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3605 Destination input or retrieval
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G01S 19/42 Determining position

Abstract

A routing module identifies POIs that can be reached from a route with a cost less than distance m. A routing engine performs a reverse exploration on nodes in the planned route to locate POIs from which the route can be reached with a cost of less than a second cost n. POIs identified as being reachable from the route with a cost of less than m, and from which the route is reachable with a cost less than n are then further filtered to identify a subset of the POIs for which the sum of the time or distance from the route to the POI and the time or distance from the POI back to the route is less than a threshold time or distance, t.

Claims

1. A computer-implemented method for providing routing to a point of interest, the method comprising:

identifying a navigation route from a current location to a destination;

determining a first detour route including a first route from the current location to a first departure point, a second route from the first departure point to a first point of interest, and a third route from the first point of interest to the destination;

determining a second detour route including a fourth route from the current location to a second departure point, a fifth route from the second departure point to a second point of interest, and a sixth route from the second point of interest to the destination;

determining, for each of the detour routes, a cost to reach the destination along the corresponding detour route, each of the costs determined based on (i) a duration of time required to travel along at least a portion of the corresponding detour route and (ii) a distance of the portion of the corresponding detour route; and

in response to determining that the cost for the second detour route is greater than the cost for the first detour route, providing the first detour route for presentation on a navigation device of a user.

2. The method of claim 1, wherein determining each of the costs is further determined based on a type of the destination.

3. The method of claim 1, wherein determining each of the costs is further determined based on a monetary cost associated with the corresponding detour route.

4. The method of claim 3, wherein the monetary cost is for a toll road of the corresponding detour route.

5. The method of claim 1, wherein, for the first detour route and the second detour route, the portion of the corresponding detour route does not include the first route and the fourth route, respectively.

6. The method of claim 1, further comprising:

determining the navigation route based on a plurality of navigation routes previously traveled by the user.

7. The method of claim 6, wherein determining the navigation route further comprises:

identifying a candidate navigation route of the plurality of navigation routes, the candidate navigation route having a candidate destination;

determining a first distance from a first location of the navigation device at a first time to the candidate destination;

determining a second distance from a second location of the navigation device at a second time to the candidate destination, the second time being subsequent to the first time; and

identifying the candidate navigation route as the navigation route in response to determining that the second distance is less than the first distance.

8. A non-transitory computer-readable storage medium storing instructions for providing routing to a point of interest, the instructions when executed by one or more processors cause the one or more processors to perform steps including:

identifying a navigation route from a current location to a destination;

determining a first detour route including a first route from the current location to a first departure point, a second route from the first departure point to a first point of interest, and a third route from the first point of interest to the destination;

determining a second detour route including a fourth route from the current location to a second departure point, a fifth route from the second departure point to a second point of interest, and a sixth route from the second point of interest to the destination;

determining, for each of the detour routes, a cost to reach the destination along the corresponding detour route, each of the costs determined based on (i) a duration of time required to travel along at least a portion of the corresponding detour route and (ii) a distance of the portion of the corresponding detour route; and

in response to determining that the cost for the second detour route is greater than the cost for the first detour route, providing the first detour route for presentation on a navigation device of a user.

9. The non-transitory computer-readable storage medium of claim 8, wherein determining each of the costs is further determined based on a type of the destination.

10. The non-transitory computer-readable storage medium of claim 8, wherein determining each of the costs is further determined based on a monetary cost associated with the corresponding detour route.

11. The non-transitory computer-readable storage medium of claim 10, wherein the monetary cost is for a toll road of the corresponding detour route.

12. The non-transitory computer-readable storage medium of claim 8, wherein, for the first detour route and the second detour route, the portion of the corresponding detour route does not include the first route and the fourth route, respectively.

13. The non-transitory computer-readable storage medium of claim 8, having further instructions that when executed by the one or more processors cause the one or more processors to perform further steps including:

determining the navigation route based on a plurality of navigation routes previously traveled by the user.

14. The non-transitory computer-readable storage medium of claim 13, wherein determining the navigation route further comprises:

identifying a candidate navigation route of the plurality of navigation routes, the candidate navigation route having a candidate destination;

determining a first distance from a first location of the navigation device at a first time to the candidate destination;

determining a second distance from a second location of the navigation device at a second time to the candidate destination, the second time being subsequent to the first time; and

identifying the candidate navigation route as the navigation route in response to determining that the second distance is less than the first distance.

15. A system for providing routing to a point of interest, comprising:

a global navigation satellite system radio configured to determine a current location of the system;

a routing engine coupled to the global navigation satellite system radio and configured to;

identify a navigation route from the current location to a destination;

determine a first detour route including a first route from the current location to a first departure point, a second route from the first departure point to a first point of interest, and a third route from the first point of interest to the destination;

determine a second detour route including a fourth route from the current location to a second departure point, a fifth route from the second departure point to a second point of interest, and a sixth route from the second point of interest to the destination;

determine, for each of the detour routes, a cost to reach the destination along the corresponding detour route, each of the costs determined based on (i) a duration of time required to travel along at least a portion of the corresponding detour route and (ii) a distance of the portion of the corresponding detour route;

determine that the cost for the second detour route is greater than the cost for the first detour route; and

a user interface coupled to the routing engine and configured to present the first detour route to a user of the system in response to the determination that the cost for the second detour route is greater than the cost for the first detour route.

16. The system of claim 15, wherein determining each of the costs is further determined based on a type of the destination.

17. The system of claim 15, wherein determining each of the costs is further determined based on a monetary cost associated with the corresponding detour route.

18. The system of claim 17, wherein the monetary cost is for a toll road of the corresponding detour route.

19. The system of claim 15, wherein the routing engine is further configured to:

determine the navigation route based on a plurality of navigation routes previously traveled by the user.

20. The system of claim 19, wherein determining the navigation route further comprises:

identify a candidate navigation route of the plurality of navigation routes, the candidate navigation route having a candidate destination;

determine a first distance from a first location of the navigation device at a first time to the candidate destination;

determine a second distance from a second location of the navigation device at a second time to the candidate destination, the second time being subsequent to the first time; and

identify the candidate navigation route as the navigation route in response to determining that the second distance is less than the first distance.