Flexible dock-out time

Patent metadata

Field	Value
Publication number	US-12062009-B2
Application number	US-202117163475-A
Country	US
Kind code	B2
Filing date	Jan 31, 2021
Priority date	Jan 30, 2019
Publication date	Aug 13, 2024
Grant date	Aug 13, 2024

Abstract

A system including one or more processors and one or more non-transitory computer-readable media storing computing instructions configured to run on the one or more processors and perform: generating a feasible dock-out plan designed to deliver one or more orders to one or more physical stores based on a feasible route plan by: generating a preliminary dock-out time boundary based on one or more delivery time windows; determining an earliest dock-out time based at least in part on the preliminary dock-out time boundary and a backward search; and determining a latest dock-out time based at least in part on the preliminary dock-out time boundary and a forward search; and transmitting a range of dock-out times comprising (i) the earliest dock-out time and (ii) the latest dock-out time to a user. Other embodiments are described.

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 that, when executed on the one or more processors, cause the one or more processors to perform operations comprising:
generating, by a routing system, a feasible dock-out plan designed to deliver one or more orders to one or more physical stores based on constraints within a feasible route plan, wherein the feasible dock-out plan comprises a flexible period of time within which to dispatch a trailer to begin transporting orders, wherein the routing system communicates with a communication system to deliver the one or more orders to the one or more physical stores within the flexible period of time, and wherein generating the feasible dock-out plan comprises:
generating, by the routing system, a preliminary dock-out time boundary based on one or more delivery time windows; and
processing, by the routing system using multiple algorithms, two parallel data flow paths to locate a range of dock-out times associated with time constraints of the one or more delivery time windows within the feasible route plan to reduce sequences of time outside of the range of dock-out times, wherein the multiple algorithms comprise a backward binary search and a forward binary search, and wherein processing, using the multiple algorithms, the two parallel data flow paths further comprises:
determining, using the backward binary search, an earliest dock-out time based at least in part on the preliminary dock-out time boundary and a backward search, wherein the backward search comprises using an iterative process moving backward by decrements to locate an earliest dock-out time range of the range of dock-out times, and wherein the earliest dock-out time range is located between a backward non-optimal dock-out start time (BNOST) and a backward optimal dock-out start time (BOST); and
determining, using the forward binary search, a latest dock-out time based at least in part on the preliminary dock-out time boundary and a forward search; and

transmitting, by the communication system, the range of dock-out times comprising (i) the earliest dock-out time and (ii) the latest dock-out time to a user, wherein the trailer is dispatched to a distribution center between the range of dock-out times to load the trailer and deliver each order within each respective time constraint associated with a respective delivery time window of the one or more delivery time windows to minimize transportation and loading costs based on the flexible period of time.

2. The system of claim 1 , wherein generating the preliminary dock-out time boundary further comprises:
computing, by the routing system, a minimal time window length (minTWL) by:
computing a respective time window length for each physical store of the one or more physical stores based on the one or more delivery time windows; and
selecting the minTWL as a lowest one of the respective time window lengths from among the one or more physical stores;
when the minTWL exceeds a predetermined boundary period of time, decreasing the minTWL based on an amount of time exceeded; and

outputting the preliminary dock-out time boundary based on the minTWL.

3. The system of claim 1 , wherein determining the earliest dock-out time further comprises:
generating, by the routing system using the backward binary search, a backward non-optimal dock-out time period for the earliest dock-out time range of dock-out times using the backward search further comprises:
determining an initial value of the BOST based on a start time (ST) of the feasible dock-out plan;
determining a step length based on the preliminary dock-out time boundary;
determining an initial value of the BNOST based on the BOST and the step length;
comparing a cost of the BNOST with a cost of the BOST; and
when the cost of the BOST is less than the cost of the BNOST, outputting the BOST and the BNOST.

4. The system of claim 3 , wherein generating the backward non-optimal dock-out time period using the backward search further comprises:
when the cost of the BOST equals the cost of the BNOST, updating the BOST as the BNOST; and
decrementing the BNOST based on the step length.

5. The system of claim 3 , wherein generating the backward non-optimal dock-out time period using the backward search further comprises:
when the cost of the BOST is greater than the cost of the BNOST, resetting the ST as the BNOST, resetting the BOST as the BNOST, and resetting the cost of the BOST as the cost of the BNOST.

6. The system of claim 3 , wherein determining the earliest dock-out time further comprises:
determining, using the backward binary search, the earliest dock-out time between the BOST and the BNOST based on a cost of intermediate points between the BOST and the BNOST.

7. The system of claim 1 , determining the latest dock-out time further comprises:
generating, by the routing system using the forward binary search, a forward non-optimal dock-out time period for the latest dock-out time of the range of dock-out times using the forward search, comprising:
determining an initial value of a forward optimal start time (FOST) based on a start time (ST) of the feasible dock-out plan;
determining a step length based on the preliminary dock-out time boundary;
determining an initial value of a forward non-optimal start time (FNOST) based on the FOST and the step length;
comparing a cost of the FNOST with a cost of the FOST; and
when the cost of the FOST is less than the cost of the FNOST, outputting the FOST and the FNOST.

8. The system of claim 7 , wherein generating the forward non-optimal dock-out time period further comprises:
when the cost of the FOST equals the cost of the FNOST, updating the FOST as the FNOST; and
incrementing the FNOST based on the step length.

9. The system of claim 7 , wherein generating the forward non-optimal dock-out time period further comprises:
when the cost of the FOST is greater than the cost of the FNOST, resetting the ST as the FNOST, resetting the FOST as the FNOST, and resetting the cost of the FOST as the cost of the FNOST.

10. The system of claim 7 , wherein determining the latest dock-out time further comprises:
determining, by the routing system using the forward binary search, the latest dock-out time between the FOST and the FNOST based on a cost of intermediate points between the FOST and the FNOST.

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:
generating, by a routing system, a feasible dock-out plan designed to deliver one or more orders to one or more physical stores based on constraints within a feasible route plan, wherein the feasible dock-out plan comprises a flexible period of time within which to dispatch a trailer to begin transporting orders, wherein the routing system communicates with a communication system to deliver the one or more orders to the one or more physical stores within the flexible period of time, and wherein generating the feasible dock-out plan comprises:
generating, by the routing system, a preliminary dock-out time boundary based on one or more delivery time windows; and
processing, by the routing system using multiple algorithms, two parallel data flow paths to locate a range of dock-out times associated with time constraints of the one or more delivery time windows within the feasible route plan to reduce sequences of time outside of the range of dock-out times, wherein the multiple algorithms comprise a backward binary search and

Assignees

• Walmart Apollo Llc

Inventors

• Huang Jing
• Sun Ou
• Liu Minghui
• Fu Mingang
• Hendricks Joseph Wayne
• Moola Ranjith

Classifications

• G06F16/29

  Geographical information databases · CPC title

• G01C21/3484

  Personalized, e.g. from learned user behaviour or user-defined profiles · CPC title

• G01C21/343

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title

• G06Q10/08355 Primary

  Routing methods · CPC title