DETERMINING ALTERNATIVE ROUTES

• US 20110295497A1
• Filed: 05/26/2010
• Published: 12/01/2011
• Est. Priority Date: 05/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Goldberg, Andrew V., Werneck, Renato F., Delling, Daniel, Abraham, Ittai
• Granted Patent: US 8,583,363 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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 an optimal route between the start location and the destination location by a map routing service of the computing device;

determining an alternative route between the start location and the destination location by the map routing service using the optimal route and a plurality of admissibility criteria comprising limited sharing, local optimality, and uniformly bounded stretch; and

outputting the alternative route 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 determining the alternative route between the start location and the destination location comprises determining a plurality of alternative routes that meet the admissibility criteria, generating a ranking of the plurality of alternative routes, and outputting a predetermined number of the alternative routes based on the ranking.

5. 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.

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

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

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

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

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

determining an optimal route between a start location and a destination location by a map routing service of a 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; and

outputting, by the computing device, at least one alternative route based on at least one single via path that is admissible with respect to the admissibility criteria only if there is at least one single via path that is admissible.

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

12. The method of claim 10, 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.

13. The method of claim 12, 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.

14. The method of claim 10, 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.

15. A computer-readable medium comprising computer-readable instructions for determining a route between two locations, said computer-readable instructions comprising instructions that:

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; and

output the highest ranked remaining candidate route that meets a plurality of admissibility criteria, wherein the admissibility criteria comprise limited sharing, local optimality, and stretch.

16. The computer-readable medium of claim 15, further comprising instructions that determine an optimal route between the start location and the destination location, and instructions that output an alternative route based on the highest ranked remaining candidate route that meets the admissibility criteria.

17. The computer-readable medium of claim 16, 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.

18. The computer-readable medium of claim 15, further comprising instructions that, if none of the remaining candidate routes meet the admissibility criteria, relax the admissibility criteria and output the highest ranked remaining candidate route that meets the admissibility criteria after being relaxed.

19. The computer-readable medium of claim 15, wherein the instructions that rank the remaining candidate routes that remain after pruning comprise instructions that sort the remaining candidate routes according to a function based on a via path of each remaining candidate route, and assign a score to each remaining candidate route.

20. The computer-readable medium of claim 19, 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.