Systems and methods for optimizing delivery routes using fleet vehicles and third-party deliverers

Patent metadata

Field	Value
Publication number	US-11810059-B2
Application number	US-202217982394-A
Country	US
Kind code	B2
Filing date	Nov 7, 2022
Priority date	Dec 6, 2016
Publication date	Nov 7, 2023
Grant date	Nov 7, 2023

Abstract

Systems and methods including 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 functions comprising: determining at least one fleet delivery route for delivery of one or more items of one or more orders to one or more locations using a vehicle fleet; dynamically shuffling the at least one fleet delivery route by at least evaluating a cost differential; when the cost differential satisfies a threshold: removing the first order from the source route; inserting the first order into the first other delivery route; and communicating the first order to a first other deliverer associated with the first other delivery route. Additional embodiments are disclosed herein.

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 functions comprising:
determining at least one fleet delivery route for delivery of one or more items of one or more orders to one or more locations using a vehicle fleet;
dynamically shuffling the at least one fleet delivery route by at least evaluating a cost differential between (a) removing a first order of the one or more orders from a source route, and (b) inserting the first order into a first other delivery route of one or more other delivery routes;
when the cost differential satisfies a threshold:
removing the first order from the source route; and
inserting the first order into the first other delivery route; and

communicating the first order to a first other deliverer associated with the first other delivery route for delivery of the first order at a first location of the one or more locations.

2. The system of claim 1 , wherein dynamically shuffling the at least one fleet delivery route comprises:
selecting the source route from the at least one fleet delivery route;
selecting the first order of the one or more orders from the source route, wherein the first order is scheduled to be delivered to the first location of the one or more locations as part of the at least one fleet delivery route and before dynamically shuffling the at least one fleet delivery route; and
selecting, using a random number generator, the first other delivery route associated with the first other deliverer of one or more other deliverers from the one or more other delivery routes.

3. The system of claim 1 , wherein evaluating the cost differential comprises using simulated annealing.

4. The system of claim 1 , wherein the computing instructions, when executed on the one or more processors, further cause the one or more processors to perform functions comprising:
receiving the one or more orders;
determining whether an additional order of the one or more orders are for delivery at an additional location of the one or more locations that is within (i) a predetermined distance from the first location for the first order or (ii) a predetermined traveling time from the first location for the first order;
when the additional order is for the delivery at the additional location that is within at least the predetermined distance or the predetermined traveling time, removing the additional order from the at least one fleet delivery route; and
communicating the additional order to the first other deliverer for the delivery of the additional order at the additional location.

5. The system of claim 4 , wherein receiving the one or more orders, determining the at least one fleet delivery route, dynamically shuffling the at least one fleet delivery route, and communicating the first order to the first other deliverer are performed in real-time.

6. The system of claim 1 , wherein the first other deliverer comprises a commercial delivery service or a crowdsourced delivery service that does not use the vehicle fleet.

7. The system of claim 1 , wherein determining the at least one fleet delivery route comprises using a heuristic greedy insertion algorithm.

8. The system of claim 1 , wherein:
the at least one fleet delivery route comprises a plurality of nodes; and
each node of the plurality of nodes comprises a different location of the one or more locations.

9. The system of claim 8 , wherein dynamically shuffling the at least one fleet delivery route further comprises:
performing a randomized node movement on the at least one fleet delivery route.

10. The system of claim 8 , wherein inserting the first order into the first other delivery route comprises:
upon removing a first node of the plurality of nodes from the source route, inserting the first node of the plurality of nodes into the first other delivery route of the one or more other delivery routes, when inserting the first node into the first other delivery route satisfies the threshold of the cost differential.

11. A method being implemented via execution of computing instructions configured to run on one or more processors and stored at one or more non-transitory computer-readable media, the method comprising:
determining at least one fleet delivery route for delivery of one or more items of one or more orders to one or more locations using a vehicle fleet;
dynamically shuffling the at least one fleet delivery route by at least evaluating a cost differential between (a) removing a first order of the one or more orders from a source route, and (b) inserting the first order into a first other delivery route of one or more other delivery routes;
when the cost differential satisfies a threshold:
removing the first order from the source route; and
inserting the first order into the first other delivery route; and

communicating the first order to a first other deliverer associated with the first other delivery route for delivery of the first order at a first location of the one or more locations.

12. The method of claim 11 , wherein dynamically shuffling the at least one fleet delivery route comprises:
selecting the source route from the at least one fleet delivery route;
selecting the first order of the one or more orders from the source route, wherein the first order is scheduled to be delivered to the first location of the one or more locations as part of the at least one fleet delivery route and before dynamically shuffling the at least one fleet delivery route; and
selecting, using a random number generator, the first other delivery route associated with the first other deliverer of one or more other deliverers from the one or more other delivery routes.

13. The method of claim 11 , wherein evaluating the cost differential comprises using simulated annealing.

14. The method of claim 11 , further comprising:
receiving the one or more orders;
determining whether an additional order of the one or more orders are for delivery at an additional location of the one or more locations that is within (i) a predetermined distance from the first location for the first order or (ii) a predetermined traveling time from the first location for the first order;
when the additional order is for the delivery at the additional location that is within at least the predetermined distance or the predetermined traveling time, removing the additional order from the at least one fleet delivery route; and
communicating the additional order to the first other deliverer for the delivery of the additional order at the additional location.

15. The method of claim 14 , wherein receiving the one or more orders, determining the at least one fleet delivery route, dynamically shuffling the at least one fleet delivery route, and communicating the first order to the first other deliverer are performed in real-time.

16. The method of claim 11 , wherein the first other deliverer comprises a commercial delivery service or a crowdsourced delivery service that does not use the vehicle fleet.

17. The method of claim 11 , wherein determining the at least one fleet delivery route comprises using a heuristic greedy insertion algorithm.

18. The method of claim 11 , wherein:
the at least one fleet delivery route comprises a plurality of nodes; and
each node of the plurality of nodes comprises a different location of the one or more locations.

19. The method of

Assignees

• Walmart Apollo Llc

Inventors

• Fu Mingang
• Deshpande Deepak
• Seetharaman Prakash
• Pattathil Devadas

Classifications

• G06Q10/08355 Primary

  Routing methods · CPC title