IP Library Granted Patent US 11,615,368
Granted Patent B2
US 11,615,368 · App. 16/178,526 · Granted Mar 28, 2023

Systems and methods for determining delivery time and route assignments

Inventors: Mingang Fu (Palo Alto, CA); Madhavan Kandhadai Vasantham (Dublin, CA); Aditya Arcot Srinivasan (Sunnyvale, CA)
Assignee: Walmart Apollo, LLC
G06Q10/0833G05D1/0217G06N20/00
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,615,368
App. No.
16/178,526
Granted
Mar 28, 2023
Kind
B2
Abstract

Systems and methods for optimizing delivery vehicle resources (e.g. a plurality of vehicles) are described herein. Available time slots for the plurality of vehicles are determined and presented to a user. In response to receiving a delivery order indicating a selected time slot, the delivery order is assigned to a vehicle from the plurality of vehicles based on a time slot indicated in the delivery order and a set of delivery parameters. A delivery route is calculated for each vehicle having a delivery order based on the set of delivery parameters. An optimized delivery route is calculated for each vehicle having a delivery order based on the set of delivery parameters.

Claims (78)

1. An apparatus comprising:

a computing device including:

a communications interface configured to communicate with, over one or more networks, a plurality of user terminals and a vehicle server, the vehicle server configured to communicate with a computing device of each of a plurality of vehicles;

a memory resource storing instructions; and

one or more processors communicatively coupled to the communications interface and memory resource, the one or more processors being configured to execute the instructions to:

receive, over the one or more networks and from the vehicle server, time data of the plurality of vehicles, wherein the time data includes a plurality of time slots for each of the plurality of vehicles that are used for a plurality of deliveries;

determine at least one available time slot among the plurality of time slots and communicate, over the one or more networks, the at least one available time slot to at least one user terminal of the plurality of user terminals;

receive, over the one or more networks and from the at least one user terminal, at least one delivery order indicating at least one selected time slot from the at least one available time slot; and

in response to receiving the at least one delivery order indicating the at least one selected time slot, implementing one or more vehicle resource optimization operations, the one or more vehicle resource optimization operations including:

determining a test delivery time interval for each of a set of trained machine learning processes by applying each of the set of trained machine learning processes to test data including at least one time and geo based feature associated with a previous delivery and a determined delivery time interval of the previous delivery;

selecting, from the set of trained machine learning processes, a trained machine learning process with a determined test delivery time interval that is closest to the determined delivery time interval of the previous delivery;

training the selected trained machine learning process with a plurality of weights applied to the test data;

determining at least one weight from the plurality of weights based on a closest match of a previously predicted delivery time interval to at least one actual delivery time associated with the test data;

applying the at least one weight to a set of purchase order feature data to generate weighted purchase order feature data associated with the at least one delivery order;

determining a predicted delivery time interval for the at least one delivery order by applying the selected trained machine learning process to the weighted purchase order feature data including at least one time and geo based feature associated with the at least one delivery order and at least one item based feature associated with the at least one delivery order, the item based feature characterizing one of a plurality of characteristics of at least one item of the at least one delivery order and the predicted delivery time interval being a predicted amount of time between when a vehicle arrives at a destination location of the at least one delivery order and when the vehicle departs the destination location;

assigning the at least one delivery order to a vehicle from the plurality of vehicles based, at least in part, on the at least one selected time slot indicated in the at least one delivery order and the determined predicted delivery time interval;

calculating, for the assigned vehicle, an optimized delivery route based, at least in part, on the determined predicted delivery time interval; and

transmit, over the one or more networks and to a computing device of the assigned vehicle via the vehicle server, the optimized delivery route.

2. The apparatus of claim 1 wherein the selected trained machine learning process applied to determine the predicted delivery time interval is at least one of: ridge regression, support vector regression using a linear kernel, random forest, and XGBoost.

3. The apparatus of claim 1 wherein the test data may further include at least one item based feature associated with the previous delivery.

4. The apparatus of claim 1 wherein the set of purchase order feature data further includes a shipping source feature, and a delivery destination based feature.

5. The apparatus of claim 1 wherein the one or more processors are configured to execute the instructions further to:

apply a first weight to data identifying a first purchase order feature of the set of purchase order feature data;

apply a second weight to data identifying a second purchase order feature of the set of purchase order feature data; and

apply the selected trained machine learning process to the first weighted data identifying the first purchase order feature and to the second weighted data identifying the second purchase order feature.

6. The apparatus of claim 1 wherein the computing device is configured to:

determine, based on the application of the selected trained machine learning process, that assigning the at least one delivery order to a first vehicle from the plurality of vehicles will prevent any previously scheduled deliveries assigned to the first vehicle from being completed on time;

determine, based on the application of the selected trained machine learning process, that assigning the at least one delivery order to a second vehicle from the plurality of vehicles will not prevent any previously scheduled deliveries assigned to the second vehicle from being completed on time; and

assign the at least one delivery order to the second vehicle from the plurality of vehicles.

7. A method comprising:

receiving, over one or more networks and from a vehicle server and by a processor, time data of a plurality of vehicles, wherein the time data includes a plurality of time slots for each of the plurality of vehicles that are used for a plurality of deliveries;

determining, by the processor, at least one available time slot among the plurality of time slots and communicate, over the one or more networks, the at least one available time slot to at least one user terminal of a plurality of user terminals;

receiving, over the one or more networks and from the at least one user terminal and by the processor, at least one delivery order indicating at least one selected time slot from the at least one available time slot;

in response to receiving the at least one delivery order indicating the at least one selected time slot, implementing, by the processor, one or more vehicle resource optimization operations, the one or more vehicle resource optimization operations including:

determining a test delivery time interval for each of a set of trained machine learning processes by applying each of the set of trained machine learning processes to test data including at least one time and geo based feature associated with a previous delivery and a determined delivery time interval of the previous delivery;

selecting, from the set of trained machine learning processes, a trained machine learning process with a determined test delivery time interval that is closest to the determined delivery time interval of the previous delivery;

training the selected trained machine learning process with a plurality of weights applied to the test data;

determining at least one weight from the plurality of weights based on a closest match of a previously predicted delivery time interval to at least one actual delivery time associated with the test data;

applying the at least one weight to a set of purchase order feature data to generate weighted purchase order feature data associated with the at least one delivery order;

determining a predicted delivery time interval for the at least one delivery order by applying the selected trained machine learning process to the weighted purchase order feature data associated with the at least one delivery order including at least one time and geo based feature associated with the at least one delivery order and at least one item based feature associated with the at least one delivery order, the item based feature characterizing one of a plurality of characteristics of at least one item of the at least one delivery order and the predicted delivery time interval being a predicted amount of time between when a vehicle arrives at a destination location of the at least one delivery order and when the vehicle departs the destination location;

assigning the at least one delivery order to a vehicle from the plurality of vehicles based, at least in part, on the at least one selected time slot indicated in the at least one delivery order and the predicted delivery time interval;

calculating, for the assigned vehicle, an optimized delivery route based, at least in part, on the predicted delivery time interval; and

transmitting, over the one or more networks to a computing device of the assigned vehicle via the vehicle server and by the processor, the optimized delivery route.

8. The method of claim 7 wherein the selected trained machine learning process applied to determine the predicted delivery time interval is at least one of: ridge regression, support vector regression using a linear kernel, random forest, and XGBoost.

9. The method of claim 7 , wherein the test data may further include at least one item based feature associated with the previous delivery.

10. The method of claim 7 wherein the set of purchase order feature data further includes a shipping source feature, and a delivery destination based feature.

11. The method of claim 7 further comprising:

applying a first weight to data identifying a first purchase order feature of the set of purchase order feature data;

applying a second weight to data identifying a second purchase order feature of the set of purchase order feature data; and

applying the selected trained machine learning process to the first weighted data identifying the first purchase order feature and to the second weighted data identifying the second purchase order feature.

12. The method of claim 7 further comprising training the selected trained machine learning process based on measured delivery times and associated purchase order features for previous purchase order deliveries.

13. The method of claim 7 further comprising:

determining, based on the application of the selected trained machine learning process, that assigning the at least one delivery order to a first vehicle from the plurality of vehicles will prevent any previously scheduled deliveries assigned to the first vehicle from being completed on time;

determining, based on the application of the selected trained machine learning process, that assigning the at least one delivery order to a second vehicle from the plurality of vehicles will not prevent any previously scheduled deliveries assigned to the second vehicle from being completed on time; and

assigning the at least one delivery order to the second vehicle from the plurality of vehicles.

14. A non-transitory computer readable medium having instructions stored thereon, wherein the instructions, when executed by at least one processor, cause a device to perform operations comprising:

receiving, over one or more networks and from a vehicle server, time data of a plurality of vehicles, wherein the time data includes a plurality of time slots for each of the plurality of vehicles that are used for a plurality of deliveries;

determining at least one available time slot among the plurality of time slots and communicate, over the one or more networks, the at least one available time slot to at least one user terminal of a plurality of user terminals;

receiving, over the one or more networks and from the at least one user terminal, at least one delivery order indicating at least one selected time slot from the at least one available time slot;

in response to receiving the at least one delivery order indicating the at least one selected time slot, implementing one or more vehicle resource optimization operations, the one or more vehicle resource optimization operations including:

determining a test delivery time interval for each of a set of trained machine learning processes by applying each of the set of trained machine learning processes to test data including at least one time and geo based feature associated with a previous delivery and a determined delivery time interval of the previous delivery;

selecting, from the set of trained machine learning processes, a trained machine learning process with a determined test delivery time interval that is closest to the determined delivery time interval of the previous delivery;

training the selected trained machine learning process with a plurality of weights applied to the test data;

determining at least one weight from the plurality of weights based on a closest match of a previously predicted delivery time interval to at least one actual delivery time associated with the test data;

applying the at least one weight to a set of purchase order feature data to generate weighted purchase order feature data associated with the at least one delivery order;

determining a predicted delivery time interval for the at least one delivery order by applying the selected trained machine learning process to the weighted purchase order feature data associated with the at least one delivery order including at least one time and geo based feature associated with the at least one delivery order and at least one item based feature associated with the at least one delivery order, the item based feature characterizing one of a plurality of characteristics of at least one item of the at least one delivery order and the predicted delivery time interval being a predict amount of time between when a vehicle arrives at a destination location of the at least one delivery order and when the vehicle departs the destination location;

assigning the at least one delivery order to a vehicle from the plurality of vehicles based, at least in part, on the at least one selected time slot indicated in the at least one delivery order and the determined predicted delivery time interval;

calculating, for the assigned vehicle, an optimized delivery route based, at least in part, on the predicted delivery time interval; and

transmitting, over the one or more networks to a computing device of the assigned vehicle via the vehicle server, the optimized delivery route.

15. The non-transitory computer readable medium of claim 14 wherein the selected trained machine learning process applied to determine the predicted delivery time interval is at least one of: ridge regression, support vector regression using a linear kernel, random forest, and XGBoost.

16. The non-transitory computer readable medium of claim 14 further comprising instructions stored thereon that, when executed by the at least one processor, further cause the device to perform operations comprising:

applying a first weight to data identifying a first purchase order feature of the set of purchase order feature data;

applying a second weight to data identifying a second purchase order feature of the set of purchase order feature data; and

applying the selected trained machine learning process to the first weighted data identifying the first purchase order feature and to the second weighted data identifying the second purchase order feature.

17. The non-transitory computer readable medium of claim 14 further comprising instructions stored thereon that, when executed by the at least one processor, further cause the device to perform operations comprising:

determining, based on the application of the selected trained machine learning process, that assigning the at least one delivery order to a first vehicle from the plurality of vehicles will prevent any previously scheduled deliveries assigned to the first vehicle from being completed on time;

determining, based on the application of the selected trained machine learning process, that assigning the at least one delivery order to a second vehicle from the plurality of vehicles will not prevent any previously scheduled deliveries assigned to the second vehicle from being completed on time; and

assigning the at least one delivery order to the second vehicle from the plurality of vehicles.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 1, 2018
From: FU, MINGANG; KANDHADAI VASANTHAM, MADHAVAN; ARCOT SRINIVASAN, ADITYA
To: WALMART APOLLO, LLC
Reel/Frame 047389/0218 →
Continuity (1)
Related Publication 20200143319A1 · May 7, 2020
Cited By (3)
US 12,524,799 US 12,547,975 US 12,602,648