Automatically planning delivery route

Patent metadata

Field	Value
Publication number	US-12111163-B2
Application number	US-202318102828-A
Country	US
Kind code	B2
Filing date	Jan 30, 2023
Priority date	Jan 31, 2020
Publication date	Oct 8, 2024
Grant date	Oct 8, 2024

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.

First claim

What is claimed is:

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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

Assignees

• Walmart Apollo Llc

Inventors

• Ma Chenxin
• Fu Mingang

Classifications

• G06Q50/40 Primary

  Business processes related to the transportation industry (shipping G06Q10/083) · CPC title

• G06Q10/08355

  Routing methods · CPC title

• G01C21/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) · CPC title

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G01C21/3415 Primary

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title