Automated route determination to avoid a particular maneuver
View Patent ↗A preferred route may be determined from an origin location to a destination location. The preferred route avoids a particular maneuver or particular maneuvers identified by a user. The determination is made by processing directed links (e.g., one-way edges) in a graph that includes one or more links and two or more nodes. The determination of a preferred route may include an estimate of the time required at one or more intersections along alternative routes and/or an estimate of the time required to travel the alternative routes based on the day of the week or the day of the year in which travel occurs. Individual routing preferences, such as a preference of a rural over an urban route and avoiding particular maneuvers in a route, also may be considered.
1. A computer implemented method for determining a route, the method comprising:
receiving a request for a first route between a first origin and a first destination from a user;
determining first route maneuvers associated with the first route;
communicating the first route maneuvers to the user;
receiving a user selection of one of the first route maneuvers as an avoided maneuver;
storing the avoided maneuver in a list of maneuvers to be avoided;
receiving, after the storage of the avoided maneuver, a request for a second route between a second origin and a second destination from the user;
accessing, in response to the received request for the second route, the list of maneuvers to be avoided; and
determining second route maneuvers based upon accessing the list, the second route maneuvers not including the avoided maneuver.
2. The method of claim 1 further comprising using an in-vehicle navigation system to present a maneuver included in the second route.
3. The method of claim 1 further comprising presenting the second route on a user system.
4. The method of claim 1 further comprising communicating the second route to a user system.
5. The method of claim 4 wherein communicating the second route to a user system comprises communicating the second route over a connection that is established using the Internet Protocol.
6. The method of claim 1 wherein storing the avoided maneuver in a list of maneuvers to be avoided includes storing the avoided maneuver as associated with the user.
7. The method of claim 1 wherein receiving a request for a first route and a request for a second route each include receiving a request for a route from the user.
8. The method of claim 1 wherein the received request for a second route is for a route that is not associated with a route previously requested, before the receipt of the user selection of one of the first route maneuvers.
9. The method of claim 1 wherein storing the avoided maneuver in a list of maneuvers to be avoided includes storing the avoided maneuver in a list of maneuvers to be avoided for later use in other routes.
10. The method of claim 1 wherein storing the avoided maneuver in a list of maneuvers to be avoided includes associating a substantial cost with the avoided maneuver.
11. The method of claim 1 wherein storing the avoided maneuver in a list of maneuvers to be avoided includes storing an avoid indicator in a directed link data structure associated with the avoided maneuver.
12. The method of claim 1 wherein storing the avoided maneuver in a list of maneuvers to be avoided includes storing the avoided maneuver such that the avoided maneuver is unusable or storing the avoided maneuver such that the likelihood of the maneuver being used in the route is reduced.
13. The method of claim 12 wherein storing the avoided maneuver in a list of maneuvers to be avoided includes storing the avoided maneuvers such that the maneuver is unusable.
14. The method of claim 12 wherein storing the avoided maneuver in a list of maneuvers to be avoided includes storing the avoided maneuver such that the likelihood of the maneuver being used in the route is reduced.
15. A computer implemented method for determining a route, the method comprising:
receiving a request for a first route between a first origin and a first destination from a user;
determining first route maneuvers associated with the first route;
communicating the first route maneuvers to the user;
receiving a user selection of one of the first route maneuvers as an avoided maneuver;
storing the avoided maneuver in a list of maneuvers to be avoided;
processing one or more maneuvers available for inclusion in the route, for each maneuver, the processing including:
determining that the maneuver may be included in the route, and
determining a cost associated with the maneuver;
processing the avoided maneuver, the processing including:
determining that the avoided maneuver is included in the list of maneuvers to be avoided, and
associating, based on the list, a different cost with the avoided maneuver, and
selecting some of the processed maneuvers for inclusion in a second route, the selection being based at least in part on the cost of the maneuvers.
16. An apparatus for determining a route, the apparatus being configured to:
receive a request for a first route between a first origin and a first destination from a user;
determine first route maneuvers associated with the first route;
communicate the first route maneuvers to the user;
receive a user selection of one of the first route maneuvers as an avoided maneuver;
store the avoided maneuver in a list of maneuvers to be avoided;
receive, after the storage of the avoided maneuver, a request for a second route between a second origin and a second destination from the user;
access, in response to the received request for the second route, the list of maneuvers to be avoid; and
determine second route maneuvers based upon accessing the list, the second route maneuvers not including the avoided maneuver.
17. The apparatus of claim 16 wherein the apparatus comprises an in-vehicle navigation system to present a maneuver included in the second route.
18. The apparatus of claim 16 further configured to present the second route on a user system.
19. The apparatus of claim 16 further configured to communicate the second route to a user system.
20. The apparatus of claim 16 further configured to communicate the second route over a connection that is established using the Internet Protocol.
21. The apparatus of claim 16 further configured to receive the user selection of one of the first route maneuvers as an avoided maneuver.
22. The method of claim 15 wherein selecting some of the processed maneuvers for inclusion in a second route includes processing the determined or associated costs to determine which selection of maneuvers minimize the total or average cost.
23. The method of claim 15 wherein associating a different cost with the avoided maneuver includes associated a numerical value with the maneuver that is large enough to prevent the avoided maneuver from being included in the second route.
24. The method of claim 15 wherein associating a different cost with the avoided maneuver includes associating the avoided maneuver with a bypass indication.