CUSTOMIZABLE ROUTE PLANNING

• US 20130231862A1
• Filed: 04/23/2013
• Published: 09/05/2013
• Est. Priority Date: 06/03/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Delling, Daniel, Werneck, Renato F.
• Application Number:
  US13/868,135
• Publication Number:
  US 20130231862A1
• Time in Patent Office: Days
• US Class Current: 701/527
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

Customizable route planning is a technique for computing point-to-point shortest paths in road networks. It includes three phases: preprocessing, customization, and queries. The preprocessing phase partitions a graph into multiple levels of loosely connected components of bounded size and creates an overlay graph for each level by replacing each component with a clique connecting its boundary vertices. Clique edge lengths are computed during the customization phase. The query phase comprises a bidirectional Dijkstra'"'"'s algorithm operating on the union of the overlay graphs and the components of the original graph containing the origin and the destination. The customization may be made even faster, enabling a wide range of applications including highly dynamic applications and on-line personalized cost functions. In an implementation, to compute overlay arc costs, Dijkstra'"'"'s algorithm may be supplemented or replaced by other techniques, such as contraction and the Bellman-Ford algorithm.

Claims

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

receiving as input, at a computing device, a graph comprising a plurality of vertices and edges;

partitioning the graph into a plurality of components of bounded size;

generating an overlay graph by replacing each of the plurality of components with a clique connecting boundary vertices of the component;

for each of the plurality of cliques, determining the weight of each of the edges of the clique by performing contraction within the corresponding cell of the partitioned graph;

performing, by the computing device, a point-to-point shortest path computation for a query using the partitioned graph, the overlay graph, and the weights of each of the edges of the cliques; and

outputting the shortest path, by the computing device.

2. The method of claim 1, wherein performing the contraction comprises temporarily removing some of the vertices of the partitioned graph and adding additional edges to the partitioned graph.

3. The method of claim 1, wherein performing the contraction comprises removing a vertex v from the graph, and adding new arcs to preserve shortest paths of the graph.

4. The method of claim 3, wherein performing the contraction further comprises for each incoming arc (u,v) and outgoing arc (v,w), creating a shortcut arc (u,w) with l(u,w)=l(u,v)+l(v,w), and temporarily adding the shortcut to the partitioned graph to represent a path between u and w.

5. The method of claim 1, further comprising determining a contraction order prior to performing the contraction, and performing the contraction in the contraction order.

6. The method of claim 5, wherein the contraction order minimizes the number of operations performed during contraction.

7. The method of claim 5, wherein partitioning the graph, generating the overlay graph, and determining the contraction order are performed during a metric-independent preprocessing stage, wherein the contraction is performed during a metric customization stage, wherein the weights of each of the edges of the cliques are determined during the metric customization stage.

8. The method of claim 1, further comprising storing microcode for use in the contraction, wherein the microcode stores a list of memory positions that are read from and written to during contraction.

9. The method of claim 8, wherein the partitioned graph, the topology of the overlay graph, a contraction order, and the microcode are metric-independent.

10. The method of claim 1, wherein the graph represents a network of nodes.

11. The method of claim 1, wherein the graph represents a road map.

12. A method of determining a shortest path between two locations, comprising:

preprocessing, at a computing device, a graph comprising a plurality of vertices to generate preprocessed data comprising a partitioned graph, a contraction order, and microcode representing the instructions to be performed during contraction; and

performing metric customization on a metric using the partitioned graph,the contraction order, and the microcode, by the computing device.

13. The method of claim 12, wherein performing metric customization on the metric using the partitioned graph comprises performing a contraction the partitioned graph, in the contraction order, to determine the lengths of clique edges in an overlay graph.

14. The method of claim 13, wherein the contraction order minimizes the number of operations performed during the contraction.

15. The method of claim 13, further comprising, during the preprocessing, storing microcode for use in the contraction, wherein the microcode stores a list of memory positions that are read from and written to during contraction.

16. The method of claim 12, wherein the preprocessing is metric-independent, and further comprising:

creating an overlay graph by replacing each component with a clique connecting the boundary vertices of the component;

determining a length of an edge of the clique during the metric customization;

receiving a query at the computing device, the query comprising an origin location and a destination location;

performing, by the computing device, a point-to-point shortest path computation on the origin location and the destination location, wherein the point-to-point shortest path computation uses the partitioned graph, the overlay graph, and the length of the edge of the clique; and

outputting the shortest path, by the computing device.

17. A method of determining a shortest path between two locations, comprising:

receiving as input, at a computing device, a plurality of overlay graphs generated from a partitioned graph;

receiving as input, at the computing device, metric customization data for a metric representing the weights of clique edges of a clique for each cell, wherein the weights of the clique edges are based on contraction performed on the partitioned graph in a predetermined contraction order; and

performing, by the computing device, a point-to-point shortest path computation on a query using the partitioned graph and the weight of clique edges of the clique.

18. The method of claim 17, wherein the metric customization data is generated using at least one mezzanine level.

19. The method of claim 17, wherein the weights of the clique edges are determined using a Bellman-Ford algorithm.

20. The method of claim 17, wherein contraction is performed by executing predetermined microcode optimized to improve locality.