Automated route determination to avoid a particular maneuver

• US 7,356,405 B1
• Filed: 05/25/2005
• Issued: 04/08/2008
• Est. Priority Date: 08/29/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: AOL LLC (Apollo Global Management, Inc.)
• Inventors: Nesbit, David W.
• Primary Examiner(s): NGUYEN, CUONG H
• Application Number:
  US11/136,377
• Time in Patent Office: 1,049 Days
• Field of Search: 701201-202, 701207-211, 340/994, 340/995.19, 340991-992
• US Class Current: 701/202
• 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/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

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.

Claims

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.

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.

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.