# US 2021/0239473 A1 · 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 2021/0239473 A1
- Document ID: US20210239473A1
- Status: Published application
- Kind: A1
- Application number: 16/777,966
- 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/US20210239473A1

## 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 automatically planning delivery routes. The method can include extracting an initial delivery route from the delivery data. The initial delivery route can comprises delivery stops. The method also can include setting a preferred delivery route as the initial delivery route. The method also can include evaluating, in real-time, the preferred delivery route. The method also can include repeating evaluating, in real-time, the preferred delivery route until a predetermined stop condition occurs. The method further can include, after repeating evaluating, in real-time, the preferred delivery route, transmitting, in real-time via a 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 run on the one more processors and perform:
extracting an initial delivery route from the delivery data, wherein the initial delivery route comprises delivery stops;
setting a preferred delivery route as the initial delivery route;
evaluating, in real-time, the preferred delivery route, comprising:
determining a to-be-resequenced delivery stop list based on the preferred delivery route, wherein:
the to-be-resequenced delivery stop list has a random quantity of delivery stops;
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 a modified preferred delivery route containing remaining delivery stops from the preferred delivery route that are not in the random quantity of delivery stops;
the each delivery stop of the preferred delivery route is selected to be moved to the to-be-resequenced delivery stop list by using a selecting act of multiple delivery-stop-selecting acts;
the selecting act is determined based, at least in part, on a random number; and
at any point in time during the evaluating the preferred delivery route, the delivery stops of the preferred delivery route comprise the remaining delivery stops of the modified preferred delivery route and the delivery stops of the random quantity of delivery stops of the to-be-resequenced delivery stop list;
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 to create the resequenced delivery route, wherein:
all of the delivery stops of the preferred delivery route are in the resequenced delivery route; and
a sequence of the delivery stops of the preferred delivery route are different from a sequence of the delivery stops of the resequenced delivery route;
determining, in real-time, whether the resequenced delivery route is preferred over the preferred delivery route;
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
when the resequenced delivery route is determined to not be preferred over the delivery route, maintaining, in real-time, the preferred delivery route;
repeating evaluating, in real-time, the preferred delivery route until a predetermined stop condition occurs; and
after repeating evaluating, in real-time, the preferred delivery route, transmitting, in real-time via a 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.

### Claim 2 (depends on 1)

The system in claim 1, wherein:
the multiple delivery-stop-selecting acts for selecting the delivery stops from 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 delivery stop; 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 3 (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:
generating the 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 in the delivery stop information; 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 savings; 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 routes.

### 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 routes; 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 additions;
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 routes.

### 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 run on the one or more processors and perform:
generating the random quantity within a range defined by a function of a total quantity of the 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 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 delivery stops of the preferred delivery route, determining that the resequenced delivery route is preferred over the preferred delivery route.

### 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 an initial delivery route from the delivery data, wherein the initial delivery route comprises delivery stops;
setting a preferred delivery route as the initial delivery route;
evaluating, in real-time, the preferred delivery route, comprising:
determining a to-be-resequenced delivery stop list based on the preferred delivery route, wherein:
the to-be-resequenced delivery stop list has a random quantity of delivery stops;
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 a modified preferred delivery route containing remaining delivery stops from the preferred delivery route that are not in the random quantity of delivery stops;
the each delivery stop of the preferred delivery route is selected to be moved to the to-be-resequenced delivery stop list by using a selecting act of multiple delivery-stop-selecting acts;
the selecting act is determined based, at least in part, on a random number; and
at any point in time during the evaluating the preferred delivery route, the delivery stops of the preferred delivery route comprise the remaining delivery stops of the modified preferred delivery route and the delivery stops of the random quantity of delivery stops of the to-be-resequenced delivery stop list;
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 to create the resequenced delivery route, wherein:
all of the delivery stops of the preferred delivery route are in the resequenced delivery route; and
a sequence of the delivery stops of the preferred delivery route are different from a sequence of the delivery stops of the resequenced delivery route;
determining, in real-time, whether the resequenced delivery route is preferred over the preferred delivery route;
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
when the resequenced delivery route is determined to not be preferred over the delivery route, maintaining, in real-time, the preferred delivery route;
repeating evaluating, in real-time, the preferred delivery route until a predetermined stop condition occurs; and
after repeating evaluating, in real-time, the preferred delivery route, transmitting, in real-time via a 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.

### Claim 12 (depends on 11)

The method in claim 11, wherein:
the multiple delivery-stop-selecting acts for selecting the delivery stops from 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 delivery stop; 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 13 (depends on 11)

The method in claim 11 further comprising:
generating the 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 in the delivery stop information; 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 savings; and
selecting the most-cost-saving delivery stop from the modified preferred delivery route.

### Claim 14 (depends on 11)

The method in claim 11, 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 routes.

### Claim 15 (depends on 11)

The method in claim 11, 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 16 (depends on 11)

The method in claim 11, 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 routes; 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 additions;
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 routes.

### Claim 17 (depends on 16)

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

### Claim 18 (depends on 11)

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

### Claim 19 (depends on 18)

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

### Claim 20 (depends on 11)

The method in claim 11, 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 delivery stops of the preferred delivery route, determining that the resequenced delivery route is preferred over the preferred delivery route.
