# US 10,119,826 B2 · System and method for accelerating route search > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,119,826 B2 - Document ID: US10119826B2 - Status: Granted - Kind: B2 - Application number: 15/525,228 - Filed: 2015-05-19 - Published: 2017-11-23 - Granted: 2018-11-06 - Earliest claimed: 2015-05-19 - Assignees: Verizon Connect Ireland Limited - Applicants: Fleetmatics Development Limited - Inventors: David Di Lorenzo; Tommaso Bianconcini; Alessandro Lori; Peter Mitchell; Fabio Schoen - Web page: https://patentgrep.com/patent/US10119826B2 ## CPC - G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes} - G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments} - G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## 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 ### Claim 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the maximum distance represents a Euclidean distance. ### Claim 3 (depends on 2) The method of claim 2, wherein clustering the set of nodes comprises: using coordinates of nodes to calculate the Euclidean distance. ### Claim 4 (depends on 1) The method of claim 1, wherein information of speed profile is not used for clustering the set of nodes. ### Claim 5 (depends on 1) The method of claim 1, further comprising: identifying border nodes based on a closest Euclidean distance between nodes of two subgroups. ### Claim 6 (depends on 1) The method of claim 1, wherein the intra group cost information and the inter group cost information are calculated by another device. ### Claim 7 (depends on 1) The method of claim 1 further comprising: creating a reduced graph that includes a predetermined number of nodes selected from the set of nodes. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 1) The method of claim 1, wherein clustering the set of nodes comprises: clustering the set of nodes periodically. ### Claim 10 (depends on 1) The method of claim 1, wherein clustering the set of nodes is triggered by a set of predetermined events. ### Claim 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. ### Claim 12 (depends on 11) The non-transitory computer-readable medium of claim 11, wherein the maximum distance represents a Euclidean distance. ### Claim 13 (depends on 12) 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. ### Claim 14 (depends on 11) The non-transitory computer-readable medium of claim 11, wherein information of speed profile is not used for clustering the set of nodes. ### Claim 15 (depends on 11) 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. ### Claim 16 (depends on 11) 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. ### Claim 17 (depends on 11) 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. ### Claim 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 18) 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.