Holistically Solving Vehicle Routing and Container Loading Problems for Middle Mile Grocery Delivery
By: Jing Huang, Mingang Fu, and Minghui Liu
The Problem
At Walmart, our middle mile includes all the channels that deliver items from distribution centers (DCs) to stores. It is responsible for delivering 100,000+ grocery pallets from more than 40 DCs to over 5,000 stores every day. We’re continually analyzing the most efficient and cost-effective ways to move these commodities. Due to high replenishment frequencies and low replenishment volume, it’s been challenging to build a dedicated truckload of pallets for each store. We need to consolidate pallets delivered to multiple stores into one truck while considering the most optimal route for quickly transporting items and reducing empty miles.
Additionally, we had to consider how middle mile delivery could accommodate significant number of regulations and constraints, as compared to other delivery channels (e.g., last mile delivery).
Vehicle routing and trailer loading problems are widely studied, but we found that common solutions fall short because:
- Routing and loading must be solved simultaneously, while sequential solve is lengthy and hard to reach
- Truck routing (mid/long haul) needs to consider drivers’ hours-of-service regulations put in place by the Department of Transportation (DOT)
- The placement of perishable items within a reefer trailer with a maximum of three compartments must be optimized and comply with many rules
Simply put, there is a greater opportunity to optimize the way we route items from DCs to stores and load trailers with pallets to increase efficiency. Using our knowledge of retail technology, we decided to tackle these problems ourselves.
What We Needed
Once a grocery DC receives an order to be delivered to a store, its warehouse management system converts orders into virtual pallets. Each virtual pallet includes plans for building a 40x48-inch wood frame carrying multiple cases of goods. A middle mile delivery optimization system would take those virtual pallets as input and produce a set of schedules with the most efficient loading plans (i.e., how pallets should be arranged in each trailer) and an optimal set of routes for getting these pallets to designated stores.
Due to hours-of-service regulations, we determined the output route should not only contain delivery sequences but also detailed driver activities, like when to take breaks and layovers. When a trailer load plan is generated, along with a route, it typically contains the row, column, orientation of each pallet, positioning of the bulkhead, temperature settings for each compartment, and empty pallets.
From a routing perspective, store orders should be delivered within the store delivery window. To make a routing solution desirable, backhauls are added to the routes to make the route more efficient. From a loading perspective, the optimizer should optimize the trailer utilization while satisfying all constraints.
The major goal of middle mile delivery optimization is to find optimal routes and loads with the most efficient operations as well as better serve the store needs.
Our Solution
We built a tabu search-based framework with neighborhood search and heuristics to solve routing and loading in one shot. Our solution analyzes problem characteristics to find the best algorithm among various heuristics and mixed integer programming models for solving different use cases. It then constructs a feasible initial route using the selected algorithm. Then, the tabu search algorithm scans a very large solution space to find the best possible solution.
A route solution not only contains detailed activities occurring at each delivery route, but it also specifies which pallets belong to each delivery route and the trailer needed to move those pallets. Once optimal routes are established, we offer load design improvements to optimize the arrangement of pallets in each trailer for optimal weight balances.
We developed many innovative heuristics to reduce problematic dimensions and running time, which improved the solution’s quality. With the help of our “secret sauces,” our solution outperformed others provided by industry-leading companies. It achieved 1% cost savings for dry good deliveries and 3–4% cost savings for perishable good deliveries. In addition to the improvements in solution quality, the system running time is 15 minutes, which is significantly lower than the running time provided by the third-party product.
How Exactly Does It Work?
One of our solution highlights is fast feasibility detection of a routing and loading solution. It’s critical to optimization and computation time. In our proposed framework, route improvement (usually solving for vehicle routing problems) is the most critical step where tabu search is applied. Because of the many hours-of-service rules and various loading rules, the feasibility check for middle mile solutions is more complicated than finding traditional vehicle routing problems. That’s why we developed innovative routing and loading heuristics to reduce the computation time of a feasibility check.
For example, let’s consider a loading feasibility check. Instead of a traditional 3D bin packing design problem, we tackled the problem from a different point of view. We first separated stacking construction as a pre-process to help us transform a 3D loading problem into a 2D problem. After stacks were constructed, we used an algorithm to determine floor spots on the trailer instead of sequencing stacks to determine their positions and orientations one-by-one. Floor spots can be considered virtual “placeholders” for stacks with fixed positions and orientations. Because of this step, we didn’t have to consider where to place each individual stack; all we needed to know was how many stacks could be placed in the container. Next, our algorithm leverages a set of existing loading patterns — such as width, length, pinwheeling, and hybrid — to narrow down possible floor spot configurations. This means that when floor spots are placed inside a trailer and pallets are consolidated into stacks, we can assign those specific stacks to each floor spot.
Another key idea we introduced focuses on improving optimization through active order split. This contrasts with passive order split in which we must split a store’s order when it can’t fit into a single container. The motivation behind this thinking is we can achieve better load consolidation with orders from other stores by actively splitting a store’s order even when it doesn’t have to be split to fit into a container. We designed multiple algorithms to determine active split, such as store location-based heuristic and mixed integer programming for order-to-route template assignment. This idea can increase the total number of stops, but it reduces cost by increasing trailer utilization and reducing the number of routes and miles traveled. Besides, the route improvement algorithm can efficiently identify and avoid redundant active split by combining them into one route.
Other highlights to our solution include the ability to order loading patterns based on unnecessary unloading, minimize wait time while complying with DOT rules, generalize design in hours-of-service for easy adaptation to ever-changing transportation rules, and so on.
Besides continuous enhancement from an algorithm perspective, efficient implementation is also key. With code optimization, especially for the part of tabu search, we were not only able to search more in the solution space for better optimization but also expedite the development process by significantly reducing system running time.
What’s Next
Walmart is currently rolling out the solution to our grocery DC network. It just went live in over 40 grocery DCs in July 2022. Additionally, we’re exploring additional opportunities to leverage this framework and continue improving our middle mile delivery.
The solution has proven to be flexible and extendible enough to accommodate additional business rules to potentially use in other networks, such as reverse logistics and GM network. We have successfully leveraged this framework to solve for delivering both frozen and dry goods to stores in Alaska and Hawaii via boat. The current algorithm also features many improvements such as parallelization and ensembling various algorithms. This new framework allows us to try various algorithms and continuously improve its effectiveness.
Finally, fully owning our own middle mile delivery solution framework enables us to further integrate routing and loading considerations into upstream replenishment systems. If we consider routing and loading costs when orders are placed, then the transportation system is likely to be more efficient when executing store orders. For example, store orders from a specific location are more likely to fill a truckload when combined with orders from a nearby store. Walmart is currently working on routing and loading optimization that’s deeply integrated with replenishment planning to generate optimal store orders and minimize transportation cost using adaptive learning algorithms.
Continually advancing our middle mile delivery system will help to provide seamless experiences for our employees and customers. It’s an exciting time to be part of Walmart!
Acknowledgement
The solution framework has been implemented as core optimizer of Load Planner (Walmart outbound delivery and trailer planning system) and rolled out to Walmart Grocery Network. We would like to thank the following teams who were instrumental in making it happen: the product team lead by Travis Johnson, Shwetal Mokashi, Joe Hendricks, Ankush Bhargava and Franky Xiao; the engineering team lead by Parvez Musani, Sai Kumar, and Ranjith Moola; and our data science team members Ou Sun, Aditya Srinivasan, Ti Zhang, Xiaojie Wang, Fereydoun Adbesh, Tiantian Nie, and Daniel Zuniga Vazquez.
