Point of interest search along a route with return
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.
1. A computer-implemented method for providing routing to a point of interest, the method comprising:
identifying a cost to reach a destination along a navigation route from a current location on the navigation route;
for each point of interest in a first set of points of interest:
identifying a departure point from the navigation route to reach the point of interest,
identifying a cost from the current location on the navigation route to the departure point,
identifying a cost to reach the point of interest from the departure point, and
identifying a cost to the destination from the point of interest;
determining, for each point of interest in the first set of points of interest, a detour cost for the point of interest based, at least in part, on (i) the cost from the current location on the navigation route to the departure point, (ii) the cost to reach the point of interest from the departure point, and (iii) the cost to the destination from the point of interest;
identifying a second set of points of interest from points of interest in the first set of points of interest that have a detour cost less than a maximum detour cost; and
displaying the second set of points of interest in a user interface of a navigation device.
2. The method of claim 1 , wherein identifying the departure part for a point of interest comprises minimizing a combined cost to reach the point of interest from the current location and to reach the point of interest from the departure point.
3. The method of claim 1 , wherein the detour cost is measured in driving time.
4. The method of claim 1 , wherein the detour cost is measured in driving distance.
5. The method of claim 1 , wherein the navigation route is inferred, and the destination is a point along the navigation route.
6. The system of claim 5 , wherein the inferred navigation route is based in part on a prediction score determined by tracked user behavior.
7. The method of claim 1 , wherein the maximum detour cost is selected by the user, the method further comprising
providing a user interface to the user for selecting the maximum detour cost;
receiving, from the user on the user interface, a selection of a maximum detour cost; and
setting the maximum detour cost based on to the selection.
8. The method of claim 7 , wherein the user selection of a maximum detour cost is a relative measurement, and setting the maximum detour cost converts the relative measurement to a numerical value.
9. The method of claim 8 , wherein the relative measurement is urgency.
10. The method of claim 1 , wherein determining the detour cost for the point of interest comprises combining the cost from the current location on the navigation route to the departure point, the cost to reach the point of interest from the departure point, and the cost to the destination from the point of interest, and subtracting the cost to reach the destination along the navigation route from the current location.
11. A system for providing routing to a point of interest, comprising:
a database storing point of interest data;
a global navigation satellite system radio, adapted to determine a current location of the global navigation system;
a routing engine, coupled to the global navigation satellite system radio and the database, adapted to:
identify a cost to reach a destination along a navigation route from a current location on the navigation route;
for each point of interest in a first set of points of interest from the database storing points of interest data:
identify a departure point from the navigation route to reach the point of interest,
identify a cost from the current location on the navigation route to the departure point,
identify a cost to reach the point of interest from the departure point, and
identify a cost to the destination from the point of interest;
determine, for each point of interest in the first set of points of interest, a detour cost for the point of interest based, at least in part, on (i) the cost from the current location on the navigation route to the departure point, (ii) the cost to reach the point of interest from the departure point, and (iii) the cost to the destination from the point of interest;
identify a second set of points of interest from points of interest in the first set of points of interest that have a detour cost less than a maximum detour cost; and
a user interface module, coupled to the routing engine, adapted to display one or more indicia of the distance to the second set of points of interest.
12. The system of claim 11 , wherein identifying the departure part for a point of interest comprises minimizing a combined cost to reach the point of interest from the current location and to reach the point of interest from the departure point.
13. The system of claim 11 , wherein the detour cost is measured in driving time.
14. The system of claim 11 , wherein the detour cost is measured in driving distance.
15. The system of claim 11 , wherein the navigation route is inferred, and the destination is a point along the navigation route.
16. The system of claim 15 , wherein the inferred navigation route is based in part on a prediction score determined by tracked user behavior.
17. The system of claim 10 , wherein the maximum detour cost is selected by the user, wherein the user interface module is further configured to provide a user interface element for selecting the maximum detour cost, receive a selection from the user of the maximum detour cost, and set the maximum detour cost based on the selection.
18. The system of claim 17 , wherein the user selection of a maximum detour cost is a relative measurement, and setting the maximum detour cost converts the relative measurement to a numerical value.
19. The system of claim 18 , wherein the relative measurement is urgency.
20. The system of claim 11 , wherein determining the detour cost for the point of interest comprises combining the cost from the current location on the navigation route to the departure point, the cost to reach the point of interest from the departure point, and the cost to the destination from the point of interest, and subtracting the cost to reach the destination along the navigation route from the current location.