# US 2021/0241227 A1 · Automatically planning delivery routes using clustering

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0241227 A1
- Document ID: US20210241227A1
- Status: Published application
- Kind: A1
- Application number: 16/778,659
- Filed: 2020-01-31
- Published: 2021-08-05
- Earliest claimed: 2020-01-31
- Assignees: Walmart Apollo, LLC
- Applicants: Walmart Apollo, LLC
- Inventors: Chenxin Ma; Mingang Fu
- Web page: https://patentgrep.com/patent/US20210241227A1

## CPC

- G06Q 10/08355: {Routing methods}
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/285: {Clustering or classification}
- G06F 16/906: Clustering; Classification
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06Q 10/06312: {Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling}
- 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
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method including planning delivery routes using clustering. The method can include extracting (a) location information of nodes from order data, (b) time window information of the nodes from the order data, and (c) load capacity information of delivery vehicles. The method further can include generating, in real-time, one or more clusters for the nodes based, at least in part, on (a) the location information of the nodes and (b) the load capacity information. Each of the one or more clusters can be associated with a respective vehicle of one or more dispatched vehicles of the delivery vehicles. The method also can include determining, in real-time, a respective centroid for each of the one or more clusters based on location information of cluster nodes of the nodes for each of the one or more clusters. Further, the method can include computing, in real-time, a node-cluster distance matrix. The node-cluster distance matrix can comprise a respective node-cluster distance between each of the nodes and each of the one or more clusters based, at least in part, on a respective distance between each of the nodes and the respective centroid for each of the one or more clusters. Additionally, the method can include reassigning, in real-time, the nodes to the one or more clusters based, at least in part, on: (a) the node-cluster distance matrix; (b) load capacity information of the one or more dispatched vehicles; and (c) a predetermined average load threshold of the one or more dispatched vehicles. Moreover, the method can include further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters based, at least in part, on the time window information of the nodes. Other embodiments are disclosed.

## Claims

### Claim 1

A system comprising:
one or more processors; and
one or more non-transitory computer-readable media storing computing instructions configured to run on the one more processors and perform:
extracting (a) location information of nodes from order data, (b) time window information of the nodes from the order data, and (c) load capacity information of delivery vehicles;
generating, in real-time, one or more clusters for the nodes based, at least in part, on (a) the location information of the nodes and (b) the load capacity information, wherein:
each of the one or more clusters is associated with a respective vehicle of one or more dispatched vehicles of the delivery vehicles;
determining, in real-time, a respective centroid for each of the one or more clusters based on location information of cluster nodes of the nodes for each of the one or more clusters;
computing, in real-time, a node-cluster distance matrix, wherein the node-cluster distance matrix comprises a respective node-cluster distance between each of the nodes and each of the one or more clusters based, at least in part, on a respective distance between each of the nodes and the respective centroid for each of the one or more clusters;
reassigning, in real-time, the nodes to the one or more clusters based, at least in part, on:
the node-cluster distance matrix;
load capacity information of the one or more dispatched vehicles; and
a predetermined average load threshold of the one or more dispatched vehicles; and
further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters based, at least in part, on the time window information of the nodes.

### Claim 2 (depends on 1)

The system in claim 1, wherein:
the computing instructions are further configured to run on the one or more processors and perform:
when an estimated delivery time for at least one node of the nodes, after further reassigning the nodes to the one or more clusters, fails to match a time window of the at least one node:
adding a new cluster to the one or more clusters; and
re-generating, in real-time, the one or more clusters for the nodes.

### Claim 3 (depends on 1)

The system in claim 1, wherein:
reassigning the nodes to the one or more clusters further comprises:
determining a closest cluster of the one or more clusters for each of the nodes, wherein:
a distance between each of the nodes and the closest cluster in the node-cluster-distance matrix is less than a respective node-cluster distance between each of the nodes and each other cluster of the one or more clusters in the node-cluster-distance matrix; and
the closest cluster is different from a respective current cluster of the one or more clusters for each of the nodes; and
when (a) the closest cluster exists; and (b) the closest cluster has an available load capacity for each of the nodes:
when a substitute node exists in both the closest cluster and a transfer list, switching each of the nodes with the substitute node;
when (a) the substitute node does not exist; and (b) the respective current cluster for each of the nodes has a respective used load capacity rate at least as great as the predetermined average load threshold, moving each of the nodes to the closest cluster; and
when (a) the substitute node does not exist; and (b) the respective used load capacity rate is less than the predetermined load threshold: adding each of the nodes to the transfer list.

### Claim 4 (depends on 3)

The system in claim 3, wherein:
the computing instructions are further configured to run on the one or more processors and perform:
determining, in real-time after determining the closest cluster for each of the nodes, that the substitute node, for each of the nodes from both the closest cluster and the transfer list, exists, when switching the substitute node and each of the nodes between results in a negative combined node-cluster distance change.

### Claim 5 (depends on 3)

The system in claim 3, wherein:
reassigning the nodes to the one or more clusters further comprises:
updating, in real-time, the respective centroid for each of the one or more clusters; and
re-computing, in real-time, the node-cluster distance matrix.

### Claim 6 (depends on 1)

The system in claim 1, wherein:
further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters further comprises:
determining a respective delivery route for each of the one or more clusters for the nodes;
when each of one or more first nodes of the nodes comprises a respective time window:
optimizing a respective first node delivery route for each of the one or more first nodes in each of the one or more clusters; and
optimizing a respective remaining node delivery route for each of one or more remaining nodes in each of the one or more clusters, wherein each of the one or more remaining nodes comprises no time window.

### Claim 7 (depends on 6)

The system in claim 6, wherein:
at least one of:
optimizing the respective first node delivery route for each of the one or more first nodes in each of the one or more clusters further comprises applying a greedy algorithm to determine an optimal slot for the first node in the respective delivery route based, at least in part, on:
the respective time window for the respective first node; and
a respective node-node distance between each pair of cluster nodes in each of the one or more clusters; or
optimizing the respective remaining node delivery route for each of the one or more remaining nodes in each of the one or more clusters further comprises applying a greedy algorithm to determine a respective optimal slot for each of the one or more remaining nodes in the respective delivery route based, at least in part, on:
a respective node-node distance between each pair of cluster nodes in each of the one or more clusters.

### Claim 8 (depends on 6)

The system in claim 6, wherein:
further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters further comprises:
repeating one or more acts for further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters for a predetermined reiteration count;
assigning, in real-time after each repetition of the one or more acts, a count of at least one of the one or more first nodes to an infeasible order count, when an estimated delivery time for the at least one of the one or more first nodes fails to match a time window of the at least one of the one or more first node; and
stopping repeating the one or more acts before reaching the predetermined reiteration count, when at least one of:
the infeasible order count is zero;
the infeasible order count is greater than a predetermined infeasible count threshold determined based on a total orders count from the order data; or
the one or more clusters remain unchanged after 2 consecutive repetitions of the one or more acts.

### Claim 9 (depends on 1)

The system in claim 1, wherein:
computing, in real-time, the node-cluster distance matrix further comprises one or more of:
determining the respective node-cluster distance based on a street distance on a map; or
when a ratio between a distribution width of node projections for the nodes on the map along a first axis in a Cartesian coordinate system and a distribution width of the node projections along a second axis orthogonal to the first axis is less than a predetermined threshold distributed, stretching the node projections along the first axis before computing the node-cluster distance matrix.

### Claim 10 (depends on 1)

The system in claim 1, wherein:
generating the one or more clusters for the nodes further comprises:
when (a) at least two nodes of the nodes have identical destinations; and (b) at least one of: (i) a respective cluster for each of the at least two nodes is different; or (ii) a respective slot for each of the at least two nodes in an identical delivery route is different from each other, merging the at least two nodes.

### Claim 11

A method being implemented via execution of computing instructions configured to run at one or more processors and stored at one or more non-transitory computer-readable media, the method comprising:
extracting (a) location information of nodes from order data, (b) time window information of the nodes from the order data, and (c) load capacity information of delivery vehicles;
generating, in real-time, one or more clusters for the nodes based, at least in part, on (a) the location information of the nodes and (b) the load capacity information, wherein:
each of the one or more clusters is associated with a respective vehicle of one or more dispatched vehicles of the delivery vehicles;
determining, in real-time, a respective centroid for each of the one or more clusters based on location information of cluster nodes of the nodes for each of the one or more clusters;
computing, in real-time, a node-cluster distance matrix, wherein the node-cluster distance matrix comprises a respective node-cluster distance between each of the nodes and each of the one or more clusters based, at least in part, on a respective distance between each of the nodes and the respective centroid for each of the one or more clusters;
reassigning, in real-time, the nodes to the one or more clusters based, at least in part, on:
the node-cluster distance matrix;
load capacity information of the one or more dispatched vehicles; and
a predetermined average load threshold of the one or more dispatched vehicles; and
further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters based, at least in part, on the time window information of the nodes.

### Claim 12 (depends on 11)

The method in claim 11 further comprising:
delivery time for at least one node of the nodes, after further reassigning the nodes to the one or more clusters, fails to match a time window of the at least one node:
adding a new cluster to the one or more clusters; and
re-generating, in real-time, the one or more clusters for the nodes.

### Claim 13 (depends on 11)

The method in claim 11, wherein:
reassigning the nodes to the one or more clusters further comprises:
determining a closest cluster of the one or more clusters for each of the nodes, wherein:
a distance between each of the nodes and the closest cluster in the node-cluster-distance matrix is less than a respective node-cluster distance between each of the nodes and each other cluster of the one or more clusters in the node-cluster-distance matrix; and
the closest cluster is different from a respective current cluster of the one or more clusters for each of the nodes; and
when (a) the closest cluster exists; and (b) the closest cluster has an available load capacity for each of the nodes:
when a substitute node exists in both the closest cluster and a transfer list, switching each of the nodes with the substitute node;
when (a) the substitute node does not exist; and (b) the respective current cluster for each of the nodes has a respective used load capacity rate at least as great as the predetermined average load threshold, moving each of the nodes to the closest cluster; and
when (a) the substitute node does not exist; and (b) the respective used load capacity rate is less than the predetermined load threshold: adding each of the nodes to the transfer list.

### Claim 14 (depends on 13)

The method in claim 13 further comprising:
determining, in real-time after determining the closest cluster for each of the nodes, that the substitute node, for each of the nodes from both the closest cluster and the transfer list, exists, when switching the substitute node and each of the nodes between results in a negative combined node-cluster distance change.

### Claim 15 (depends on 13)

The method in claim 13, wherein:
reassigning the nodes to the one or more clusters further comprises:
updating, in real-time, the respective centroid for each of the one or more clusters; and
re-computing, in real-time, the node-cluster distance matrix.

### Claim 16 (depends on 11)

The method in claim 11, wherein:
further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters further comprises:
determining a respective delivery route for each of the one or more clusters for the nodes;
when each of one or more first nodes of the nodes comprises a respective time window:
optimizing a respective first node delivery route for each of the one or more first nodes in each of the one or more clusters; and
optimizing a respective remaining node delivery route for each of one or more remaining nodes in each of the one or more clusters, wherein each of the one or more remaining nodes comprises no time window.

### Claim 17 (depends on 16)

The method in claim 16, wherein:
at least one of:
optimizing the respective first node delivery route for each of the one or more first nodes in each of the one or more clusters further comprises applying a greedy algorithm to determine an optimal slot for the first node in the respective delivery route based, at least in part, on:
the respective time window for the respective first node; and
a respective node-node distance between each pair of cluster nodes in each of the one or more clusters; or
optimizing the respective remaining node delivery route for each of the one or more remaining nodes in each of the one or more clusters further comprises applying a greedy algorithm to determine a respective optimal slot for each of the one or more remaining nodes in the respective delivery route based, at least in part, on:
a respective node-node distance between each pair of cluster nodes in each of the one or more clusters.

### Claim 18 (depends on 16)

The method in claim 16, wherein:
further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters further comprises:
repeating one or more acts for further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters for a predetermined reiteration count;
assigning, in real-time after each repetition of the one or more acts, a count of at least one of the one or more first nodes to an infeasible order count, when an estimated delivery time for the at least one of the one or more first nodes fails to match a time window of the at least one of the one or more first node; and
stopping repeating the one or more acts before reaching the predetermined reiteration count, when at least one of:
the infeasible order count is zero;
the infeasible order count is greater than a predetermined infeasible count threshold determined based on a total orders count from the order data; or
the one or more clusters remain unchanged after 2 consecutive repetitions of the one or more acts.

### Claim 19 (depends on 11)

The method in claim 11, wherein:
computing, in real-time, the node-cluster distance matrix further comprises one or more of:
determining the respective node-cluster distance based on a street distance on a map; or
when a ratio between a distribution width of node projections for the nodes on the map along a first axis in a Cartesian coordinate system and a distribution width of the node projections along a second axis orthogonal to the first axis is less than a predetermined threshold distributed, stretching the node projections along the first axis before computing the node-cluster distance matrix.

### Claim 20 (depends on 11)

The method in claim 11 wherein:
generating the one or more clusters for the nodes further comprises:
when (a) at least two nodes of the nodes have identical destinations; and (b) at least one of: (i) a respective cluster for each of the at least two nodes is different; or (ii) a respective slot for each of the at least two nodes in an identical delivery route is different from each other, merging the at least two nodes.