The key in tour optimization, as in many other complex problems, is mathematics.
The field of operations research provides many effective algorithms to solve these problems, such as integer linear programming or metaheuristics. This includes tour optimization problems with hundreds of delivery points with many constraints.
In such contexts, finding the mathematical optimum is almost impossible, even with these algorithms. But they can provide excellent solutions, much better than those developed by experienced humans.
A gap between theory and reality
Depending on the context and the time available for the computer to find a good solution, an algorithm can generate routes that are up to 40% more efficient than those provided by a human on indicators such as the number of miles traveled or the number of vehicles used.
In addition to performance gains, algorithms produce routes that are feasible, taking into account constraints such as vehicle capacity, time slots, work schedules, etc. If this is mathematically possible, they will produce routes with virtually no delay at each delivery point, thus greatly improving service quality.
With so many advantages, it seems logical that route optimization software should be the go-to solution for planners at any transport company.
But this is far from being the case.
In our experience, the vast majority of companies whose teams have to make trips that require planning do not use a route optimization solution, there are 4 main reasons for that:
- They have not reached the minimum level of digitalization required to consider implementing it (this is sometimes the case for small businesses)
- They believe that the potential benefits from optimizing their routes (versus manual planning) are not worth it
- They believe that their activity has too many specific constraints to be taken into account by a route optimization software
- They already have implemented it in the past but have been disappointed by the routes generated (often lack of realism or non-applicable in the field)
Well-identified but rarely solved problems.
Mathematical route optimization is an excellent answer to the planning problems we have just described. It has even become essential given the new challenges in the logistics industry, which require a combination of operational performance and reduced environmental impact. As we have seen, many companies that would need it do not use it. Most of the time, it is the way it is implemented that prevents companies from really benefiting from it. Let’s take a look at some of the obstacles to using a route optimization solution:
1 – Low-quality data
One of the first obstacles to the implementation of a route optimization solution is the need for “clean” data to work.
The AI-related saying “garbage in, garbage out” perfectly applies here. Addresses, weights, volumes are data hard to collect and clean. In many cases, addresses are filled in manually, have many errors or are incomplete, making geocoding difficult and distance calculations incorrect. Weights and volumes of goods and packages to be transported are still often declared and not measured, when available.
It is only recently that most companies have reached a sufficient level of digitization for the quality of their data to allow for good route optimization.
2 – Planners have the data in their heads but not in the database
The second problem in route optimization is that some of the data needed for the calculations are not in any database. This can be due to situational data that is only true on a given day or to data that has not been entered in the database (intentionally or not):
- This driver is late this morning and will start the round 1 hour later
- The customer’s store is open all day but prefers to be delivered before the first customers arrive at 9am
- This street is pedestrian-only after 1pm
- This driver wants to finish his round near his home to pick up his son at school
- This driver knows this area very well and is faster than anyone else
- This customer had an argument with a driver and does not want to be delivered by him/her anymore
- And so on.
These few examples show the never-ending complexity that planners and drivers are dealing with every day. The constraints mentioned above must be taken into account in the route optimization for the solution to be realistic but the data is not available anywhere in the database for the algorithm.
3 – Specific business constraints
Many businesses have very specific constraints, for example:
- Furniture delivery requires 2 delivery workers over a certain weight,
- Some interventions require the technicians to go to a PUDO (Pick-Up Drop Off) center to pick up equipment,
- The time spent by a technician at a customer’s home can vary from one to several hours depending on the technical complexity of the intervention,
- In bulk transport, some collection locations can only handle one vehicle at a time
- And so on.
There are as many as constraints as there are businesses.
If these constraints are not taken into account when planning routes, the solutions provided will be neither adapted nor realistic, requiring the user to adjust the provided route by making a large number of manual changes. Adjustments that are likely to compromise the overall performance of the calculated routes…
4 – Dynamic business environment
One of the major problems in route optimization comes from the highly dynamic and changing nature of field operations.
Traffic jams, missing customers, wrong addresses, no parking: the last mile is full of challenges.
While the vast majority of route optimization solutions are static (route calculation and cut-off), the last mile is extremely variable and requires the utmost responsiveness. Routes calculated at a given time are no longer realistic a few minutes later.
In route optimization, there is a wide gap between theory and reality that software publishers’ often have a hard time bridging.
At Kardinal, beyond the algorithms, our main concern is to design a route optimization software for our customers that provides high-performance solutions that are realistic and consistent with their business objectives.
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.