Optimize E-Commerce Last-Mile Delivery with Python
Organize your routes to deliver parcels with a minimum number of drivers using optimization models with Python.
E-commerce companies' main operational challenge is last-mile delivery; it can be complex and costly.
As a data scientist, what can you do?
If you travel to first and second-tier cities of China, you will find on the street many delivery drivers (Chinese: 快递).
They take the parcels from small warehouses called customer service centres (客户服务中心) located in each neighbourhood and deliver them to the final customers.
They provide extensive geographical coverage for last-mile delivery to offer the best service level and delivery lead time in the market.
How can you use Python to optimize the routing from these centres?
This article will present a solution to optimize the last-mile delivery from these centres, reducing costs and ensuring a uniform workload distribution to each driver.
I. How to optimize last-mile delivery with Python?
1. Problem Statement: Last Mile Delivery Optimization
2. Distance Matrix
3. Demand: number of parcels to deliver to each location
II. Build your Model
1. Import Distance Matrix and Init parameters
2. Create functions to calculate distances and order quantities
3. Build your model with constraints
4. Show the solution
III. Conclusion
1. Simulate Several Scenarios with Digital Twin
2. Container Loading Optimization with Python
3. Generative AI: GPT x Supply Chain OptimizationOptimize last-mile delivery with Python
Problem Statement: Last Mile Delivery Optimization
You are a data scientist at a courier company based in Shanghai.
The operational manager in a local service centre requested your support to manage his fleet
- Four drivers in your team
- 15 parcel capacity per vehicle
- 16 destinations to cover in the neighbourhood named Dj with j in [1, 16]
- D0 is the centre
- One route per driver
What are the parameters?
Distance Matrix
To build your model, you need to provide a distance matrix M as inputs defined by
- M(i, j) with i, j in [0, 16]
- M(i, j) = distance between Di and Dj
This distance matrix will be loaded from an Excel file. You can find an example of this scenario here: Link
They represent all the locations we must cover in the centre's scope.
What about the volumes of parcels?
Demand: number of parcels to deliver to each location
We will use here a Python list with the first value at zero (because you don’t provide anything in the centre)
- Demand = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
What do we want to achieve?
We want to deliver all parcels with a minimum number of drivers.
Objective
- Deliver all parcels with a minimum number of drivers
- Optimize the routing to minimize the distance covered per route
Let us run the model 👇
Results
Route for driver 0
0 Parcels(0) -> 4 Parcels(4) -> 3 Parcels(6) -> 1 Parcels(7) -> 7 Parcels(15) -> 0 Parcels(15)
Distance of the route: 1552 (m)
Parcels Delivered: 15 (parcels)
Route for driver 1
0 Parcels(0) -> 14 Parcels(4) -> 16 Parcels(12) -> 10 Parcels(14) -> 9 Parcels(15) -> 0 Parcels(15)
Distance of the route: 1552 (m)
Parcels Delivered: 15 (parcels)
Route for driver 2
0 Parcels(0) -> 12 Parcels(2) -> 11 Parcels(3) -> 15 Parcels(11) -> 13 Parcels(15) -> 0 Parcels(15)
Distance of the route: 1552 (m)
Parcels Delivered: 15 (parcels)
Route for driver 3
0 Parcels(0) -> 8 Parcels(8) -> 2 Parcels(9) -> 6 Parcels(13) -> 5 Parcels(15) -> 0 Parcels(15)
Distance of the route: 1552 (m)
Parcels Delivered: 15 (parcels)
Total distance of all routes: 6,208 (m)
Parcels Delivered: 60/60Based on these results, you can assign each of your four drivers a route that has the same total distance
- 100% of parcels are delivered with a minimum distance covered
- Drivers’ vehicles are loaded to their maximum capacity (15/15)
What are the benefits?
Using this model helps ensure that your drivers, who are paid a fixed amount by delivery, will be fairly assigned to a route.
You will avoid the issue of having drivers complaining because they have longer routes than their colleagues.
Moreover, you are using your resources at their maximum capacity.
How do we build this model?
Let me explain that to you in the next section.
🏫 Discover 70+ case studies using data analytics for supply chain optimization 🏭 and sustainability🌳🏪 in this Cheat Sheet
Build your Model
We will use the capacitated vehicle routing problem (CVRP) with Google OR-Tools.
What are the OR-Tools of Google?
OR-Tools is an open-source collection of Google with tools for combinatorial optimization.
The objective is to find the best solution out of many possible solutions.
Let us try to use this library to build the optimal routes.
Import Distance Matrix and Init parameters
This matrix and the parameters have been defined in the first section.
How do we calculate distances?
Create functions to calculate distances and order quantities
What’s remaining? The constraints.
Build your model with constraints.
Now that you have built the model, you can run it and export the results.
Show the solution
You can find the full code in this Github repository: Link
💡 Follow me on Medium for more articles related to 🏭 Supply Chain Analytics, 🌳 Sustainability and 🕜 Productivity.
Conclusion
This model can help the centre manager to
- Optimize his fleet with full utilization of his drivers and vehicles
- Ensure that the workload is equally distributed among each driver
We can improve the results!
- What could be the result of higher capacity (boxes) per driver?
- What would the results be if we had a weight or volume constraint?
I will let you test it and share your results (or questions) in the comment area.
What about the sorting centre itself?
Simulate Several Scenarios with Digital Twin
A digital twin is a digital replica of a physical object or system.
A Supply Chain digital twin is a computer model representing various components and processes involved in the supply chain, such as warehouses, transportation networks, and production facilities.
What about the last mile delivery model?
In this specific scenario, we can model the sorting centre (receiving a package from the regional hub) and the last-mile delivery.
Why would we do that?
When brainstorming potential route allocation strategies, you can simulate their impacts on the distribution network.
For example,
- What would the impact be if we increased the storage capacity per delivery vehicle?
- What would impact CO2 emissions if we use vans versus electric bikes?
- What would be the optimal distribution network (locations of your last-mile distribution centres) to minimize the total costs?
A digital twin can answer these questions by running multiple scenarios.
For more information, have a look at the article linked below.
What about the filling rate of trucks?
If we use trucks for last-mile delivery, the question of the loading capacity can create limitations.
Containers Loading Optimization with Python
As we maximize the number of deliveries per driver, we may face issues if our trucks have limited storage capacity.
Let us assume that the picture above represents the loading plan of two similar trucks.
They have been loaded with different strategies
- The container on the left side used an optimized algorithm
- The right one has two pallets on the side that could not be loaded.
How can we avoid being in the situation of the second container?
We can implement an algorithm built with Python using the 2d-knapsack problem to maximise the number of pallets loaded.
This tool would provide the optimal sequence of pallet to maximize the number of pallets loaded.
For more information about the algorithm, check the link below 👇
Have you heard about Generative AI?
Generative AI: GPT x Supply Chain Optimization
Following the trend of Generative AI with large language models (LLMs), I wanted to test this technology on logistic operational issues in the 3PL industry.
I shared this prototype of LangChain Agent, powered by GPT and connected to a TMS.
This agent’s performance is impressive; it can answer operational questions autonomously by querying a database and extracting the results.
What if we create a super agent for Supply Chain Optimization?
The idea would be to equip a GPT agent with optimization models like the one built in this article.
This module could be included to cover the last-mile delivery.
It can be connected to store orders, warehouse operations and demand planning to optimise end-to-end supply chain.
Suppose a world where GPT would support our last-mile delivery centre to optimize its fleet.
For more details,
About Me
Let’s connect on Linkedin and Twitter. I am a Supply Chain Engineer who uses data analytics to improve logistics operations and reduce costs.
For consulting or advice on analytics and sustainable supply chain transformation, feel free to contact me via Logigreen Consulting.
If you are interested in Data Analytics and Supply Chain, look at my website.
💌 New articles straight in your inbox for free: Newsletter
📘 Your complete guide for Supply Chain Analytics: Analytics Cheat Sheet
