Mathematics and last mile optimization: when theory meets reality
- May 8, 2021
- 2 mins
Cédric Hervet is the Scientific Director of Kardinal, a tech startup that he co-founded in 2015, specialized in software solutions for the transport and logistics industry. Kardinal provides a route optimization software solution based on innovative algorithms and aims at becoming the tech leader in logistics intelligence.
Introduction
Route optimization is a common problem for many companies involved in the transport of goods or people. From parcel delivery to technical maintenance rounds to home care activities, there are many situations where route optimization is the obvious solution to the planning puzzle.
In this article, I’ll try to explain what route optimization techniques are, what the problems are with conventional approaches, and how we, at Kardinal, try to address their weaknesses.
PART I: Route optimization or finding a needle in a haystack
To understand why route optimization is a complex process, try to imagine yourself in front of a schedule where you have 5 available drivers and 100 delivery points to distribute among them, all in the same city. Your objective is obviously to assign the “right” delivery points to the “right” drivers in the “right” order, so that their rounds are “optimized”.
You might intuitively look at the geographical position of the first driver and assign the closest delivery point to him/her first, then the point closest to that point and so on until his/her schedule is full.
Then, you will repeat the same process for the second driver, until all the delivery points are scheduled. If you are lucky enough to have a map showing all the delivery points to visit, the planning could even be relatively quick. A few adjustments if needed and that’s it, your schedule is ready!
So, is that all? A bit of common sense and a map are enough?
Unfortunately not, for two reasons:
- Our example is highly simplified and we have neglected a very important aspect of route optimization: constraints. There is no activity that does not have specific constraints. In our delivery example, these constraints could be: the capacity of the vehicles, the weight and size of the parcels, the delivery time slots to be met, traffic accidents and traffic jams, absent customers who require a second visit of the driver…
- The total number of possible routes is so large that it is almost impossible to find the optimal routes through such a simple process. In fact, there is a good chance that your planning will be inefficient using this method.
You may argue that this is not your job and that an experienced planner would do a better job than you. And you would be right, he or she would indeed do (much) better, but the solution would still be far from ideal. Experts who plan routes manually are tackling one of the most difficult math problems, even for the most powerful computers.
To understand why, imagine a driver who has to make N deliveries, starting from a warehouse and returning to it. Let’s try to count the total number of possible routes. For the first stop, there are N possibilities. For the second choice, there are N-1 possibilities. N-2 for the third, and so on until the end. So the total number of possible rounds is 1 x 2 x 3 x 4 x … x N.
And that’s a lot!
The table below shows the number of possible rounds depending on the number of delivery points to be visited, and roughly how long it would take a normal computer to list all the possible rounds to find the best one:
Number of delivery points
10
15
20
Number of possible rounds
1.31 x 10^12
Calculation time
several hours
2000 years
If a driver makes 25 deliveries in a day, there are as many different routes as there are stars in the universe. We are far from our example with 5 drivers and 100 stops, which was already very simplistic since we neglected all the constraints to be respected in the schedule.
Figuring out the best round, even in simple contexts, is as difficult as finding a tiny needle in a ridiculously large haystack.
It is almost impossible for a human brain and remains a tremendous challenge for the most powerful computers.
About the Author
Cédric Hervet has a PhD in Applied Mathematics and is co-founder of Kardinal. For over 10 years, he has been studying and designing Artificial Intelligence systems for industrial applications in telecommunications, digital marketing and transportation. His dual expertise in statistics/machine learning and algorithms/operational research allows him to bring together these two major sets of techniques to design the intelligent systems of tomorrow.
