System and method for accelerating route search

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.

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.