📈 #12 From Pizzerias to Paramedics: How VRP is Transforming Modern Logistics
📈 #12 From Pizzerias to Paramedics: How VRP is Transforming Modern Logistics
Helping businesses saving money and improving customer service by delivering goods and services more quickly and efficiently.
Radikal Bikers, a fast-paced motorcycle popular racing game from the late 90s, was a favorite of mine.
I used to play non-stop.
The goal was to deliver pizzas around the city in a competition with 3 more pizzerias, and along the way you could pick up power-ups to improve your speed or time.
But one question always lingered in my mind: why are 4 different pizzerias competing to deliver exactly the same pizza to the same people? Wouldn't it be more efficient if a single pizzeria delivered multiple orders at once?
This question highlights the potential for inefficiencies in the pizza delivery industry, which is why I'm excited to explore the optimization problem of finding the most efficient way to deliver multiple orders from a single pizzeria.
Today in Feasible, we'll see this problem and learn how it can be solved to save businesses money and improve customer service.
Let's go for it!
🚚 Vehicle Routing Problem, or VRP
The Vehicle Routing Problem (VRP) is a combinatorial optimization problem that asks for the best set of routes for a fleet of vehicles to traverse in order to serve a given set of customers.
The VRP generalizes the Traveling Salesman Problem (TSP), which asks for the shortest route for a single vehicle to visit each of a set of customers exactly once and return to the starting point. If you remember the TSP is because we talked about it some posts ago:
The VRP is a complex problem because it must take into account a number of factors, such as:
The location of customers
The size of orders
The capacity of vehicles
Traffic conditions
Time constraints
The goal of the VRP is to find a set of routes that minimizes the total cost or time of the delivery operation, while satisfying all of the constraints.
It is an important problem to solve because it can help businesses to save money and improve customer service. For example, a delivery company can use the VRP to find the most efficient routes for its delivery drivers. This can help the company to reduce its fuel costs and improve its delivery times. A logistics company can use the VRP to optimize the routes of its trucks. This can help the company to reduce its labor costs and improve its customer service.
The VRP is also important because it is used in a variety of other applications that affects not only businesses but more importantly our society, such as:
Planning the routes of school buses
Routing emergency vehicles
Scheduling public transportation
Planning the delivery of goods to disaster zones
🤔 But it’s pretty difficult to solve
In fact it is a NP-hard problem, which means that there is no known polynomial-time algorithm for solving it.
→ Hey, Borja, I don’t understand anything you said.
I know, we didn’t delve into those terms. No worries, I’ll talk about those in next posts.
The thing is this problem is so difficult that finding the best possible solution to it is only doable for small problems. For bigger ones there are a number of algorithms that can be used to find good solutions in a reasonable amount of time. But we cannot guarantee the best possible one.
If I had to solve it manually, I would go with some ideas like:
Start with an initial solution. For example, I would assign each customer to a random vehicle.
Evaluate the initial solution. This involves calculating the total cost or time of the solution.
Make a small change to the solution. For example, I would swap two customers between vehicles.
Evaluate the new solution.
If the new solution is better than the old solution, accept it. Otherwise, reject it.
Repeat steps 3-5 until I cannot find any better solutions.
Look.
These steps are the usual ones when dealing with algorithms for this problem. Actually, those are the steps for the heuristic algorithm called Iterated Local Search (ILS). The ILS algorithm is a simple and effective heuristic algorithm for solving the VRP.
🔢 Ok so how can I practically solve it?
1️⃣ If you have some coding skills but don’t want to write yourself the algorithms, Google OR-Tools can help you in that quest.
OR-Tools is an easy to use, open-source library that provides a variety of tools for solving optimization problems, including the VRP. You need to know how to define the time/distance matrix and how you can add constraints like the capacity of the vehicle or time windows for the deliveries.
It internally uses a constructive algorithm to find and evaluate an initial solution and then uses a more complex algorithm that you can select. One of them is a variant of the ILS we’ve seen before called Guided Local Search, in which the evaluation function is dynamically modified by penalizing certain solution components.
2️⃣ But if not, there are some options like Nextmv or Nextbillion.ai. Those companies provide simple and convenient API services to solve VRP problems without having to write any code.
You just throw your data and get a solution for your problem, considering several factors like preferred delivery time slots, traffic conditions or even vehicle conditions. And those services usually work like Nextmv describe in their page:
So you have your data about vehicles, orders, locations to serve and business rules, and you get which vehicles are needed to cover those orders minimizing times and/or costs.
3️⃣ And if you want to play with a similar but simpler and graphical tool, you can try VROOM (Vehicle Routing Open-source Optimization Machine).
VROOM is a web-based tool that allows you to solve VRP problems visually. It is easy to use and it is a great way to learn about the VRP.
You can click on the Demo button and then a map of Paris appears. Clicking on different parts of the map will add locations to serve -or you can automatically add several locations clicking on the Add button at the right after creating your first location. Finally, clicking on the left side with those gears you solve the problem and see the solution on the map!
🌎 Are there applications in the real world?
Well, of course there are!
🍣 Food delivery companies like Uber Eats or DoorDash solve the VRP to optimize the routes of their delivery drivers. This helps them to deliver food to customers quickly and efficiently.
🚛 Logistics companies like FedEx or UPS solve the VRP to optimize the routes of their trucks, helping them to deliver packages to customers on time and at a low cost. And we already have seen the UPS example with their ORION project:
Spoiler: UPS saved 50 million dollars the same year it started applying the recommendations done by ORION.
🚑 Emergency services like ambulances and fire trucks use the VRP to optimize the routes of their vehicles. This helps them to get to the scene of emergencies as quickly as possible.
I’ve been involved in a project for the ambulances in Madrid. Since it was an experimental project, we tried to solve the problem with more pure AI techniques rather than the ones we’ve seen in this post. The objective was to make forecast of incidents in Madrid that needed ambulances, and move the ambulances to get to those incidents in an efficient way ensuring that there will always be an ambulance placed near an incident. We used Reinforcement Learning for that and it was pretty funny! You can see it in our github.
✍🏻 Some conclusions
In this post we have seen a lot of things related to delivery services:
The vehicle routing problem (VRP) is a complex problem that involves finding the most efficient way to deliver multiple orders from a single pizzeria.
The VRP is important because it can help businesses to save money and improve customer service.
There are a number of different algorithms that can be used to give solutions to the VRP.
The VRP is used in a variety of real-world applications, such as food delivery, logistics, and emergency services.
I hope that this post helped you scracht the surface of such an important problem in our society 😊
In any case, I would love to read your thoughts in comments!
Talk soon,
Borja.
