# US 12,111,163 B2 · Automatically planning delivery route

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

- Number: US 12,111,163 B2
- Document ID: US12111163B2
- Status: Granted
- Kind: B2
- Application number: 18/102,828
- Filed: 2023-01-30
- Published: 2023-06-08
- Granted: 2024-10-08
- Earliest claimed: 2020-01-31
- Assignees: Walmart Apollo, LLC
- Applicants: Walmart Apollo, LLC
- Inventors: Chenxin Ma; Mingang Fu
- Web page: https://patentgrep.com/patent/US12111163B2

## CPC

- G01C 21/3415: {Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents}
- G01C 21/3492: {employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968)}
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06Q 10/08355: {Routing methods}
- G06Q 50/40: Business processes related to the transportation industry (shipping G06Q10/083)
- 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 including setting a preferred delivery route as an initial delivery route comprising original delivery stops. The method further can include evaluating, in real-time, the preferred delivery route, comprising: (a) determining a to-be-resequenced delivery stop list by moving a random quantity of delivery stops from the original delivery stops to the to-be-resequenced delivery stop list based on a delivery-stop-selecting act, wherein: after the to-be-resequenced delivery stop list is determined, a modified preferred delivery route comprises remaining delivery stops from the original delivery stops; (b) after determining the to-be-resequenced delivery stop list, creating, in real-time, a resequenced delivery route by adding each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list to the modified preferred delivery route; (c) determining, in real-time, whether the resequenced delivery route is preferred over the preferred delivery route; and (d) when the resequenced delivery route is determined to be preferred over the preferred delivery route, resetting, in real-time, the preferred delivery route to be the resequenced delivery route. The method further can include transmitting, in real-time via a computer network, the preferred delivery route to a driver mobile device of a delivery driver for the delivery driver to follow the preferred delivery route to make deliveries. 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, when run on the one or more processors, cause the one or more processors to perform:
setting a preferred delivery route as an initial delivery route comprising original delivery stops;
evaluating, in real-time, the preferred delivery route, comprising:
generating a random act-selecting number;
determining a delivery-stop-selecting act from multiple delivery-stop-selecting acts based, at least in part, on the random act-selecting number, as generated;
determining a to-be-resequenced delivery stop list by moving a random quantity of delivery stops from the original delivery stops to the to-be-resequenced delivery stop list based on the delivery-stop-selecting act, as determined, wherein:
after the to-be-resequenced delivery stop list is determined, a modified preferred delivery route comprises remaining delivery stops from the original delivery stops;
after determining the to-be-resequenced delivery stop list, creating, in real-time, a resequenced delivery route by adding each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list to the modified preferred delivery route;
determining, in real-time, whether the resequenced delivery route is preferred over the preferred delivery route; and
when the resequenced delivery route is determined to be preferred over the preferred delivery route, resetting, in real-time, the preferred delivery route to be the resequenced delivery route; and
transmitting, in real-time via a computer network, the preferred delivery route, as reset, to a driver mobile device of a delivery driver for the delivery driver to follow the preferred delivery route, as reset, to make deliveries.

### Claim 2 (depends on 1)

The system in claim 1, wherein:
the multiple delivery-stop-selecting acts for selecting delivery stops to be moved to the to-be-resequenced delivery stop list comprise two or more of:
randomly picking a particular one of the delivery stops to be removed from the preferred delivery route;
determining the particular one of the delivery stops to be removed from the preferred delivery route based on a cost for the particular one of the delivery stops; or
choosing the particular one of the delivery stops to be removed from the preferred delivery route based, at least in part, on a position of a previously resequenced delivery stops in a prior version of the preferred delivery route.

### Claim 3 (depends on 1)

The system in claim 1, wherein the computing instructions are further configured to, when run on the one or more processors, cause the one or more processors to perform:
generating a random number within a predefined range; and
each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list is moved from the preferred delivery route to the to-be-resequenced delivery stop list to create the modified preferred delivery route based, at least in part, on:
when (a) the random number is greater than a random number threshold defined by a function of a quantity of the delivery stops; and (b) a prior version of the preferred delivery route exists, choosing a delivery stop from the preferred delivery route based on a position of a previously resequenced delivery stop in the prior version of the preferred delivery route;
when (a) (i) the random number is not greater than the random number threshold, or (ii) no prior version of the preferred delivery route exists; and (b) the random quantity of delivery stops is greater than a predefined delivery stop count threshold, randomly picking a delivery stop from the preferred delivery route; and
when (a) (i) the random number is not greater than the random number threshold, or (ii) no prior version of the preferred delivery route exists; and (b) the random quantity of delivery stops is not greater than the predefined delivery stop count threshold:
determining a respective cost saving for removing each delivery stop of the remaining delivery stops of the modified preferred delivery route;
determining a most-cost-saving delivery stop of the remaining delivery stops of the modified preferred delivery route based on the respective cost saving; and
selecting the most-cost-saving delivery stop from the modified preferred delivery route.

### Claim 4 (depends on 1)

The system in claim 1, wherein creating, in real-time, the resequenced delivery route comprises:
after adding each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route, sorting, in real-time, the remaining delivery stops of the modified preferred delivery route.

### Claim 5 (depends on 1)

The system in claim 1, wherein creating, in real-time, the resequenced delivery route further comprises:
after adding each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route, using a greedy algorithm on the resequenced delivery route.

### Claim 6 (depends on 1)

The system in claim 1, wherein creating, in real-time, the resequenced delivery route further comprises:
when the random quantity is greater than a predetermined quantity threshold:
after adding each delivery stop of the random quantity of delivery stops from the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route, sorting, in real-time, the remaining delivery stops of the modified preferred delivery route; and
when the random quantity is not greater than the predetermined quantity threshold:
determining a respective cost addition for adding each delivery stop of the random quantity of delivery stops from the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route;
determining a lowest-cost-addition delivery stop of the random quantity of delivery stops from the to-be-resequenced delivery stop list based on the respective cost addition;
moving the lowest-cost-addition delivery stop from the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route; and
after moving the lowest-cost-addition delivery stop from the to-be-resequenced delivery stop list, sorting, in real-time, the remaining delivery stops of the modified preferred delivery route.

### Claim 7 (depends on 6)

The system in claim 6, wherein:
sorting the remaining delivery stops of the modified preferred delivery route comprises using a greedy algorithm on the modified preferred delivery route.

### Claim 8 (depends on 1)

The system in claim 1, wherein the computing instructions are further configured to, when run on the one or more processors, cause the one or more processors to perform:
generating the random quantity within a range defined by a function of a total quantity of the original delivery stops of the preferred delivery route.

### Claim 9 (depends on 8)

The system in claim 8, wherein:
the range is from 10% to 40% of the total quantity of the original delivery stops of the preferred delivery route.

### Claim 10 (depends on 1)

The system in claim 1, wherein:
determining, in real-time, whether the resequenced delivery route is preferred over the preferred delivery route comprises at least one of:
when a route cost of the resequenced delivery route is less than a route cost of the preferred delivery route, determining that the resequenced delivery route is preferred over the preferred delivery route; or
when a random number generated in a predefined range is greater than a threshold defined by a function of a variable associated with a total quantity of the original delivery stops of the preferred delivery route, determining that the resequenced delivery route is preferred over the preferred delivery route.

### Claim 11 (depends on 1)

The system in claim 1, wherein the computing instructions are further configured to, when run on the one or more processors, cause the one or more processors to perform:
repeating evaluating, in real-time, the preferred delivery route until a predetermined stop condition occurs, wherein the random quantity of delivery stops of the to-be-resequenced delivery stop list are re-determined for each iteration of the repeating evaluating the preferred delivery route.

### Claim 12

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:
setting a preferred delivery route as an initial delivery route comprising original delivery stops;
evaluating, in real-time, the preferred delivery route, comprising:
generating a random act-selecting number;
determining a delivery-stop-selecting act from multiple delivery-stop-selecting acts based, at least in part, on the random act-selecting number, as generated;
determining a to-be-resequenced delivery stop list by moving a random quantity of delivery stops from the original delivery stops to the to-be-resequenced delivery stop list based on the delivery-stop-selecting act, as determined, wherein:
after the to-be-resequenced delivery stop list is determined, a modified preferred delivery route comprises remaining delivery stops from the original delivery stops;
after determining the to-be-resequenced delivery stop list, creating, in real-time, a resequenced delivery route by adding each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list to the modified preferred delivery route;
determining, in real-time, whether the resequenced delivery route is preferred over the preferred delivery route; and
when the resequenced delivery route is determined to be preferred over the preferred delivery route, resetting, in real-time, the preferred delivery route to be the resequenced delivery route; and
transmitting, in real-time via a computer network, the preferred delivery route, as reset, to a driver mobile device of a delivery driver for the delivery driver to follow the preferred delivery route, as reset, to make deliveries.

### Claim 13 (depends on 12)

The method in claim 12, wherein:
the multiple delivery-stop-selecting acts for selecting delivery stops to be moved to the to-be-resequenced delivery stop list comprise two or more of:
randomly picking a particular one of the delivery stops to be removed from the preferred delivery route;
determining the particular one of the delivery stops to be removed from the preferred delivery route based on a cost for the particular one of the delivery stops; or
choosing the particular one of the delivery stops to be removed from the preferred delivery route based, at least in part, on a position of a previously resequenced delivery stop in a prior version of the preferred delivery route.

### Claim 14 (depends on 12)

The method in claim 12 further comprising:
generating a random number within a predefined range; and
each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list is moved from the preferred delivery route to the to-be-resequenced delivery stop list to create the modified preferred delivery route based, at least in part, on:
when (a) the random number is greater than a random number threshold defined by a function of a quantity of the delivery stops; and (b) a prior version of the preferred delivery route exists, choosing a delivery stop from the preferred delivery route based on a position of a previously resequenced delivery stop in the prior version of the preferred delivery route;
when (a) (i) the random number is not greater than the random number threshold, or (ii) no prior version of the preferred delivery route exists; and (b) the random quantity of delivery stops is greater than a predefined delivery stop count threshold, randomly picking a delivery stop from the preferred delivery route; and
when (a) (i) the random number is not greater than the random number threshold, or (ii) no prior version of the preferred delivery route exists; and (b) the random quantity of delivery stops is not greater than the predefined delivery stop count threshold:
determining a respective cost saving for removing each delivery stop of the remaining delivery stops of the modified preferred delivery route;
determining a most-cost-saving delivery stop of the remaining delivery stops of the modified preferred delivery route based on the respective cost saving; and
selecting the most-cost-saving delivery stop from the modified preferred delivery route.

### Claim 15 (depends on 12)

The method in claim 12, wherein creating, in real-time, the resequenced delivery route comprises:
after adding each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route, sorting, in real-time, the remaining delivery stops of the modified preferred delivery route.

### Claim 16 (depends on 12)

The method in claim 12, wherein creating, in real-time, the resequenced delivery route further comprises:
after adding each delivery stop of the random quantity of delivery stops of the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route, using a greedy algorithm on the resequenced delivery route.

### Claim 17 (depends on 12)

The method in claim 12, wherein:
creating, in real-time, the resequenced delivery route further comprises:
when the random quantity is greater than a predetermined quantity threshold:
after adding each delivery stop of the random quantity of delivery stops from the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route, sorting, in real-time, the remaining delivery stops of the modified preferred delivery route; and
when the random quantity is not greater than the predetermined quantity threshold:
determining a respective cost addition for adding each delivery stop of the random quantity of delivery stops from the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route;
determining a lowest-cost-addition delivery stop of the random quantity of delivery stops from the to-be-resequenced delivery stop list based on the respective cost addition;
moving the lowest-cost-addition delivery stop from the to-be-resequenced delivery stop list to the modified preferred delivery route to create the resequenced delivery route; and
after moving the lowest-cost-addition delivery stop from the to-be-resequenced delivery stop list, sorting, in real-time, the remaining delivery stops of the modified preferred delivery route.

### Claim 18 (depends on 17)

The method in claim 17, wherein:
sorting the remaining delivery stops of the modified preferred delivery route comprises using a greedy algorithm on the modified preferred delivery route.

### Claim 19 (depends on 12)

The method in claim 12 further comprising:
generating the random quantity within a range defined by a function of a total quantity of the original delivery stops of the preferred delivery route.

### Claim 20 (depends on 19)

The method in claim 19, wherein:
the range is from 10% to 40% of the total quantity of the original delivery stops of the preferred delivery route.

### Claim 21 (depends on 12)

The method in claim 12, wherein:
determining, in real-time, whether the resequenced delivery route is preferred over the preferred delivery route comprises at least one of:
when a route cost of the resequenced delivery route is less than a route cost of the preferred delivery route, determining that the resequenced delivery route is preferred over the preferred delivery route; or
when a random number generated in a predefined range is greater than a threshold defined by a function of a variable associated with a total quantity of the original delivery stops of the preferred delivery route, determining that the resequenced delivery route is preferred over the preferred delivery route.

### Claim 22 (depends on 12)

The method in claim 12, further comprising:
repeating evaluating, in real-time, the preferred delivery route until a predetermined stop condition occurs, wherein the random quantity of delivery stops of the to-be-resequenced delivery stop list are re-determined for each iteration of the repeating evaluating the preferred delivery route.