CUSTOMIZABLE ROUTE PLANNING
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20)
-
Specification