System and method for accelerating route search

• US 10,119,826 B2
• Filed: 05/19/2015
• Issued: 11/06/2018
• Est. Priority Date: 05/19/2015
• Status: Active Grant

• Current Assignee: Verizon Connect Development Limited (Verizon Communications Inc.)
• Original Assignee: Verizon Connect Ireland Limited (Verizon Communications Inc.)
• Inventors: Di Lorenzo, David, Bianconcini, Tommaso, Lori, Alessandro, Mitchell, Peter, Schoen, Fabio
• Primary Examiner(s): Heinle, Courtney D
• Application Number:
  US15/525,228
• Publication Number:
  US 20170336219A1
• Time in Patent Office: 1,267 Days
• 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/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A method for finding an approximation to the all-pairs shortest travel path between a number of predetermined nodes, comprising clustering nodes of an original road network into a plurality of subgroups so that the number of nodes in each subgroup is no greater than a first predetermined threshold and the maximum distance between any two nodes of a subgroup is no greater than a second predetermined threshold; adding information of intra group shortest paths for all pairs in a same subgroup to a newly created higher level road network; adding information of inter group shortest paths for the plurality of subgroups to the same road network; and searching the same road network for the shortest travel path. In those cases in which the path returned is not exact, the path represents one in the original map, even if not necessarily the best one.

Claims

1. A method, comprising:

determining, by a device, whether a quantity of nodes in a set of nodes satisfies a first threshold;

clustering, by the device and based on determining that the quantity of nodes satisfies the first threshold, the set of nodes into a plurality of subgroups so that;

a quantity of nodes in each subgroup is no greater than a second threshold, and

a maximum distance between any two nodes of a same subgroup is no greater than a third threshold,

the second threshold and the third threshold being determined based on a computing capability of the device;

determining, by the device, intra group cost information for the plurality of subgroups,

the intra group cost information being associated with a shortest path among all pairs of nodes that belong to a same subgroup;

determining, by the device, inter group cost information,

the inter group cost information being associated with a shortest path between nodes of two subgroups; and

building, by the device and based on determining the intra group cost information and the inter group cost information, a graph of the set of nodes.

2. The method of claim 1, wherein the maximum distance represents a Euclidean distance.

3. The method of claim 2, wherein clustering the set of nodes comprises:

using coordinates of nodes to calculate the Euclidean distance.

4. The method of claim 1, wherein information of speed profile is not used for clustering the set of nodes.

5. The method of claim 1, further comprising:

identifying border nodes based on a closest Euclidean distance between nodes of two subgroups.

6. The method of claim 1, wherein the intra group cost information and the inter group cost information are calculated by another device.

7. The method of claim 1 further comprising:

creating a reduced graph that includes a predetermined number of nodes selected from the set of nodes.

8. The method of claim 7, wherein a Dijkstra algorithm is used on the reduced graph to find a path between any two nodes of the reduced graph.

9. The method of claim 1, wherein clustering the set of nodes comprises:

clustering the set of nodes periodically.

10. The method of claim 1, wherein clustering the set of nodes is triggered by a set of predetermined events.

11. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions that, when executed by at least one processor, cause the at least one processor to;

determine whether a quantity of nodes in a set of nodes satisfies a first threshold;

cluster, based on determining that the quantity of nodes satisfies the first threshold, the set of nodes into a plurality of subgroups so that;

a quantity of nodes in each subgroup is no greater than a second threshold, and

a maximum distance between any two nodes of a same subgroup is no greater than a third threshold,

the second threshold and the third threshold being determined based on a computing capability of the at least one processor;

determine intra group cost information for the plurality of subgroups,

the intra group cost information being associated with a shortest path among all pairs of nodes that belong to a same subgroup;

determine inter group cost information,

the inter group cost information being associated with a shortest path between nodes of two subgroups; and

build, based on determining the intra group cost information and the inter group cost information, a graph of the set of nodes.

12. The non-transitory computer-readable medium of claim 11, wherein the maximum distance represents a Euclidean distance.

13. The non-transitory computer-readable medium of claim 12, wherein the one or more instructions, that cause the at least one processor to cluster the set of nodes, cause the at least one processor to:

cluster the set of nodes using coordinates of nodes to calculate the Euclidean distance.

14. The non-transitory computer-readable medium of claim 11, wherein information of speed profile is not used for clustering the set of nodes.

15. The non-transitory computer-readable medium of claim 11, wherein the one or more instructions, when executed by the at least one processor, further cause the at least one processor to:

identify border nodes based on a closest Euclidean distance between two subgroups.

16. The non-transitory computer-readable medium of claim 11, wherein the one or more instructions, when executed by the at least one processor, further cause the at least one processor to:

create a reduced graph that includes a predetermined number of nodes selected from the set of nodes.

17. The non-transitory computer-readable medium of claim 11, wherein the one or more instructions, that cause the at least one processor to cluster the set of nodes, cause the at least one processor to:

cluster the set of nodes periodically.

18. A device comprising:

a memory; and

at least one processor communicatively coupled to the memory to;

determine whether a quantity of nodes in a set of nodes satisfies a first threshold;

cluster, based on determining that the quantity of nodes satisfies the first threshold, the set of nodes into a plurality of subgroups so that;

a quantity of nodes in each subgroup is no greater than a second threshold, and

a maximum distance between any two nodes of a same subgroup is no greater than a third threshold,

the second threshold and the third threshold being determined based on a computing capability of the device;

determine intra group cost information for the plurality of subgroups,

the intra group cost information being associated with a shortest path among all pairs of nodes that belong to a same subgroup;

determine inter group cost information,

the inter group cost information being associated with a shortest path between nodes of two subgroups; and

build, based on determining the intra group cost information and the inter group cost information, a graph of the set of nodes.

19. The device of claim 18, wherein the at least one processor, when building the graph of the set of nodes, is to:

build a graph including only a subset of the set of nodes.

20. The device of claim 18, where at least one of the second threshold or the third threshold is determined based on a computing capability of another device.