Systems and methods for determining a shortest path between nodes

1 . A method comprising:

receive, using one or more processors, input data including information about locations within a road network and conditions associated with the road network, the conditions including at least: one or more distances between the locations and one of more times to traverse between the locations;

pre-processing, using the one or more processors and based on a multi-level overlay (MLO) algorithm, the input data to form a stable shortest path graph including the locations within the road network, wherein the locations are categorized into a hierarchy of cells and levels, and wherein a number of boundary arcs between cells is minimized by optimizing partitioning parameters;

determining, using one or more processors and based on the MLO data structure, one or more hub labels associated with the locations included within a shortest path graph;

modifying, using the one or more processors, an order of hub identifiers associated with the one or more hubs labels into a sequential order by assigning consecutive identifiers to boundary arcs from a same cell in the hierarchy to improve memory access patterns during query processing;

storing, in memory, the hub identifiers as intervals representing contiguous ranges of values instead of as individual listings to reduce memory requirements and enable faster query processing;

receiving, using the one or more processors, a delivery route query including an indication of a first location and a second location of the locations, wherein the first location is a starting location of a delivery route, and the second location is a destination location of the delivery route; and

determining, using the one or more processors, based on the MLO data structure, and using the one or more hub labels, a shortest path between the first location and the second location by performing label intersection using interval-based operations on the ranges of hub identifier values to reduce computational resource usage, wherein the shortest path is a delivery route between the starting location and the destination location;

sending, using the one or more processors, the delivery route to a delivery vehicle or a device associated with a delivery driver of the delivery vehicle; and

autonomously navigating a delivery vehicle along the delivery route.

2 . The method of claim 1 , further comprising:

performing a forward search of the shortest path graph from the first location;

performing a backward search of the shortest path graph from the second location; and

determining, based on the forward search and the backward search, a first cell within the shortest path graph in which the forward search and backward search intersect.

3 . The method of claim 2 , wherein determining the shortest path between the first location and the second location further comprises performing a search within the first cell and a first level associated with the first cell instead of a second cell and a second level associated with the second cell.

4 . A method comprising:

determining, using one or more processors and based on a multi-level overlay (MLO) data structure, one or more hub labels associated with one or more nodes included within a shortest path graph;

receiving, using the one or more processors, an indication of a first node and a second node of the one or more nodes;

generating canonical labels using asymmetric pruning, wherein the asymmetric pruning reduces a number of the one or more hub labels by including only boundary arcs of cells including a terminal tail vertex of a hub label at each level of the MLO data structure, and wherein forward labels maintain complete hub information while backward labels are asymmetrically pruned to reduce storage requirements and accelerate queries;

determining, using the one or more processors and the one or more hub labels, a shortest path or a cost between the first node and the second node; and

autonomously navigating a delivery vehicle along the delivery route.

5 . The method of claim 4 , wherein the first node is a starting location of a delivery route, wherein the second node is a destination location of the delivery route, and wherein the shortest path is a delivery route between the starting location and the destination location.

6 . The method of claim 4 , further comprising:

modifying an order of hub identifiers associated with the one or more hubs labels into a sequential order.

7 . The method of claim 4 , further comprising:

storing, in memory, one or more ranges of hub identifier values instead of all hub identifiers.

8 . The method of claim 4 , further comprising:

performing a forward search of the shortest path graph from the first node;

performing a backward search of the shortest path graph from the second node; and

determining, based on the forward search and the backward search, a first cell within the shortest path graph in which the forward search and backward search intersect, wherein determining the shortest path between the first node and the second node further comprises performing a search within the first cell and a first level associated with the first cell instead of a second cell and a second level associated with the second cell.

9 . The method of claim 8 , further comprising:

determining that a current interval minimum is higher than a best cost value, wherein an interval comprises a continuous range of hub identifier values that are stored together with an associated interval minimum to reduce memory usage and enable interval skipping during query processing; and

advancing to a subsequent source interval and/or a subsequent target interval based on the determination without examining individual hub identifiers within the current interval.

10 . A system comprising:

memory that stores computer-executable instructions; and

one or more processors configured to access the memory and execute the computer-executable instructions to:

determine, based on a multi-level overlay algorithm, one or more hub labels associated with one or more nodes included within a shortest path graph;

receive an indication of a first node and a second node of the one or more nodes;

perform a forward search of the shortest path graph from the first node;

perform a backward search of the shortest path graph from the second node;

determine, based on the forward search and the backward search, a first cell within the shortest path graph in which the forward search and backward search intersect;

perform a search within the first cell and a first level associated with the first cell instead of a second cell and a second level associated with the second cell;

determine that a current interval minimum is higher than a best cost value, wherein an interval comprises a continuous range of hub identifier values that are stored together with an associated interval minimum to reduce memory usage and enable interval skipping during query processing;

advance to a subsequent source interval and/or a subsequent target interval based on the determination without examining individual hub identifiers within the current interval;

determine, based on the multi-level overlay data structure, and using the one or more hub labels, a shortest path or a cost between the first node and the second node; and

autonomously navigate a delivery vehicle along the delivery route.

11 . The system of claim 10 , wherein the first node is a starting location of a delivery route, wherein the second node is a destination location of the delivery route, and wherein the shortest path is a delivery route between the starting location and the destination location.

12 . The system of claim 10 , wherein the one or more processors are further configured to execute the computer-executable instructions to:

modify an order of hub identifiers associated with the one or more hubs labels into a sequential order.

13 . The system of claim 10 , wherein the one or more processors are further configured to execute the computer-executable instructions to:

store, in memory, a range of hub identifier values instead of all hub identifiers.

14 . The system of claim 10 , wherein the one or more processors are further configured to execute the computer-executable instructions to:

generate canonical labels using asymmetric pruning.