Determining alternative routes

• US 8,583,363 B2
• Filed: 05/26/2010
• Issued: 11/12/2013
• Est. Priority Date: 05/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Abraham, Ittai, Delling, Daniel, Goldberg, Andrew V., Werneck, Renato F.
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): Lee, Tyler J
• Application Number:
  US12/787,412
• Publication Number:
  US 20110295497A1
• Time in Patent Office: 1,266 Days
• Field of Search: 701/200, 701/400, 701/533, 701/409, 701/411, 701/416, 701/417, 340/988
• US Class Current: 701/416
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

Alternative routes to an optimal route may be determined and presented to a user via a computing device. Alternative routes are selected from candidate routes that meet admissibility criteria. In an implementation, admissibility of a candidate route (in order for it to be considered an alternative route) may be determined based on three criteria: “limited sharing”, “local optimality”, and “stretch” such as “uniformly bounded stretch”. Limited sharing refers to the amount of difference between the alternative route and the optimal route, local optimality refers to lack of unnecessary detours, and uniformly bounded stretch refers to a length of the shortest path to travel between two points on the alternative route.

Claims

1. A method of determining a route between two locations, comprising:

receiving a start location and a destination location at a computing device;

determining, by the computing device, an optimal route between the start location and the destination location using a map routing service of the computing device;

determining a plurality of alternative routes between the start location and the destination location by the map routing service of the computing device using the optimal route and a plurality of admissibility criteria comprising limited sharing, local optimality, and uniformly bounded stretch, wherein the limited sharing admissibility criteria is that a percentage of edges shared by the alternative route and the optimal route is less than a predetermined percentage;

ranking, by the computing device, the plurality of alternative routes using each of the plurality of admissibility criteria; and

outputting the ranked plurality of alternative routes by the computing device.

2. The method of claim 1, wherein determining the alternative route comprises determining a plurality of candidate routes between the start location and the destination location and determining the admissibility of the candidate routes using the admissibility criteria.

3. The method of claim 2, further comprising pruning the plurality of candidate routes prior to determining the admissibility of the candidate routes, wherein only the admissibility of the pruned candidate routes is determined.

4. The method of claim 2, wherein if none of the candidate routes meet the admissibility criteria, then relaxing the admissibility criteria and determining the admissibility of the candidate routes using the relaxed admissibility criteria.

5. The method of claim 1, wherein limited sharing is based on an amount of a difference between the alternative route and the optimal route.

6. The method of claim 5, wherein local optimality is based on a number of detours on the alternative route.

7. The method of claim 6, wherein uniformly bounded stretch is based on a length of the shortest path between two points on the alternative route.

8. The method of claim 7, wherein the alternative route is at least y% locally optimal and the alternative route has a uniformly bounded stretch of at most z%, where y and z are predetermined threshold values.

9. A method of determining a route between two locations, comprising:

determining, by a computing device, an optimal route between a start location and a destination location using a map routing service of the computing device;

determining a plurality of single via paths between the start location and the destination location by the computing device;

evaluating the single via paths against a plurality of admissibility criteria, by the computing device, wherein the plurality of admissibility criteria includes limited sharing, and the limited sharing criteria is that a percentage of edges shared by an alternative route and the optimal route is less than a predetermined percentage;

outputting, by the computing device, a plurality of alternative routes based on the single via paths of the plurality of single via paths that are admissible with respect to the admissibility criteria, wherein the plurality of alternative routes are ranked by the computing device using each of the plurality of admissibility criteria.

10. The method of claim 9, wherein the admissibility criteria comprise limited sharing, local optimality, and stretch.

11. The method of claim 9, further comprising determining a plurality of candidate routes between the start location and the destination location, wherein determining the single via paths comprises determining via paths of the candidate routes using a plurality of via points.

12. The method of claim 11, further comprising determining the plurality of via points using a pruned bidirectional Dijkstra algorithm, wherein each via point gives a path formed by going from the start location to the via point and from the via point to the destination location along an optimal path.

13. The method of claim 9, wherein each of the single via paths is a concatenation of two shortest paths between the start location and the destination location through a vertex.

14. A system comprising:

a processor configured to;

determine a plurality of candidate routes between a start location and a destination location;

prune the candidate routes to eliminate a portion of the candidate routes;

rank the remaining candidate routes that remain after pruning based on each of a plurality of admissibility criteria; and

output the highest ranked remaining candidate route that meets the plurality of admissibility criteria, wherein the admissibility criteria comprise limited sharing, local optimality, and stretch, wherein the limited sharing admissibility criteria is that a percentage of edges shared by an alternative route and the optimal route is less than a predetermined percentage.

15. The system of claim 14, wherein the processor is further configured to:

determine the optimal route between the start location and the destination location, and output the alternative route based on the highest ranked remaining candidate route that meets the admissibility criteria.

16. The system of claim 15, wherein limited sharing is based on an amount of a difference between the highest ranked remaining candidate route and the optimal route, wherein local optimality is based on an amount of detours on the highest ranked remaining candidate route, and wherein the stretch is uniformly bounded stretch and is based on a length of the shortest path between two points on the highest ranked remaining candidate route.

17. The system of claim 14, wherein, if none of the remaining candidate routes meet the admissibility criteria, the admissibility criteria is relaxed and the highest ranked remaining candidate route that meets the admissibility criteria after being relaxed is provided as an output.

18. The system of claim 14, wherein ranking the remaining candidate routes that remain after pruning comprises sorting the remaining candidate routes according to a function based on a via path of each remaining candidate route, and assigning a score to each remaining candidate route.

19. The system of claim 18, wherein each via path is a single via path that is a concatenation of two shortest paths between the start location and the destination location through a vertex.