Delivery Hero reduces middle mile costs with AWS-powered route optimization

Delivery Hero is a leader in the food delivery and quick commerce (q-commerce) industry, providing on-demand delivery services in multiple markets globally. The company has become a pioneer in q-commerce, specializing in the rapid delivery of groceries, household items, and other essentials, with the business now having a strong presence in over 50 countries. By leveraging a network of local partners, dark stores (a local warehouse to fulfill online orders enabling rapid deliveries), and cutting-edge technology, Delivery Hero ensures rapid fulfillment, catering to the growing consumer demand for speed and convenience in everyday shopping. This forward-thinking strategy positions Delivery Hero as a leader in the rapidly evolving q-commerce landscape. The middle-mile transshipment process – movement of goods from distribution centers to dark stores – directly impacts the timely replenishment of dark stores and overall inventory management. To address these challenges, Delivery Hero requires an automated vehicle capacity planning and intelligent route optimization solution. This post details how we tackle the daily middle mile transportation planning challenges of Delivery Hero q-commerce network using a constrained vehicle routing problem solution running on Amazon Web Services (AWS) cloud, and resulting in savings of up to 24% for the middle-mile planning process. Following an initial proof-of-concept (POC) phase, AWS Professional Services and Delivery Hero launched the route optimization solution in a selected market and also conducted minimum viable product (MVP) studies for two other markets.

Middle mile as a pocket of operational opportunity

One of the crucial aspects of q-commerce is stock availability, requiring real-time inventory management to ensure that items displayed as available are delivered as soon as possible. Inventory shortage results in customer dissatisfaction, order cancellations, and a loss of trust- the outcomes that are particularly damaging in a market driven by speed and reliability. Effective middle-mile planning plays a pivotal role in ensuring stock availability by facilitating timely replenishment of dark stores and minimizing customer delivery delays. Optimizing the movement of goods from distribution centers to dark stores ensures adequate inventory levels, aligning with the fast-paced demands of q-commerce while enhancing operational efficiency.

The middle-mile network at Delivery Hero consists of distribution centers (DCs), typically located on the outskirts of urban regions. In most cases, a single DC serves all stores within a region. However, in regions with multiple DCs, each DC is assigned a specific set of stores, which are distributed strategically across the urban area. This structure ensures efficient inventory replenishment, with each DC fulfilling orders exclusively for its designated stores. The diagram provides an example of the high-level network structure and illustrates how a daily transportation plan with milk-runs (a logistics operation where a single vehicle performs multiple pickups or deliveries in one trip) encompasses multiple store deliveries. In this example, the routing plan uses two vehicles. Truck 1 is loaded twice at the DC while visiting stores A and B in one trip and stores G, H and K in another. Truck 2 is loaded only once and visits stores C, D, E and F.

Across multiple markets, transshipment is either handled by a third-party logistics provider (3PL) or Delivery Hero-operated DCs using milk-run operations. Once the final order set for each dark store is confirmed, next-day operations are planned at the close of business. Order preparation at the DC, including palletization, packaging, and staging, is conducted overnight, ensuring vehicles are loaded and ready for dispatch at the start of the day. The planning process we consider in this post encapsulates Steps 2 and 3.

To effectively manage middle-mile transshipment, day-ahead route planning faces several significant challenges that necessitate an automated vehicle capacity planning and intelligent route optimization solution. For instance, in one of its markets, Delivery Hero operates four DCs supporting over 150 stores, with fleet sizes ranging from 10 to 18 vehicles depending on the DC scale. Daily pallet movement between DCs and stores fluctuates significantly, varying from 50 to 60 pallets to nearly 150 pallets. One of the main issues is the high variability in order volumes and delivery destinations, which can fluctuate daily based on demand patterns, promotions, and seasonal trends. This unpredictability complicates route planning because fixed or manual routes often lead to inefficiencies, increased costs, and delays. Additionally, multiple constraints, such as vehicle capacity, delivery time windows, and dark store cut-off times, must be balanced to minimize delays and ensure timely replenishment. Without automation, manually balancing these factors becomes time-intensive, prone to human error, and less adaptable to the last-minute changes or disruptions. Moreover, effective milk-run optimization requires careful route sequencing to consolidate deliveries and reduce empty miles, which is challenging in a dense urban landscape, where traffic conditions, congestion patterns, and vehicle accessibility add further complexity. Together, these factors also highlight the need for an advanced vehicle capacity planning and route optimization that dynamically adjusts routes based on evolving constraints, thereby maximizing efficiency, reducing operational costs, and ensuring reliable, on-time delivery to each dark store.

Recognizing these challenges, Delivery Hero and AWS Professional Services partnered to develop a comprehensive route optimization solution tailored to the specific demands of Delivery Hero middle-mile transshipment process. Our solution uses an advanced algorithm to simultaneously consider order volume, delivery windows, and vehicle capacity, ensuring that routes are optimized for efficiency and cost-effectiveness. By incorporating traffic and travel time forecasts alongside just-in-time operational constraints, our tool offers the flexibility to adapt to daily fluctuations and last-minute changes. This streamlines the replenishment process for each dark store while boosting overall service reliability.

Solution

Navigating complexity in middle-mile planning

Daily route planning with milk-runs presents a significant challenge because it needs to accommodate the constantly shifting demands of dark stores. The orders from dark stores vary dynamically from day-to-day based on their sales performance and inventory replenishment policies. As a result, operating with fixed routes or even a fixed schedule of periodic visits is neither practical nor efficient. Consequently, as the orders fluctuate, the output of the order planning process, serving as the input for the transportation planning process, also changes on a daily basis, requiring continuous adjustments to ensure optimal operations.

The components of the daily transportation planning process include dark stores, planned deliveries to each dark store, and the fleet. Because the locations of dark stores and the set of available vehicles at DCs remain constant, the daily planning process operates with a fixed distribution network and a fixed set of resources. The main dynamic input is the daily planned deliveries to each dark store. A solution needs to solve a constrained vehicle routing problem that consolidates the planned deliveries, assigns them to vehicles, and creates routing sequences for each vehicle trip. To fully automate the transportation planning process and ensure its operational feasibility, the problem formulation needs to include all relevant constraints.

The Vehicle Routing Problem (VRP) is a complex logistics challenge that focuses on finding the most efficient routes for a fleet of vehicles to deliver goods to various locations. The typical objective is to minimize travel time, costs, or CO2 while adhering to specific constraints, such as vehicle capacity and delivery time windows. In essence, the VRP seeks to optimize the allocation of resources by determining the most efficient delivery routes, thereby reducing time, fuel consumption, and operational costs.

Delivery Hero’s challenges are not far away from the well-known challenges of solving routing problems. In their case, the biggest challenge is to create a solution that is adaptable to various markets under their global operations. Although the main principle of a two-tiered network structure with DCs and dark stores is the same across markets, the operational constraints and restrictions imposed by their 3PL contractual agreements and local legislations create different versions of the VRP in different markets.

A modular and adaptable VRP solution for different markets

In order to overcome the challenge of varying constraints in different markets, we developed a solution where operational constraints are implemented in a modular structure, the objective of the problem can be changed and different variations of the contractual restrictions and considerations can be integrated into the model. Our eventual goal is to create a solution that is modular and adaptable to each market for a fully automated and tailored middle-mile planning process.

For one of Delivery Hero markets, as an example, we considered fleet-related constraints, time-related constraints and vehicle-store compatibility constraints. Fleet-related constraints include the availability of different vehicle types, each with its own specific capacity. The time-related constraints include the driver’s shift duration, the store and DC operational time-windows (the opening and closing hours) as well as the loading and unloading times at the DC and stores. For this example market, we also consider compatibility between vehicles and stores as some stores are able to accept a limited set of vehicles depending on their size. The optimization criteria considers both fixed costs corresponding to daily rental price of vehicles (based on the vehicle size) and variable costs due to route lengths.

By removing any of the constraint modules, we modify the modular structure exemplified in the diagram. For example, we remove the time-windows module if there are no such constraints in a market. If there are additional constraints limiting the types of orders that a certain subset of vehicles transport (e.g., some orders need to be transported in refrigerated compartments), we add an “order-specific” constraint module under the vehicle-compatibility constraints. The optimization criteria have fixed costs and variable costs, depending on the situation. Note that we can also replace the optimization criteria with a cost function considering the driver’s working hours. For Delivery Hero, we employ a meta-heuristic solver chosen using experiments on the historical planning data of the market. Delivery Hero can replace the meta-heuristic algorithm for another market after conducting sufficient experiments with its own historical data.

Business value from a POC

Reducing operational costs and maximizing fleet utilization while adhering to business-critical performance metrics focused on timely and accurate inventory replenishment, are the key objectives for Delivery Hero. Furthermore, the ability to make swift and precise daily planning decisions is fundamental to improving their supply chain performance. During the POC phase of this project, we observed the following results:

1. The back-testing experiments using historical data from the selected market demonstrated that our solution achieved a 24% reduction in total costs (including both fixed and variable). This reduction was primarily driven by a 22% decrease in mileage, with the remainder attributed to more efficient vehicle sizing decisions with vehicle utilization increasing from 81% to 96%.
2. The selected market had four DCs and each one required daily manual planning efforts of 1 – 2.5 hours depending on the scale of operations. The AWS solution requires only 5 – 10 minutes per DC to produce plans that outperform previous solutions by the benefit above.

In the subsequent MVP phase of the project, we tested the modular solution for its market adaptability. Although it is highly unlikely that two markets have exactly the same set of constraints and contractual restrictions, we were able to observe that the level of effort required to modify the model was reasonable due to the modular structure of the solution. This was recognized as a key advantage of opting for a built solution, as it offered greater customization and flexibility compared to the off-the-shelf alternatives. As AWS Professional Services handed over the solution to the data science teams at Delivery Hero through an end-to-end extensive knowledge transfer, the Delivery Hero in-house data science teams are now fully capable of modifying the solution according to the requirements of different markets.

After a successful POC in a selected market, Delivery Hero launched the initial production version of the middle-mile route optimization solution. Following a transition period, Delivery Hero plans to fully replace the existing manual planning process in the selected market with the automated solution developed in this collaboration. Furthermore, the Warehousing & Distribution organization identified the next two markets for implementation, with historical data from these markets already collected for back-testing and performance evaluation.

Productionizing the solution

For the DC planners, Delivery Hero built a user interface (UI) that accesses the required input data including the orders, the stores and the available fleet. Considering the requirements for integration with their UI through the Transportation Management System (TMS), we built the reference architecture to deploy the daily middle-mile planning solution backend.

The core logic of the optimization solution is containerized and stored on Amazon ECR. The container is pulled and run as ephemeral jobs on AWS Batch, backed by AWS Fargate. We leverage AWS Batch and AWS Fargate for scalability, i.e., to launch multiple independent jobs if necessary, or scale to zero when not needed, as well as its low cold start time to avoid creating overhead for the optimization task. We use AWS Lambda to submit jobs on AWS Batch providing an easier-to-use serverless architecture so that the Delivery Hero Transportation Management System (TMS) can directly trigger the Lambda function without knowing the details of the compute environment, reducing the dependency between teams and avoiding the effort of maintaining a full API (e.g., Amazon API Gateway, which remains viable for larger teams). Inputs and outputs for the optimization task are stored on Amazon Simple Storage Service (Amazon S3) for scalability, availability and fine-tuned access control. Once the task is complete, TMS is notified via Amazon SQS and retrieves the optimization results from Amazon S3. Authentication between TMS and the optimization backend is provided by AWS Identity and Access Management (IAM). Finally, if TMS needs to update geographical data about the DCs or stores, it can query the data from Amazon Location Service.

With the successful integration of this reference architecture into both the newly-developed user interface (UI) and the existing TMS solution, scaling the solution to additional markets only requires the deployment of the UI in the respective regions. Consequently, this will significantly reduce the learning curve for users in planner roles, because they only need to familiarize themselves with the interactive functionalities of the new UI.

The AWS route optimization solution can be integrated into an existing AWS architecture or as a standalone API to provide a seamless integration with existing order management and transportation management systems. The solution comes with a generic backend architecture and provides the flexibility to use different AWS services for deployment (e.g., AWS Batch, Amazon SageMaker). As a highly portable solution, the reference architecture is only one of many options for deployment. For example, one can build a more decoupled service architecture with REST API on Amazon API Gateway, or store and update data on Amazon DynamoDB with a GraphQL API on AWS AppSync, or streamline orchestration with AWS Step Functions.

Conclusion

The effectiveness of middle-mile transportation is pivotal to the success of q-commerce operations at Delivery Hero. The AWS route optimization solution reduces costs and improves vehicle utilization, both by double digit percentages, while aligning with Delivery Hero performance metrics to facilitate timely and efficient deliveries. Given the diverse and varying conditions across the markets in which Delivery Hero operates, the modular design of the solution allows for easy adaptation to market-specific constraints. Once deployed in all markets, the solution’s global impact will result in millions of dollars in reduced operational costs. Additionally, integrating the unified UI experience with order management, transportation management systems, and the route optimization backend streamlines adoption, minimizing daily effort from the end-user perspective.

While the primary purpose of the route optimization solution is day-ahead planning, it can also be effectively utilized for tactical planning to optimize resource allocation and for strategic planning to guide network design and configuration. For tactical planning, it is able to simulate 3PL contractual conditions and evaluate their impact under various scenarios to identify robust parameters and optimal arrangements. For strategic planning, back-testing on historical or forecasted data enables analysis of alternative facility locations, adjustments to store assignment schemes, and potential shifts in network expansion or contraction strategies.