Operational Research: Science of the best with less
The development of computer science and applied mathematics has made it possible to model and solve complex optimization problems. This discipline, Operational Research, has met with numerous successes in industry and transport by intelligently exploiting the computational capabilities of increasingly powerful computers to solve combinatorial problems inaccessible to the human mind.
Thus, the scheduling of tasks in a factory, the management of financial assets, the construction of staff schedules became problems that a rational, scientific approach would solve. And among the combinatorial optimization problems that have generated research efforts is the optimization of delivery routes.
Tour optimization: an old problem, always difficult to solve
One of the fundamental problems related to tour optimization is the famous “Problem of the Commercial Traveller”, the first description of which can be found in 1832, which consists in finding the way to visit N points (for example: the customers that a salesperson wishes to meet) that minimizes the distance travelled by the said salesperson.
Formally, this means identifying a Hamiltonian cycle of lower cost in a complete graph with weighting on the arcs. To realize the highly combinatorial aspect of this problem, we can calculate the number of possible tours based on the number of points to visit.
For 3 points, there are 6 possible rounds. For 6 points, there are 720. For every 10, there are already 3,628,800. For 43 points, there are as many as atoms that make up the Earth (about 1050), and for 60 points, there are as many atoms in the Universe (about 1080).
This combinatorial explosion makes it very quickly impossible to explore all the solutions exhaustively: this is where mathematics comes in to imagine algorithms capable of solving in a few minutes what would take centuries for a computer, even a very powerful one, to try all the solutions in order to find the best one.
Vehicle tours: from Mathematics to the Field
For decades, researchers have been working to solve more complex and realistic versions than the rather theoretical version of the Commercial Traveller: tours of several vehicles, with limited carrying capacities, with time slots to be respected, with departures from several depots, etc.
For each of these variants, exact algorithms (slow but capable of providing the best solution to the problem) as well as approximate algorithms (fast to provide good solutions, without any guarantee of optimality) have been designed.
These theoretical and technical advances have been transferred to transport professionals and many software solutions integrating route optimization have been designed to help them, contributing to the improvement of Supply Chain performance.
The last mile and the real time barrier
However, until recently, there was one area where existing algorithms and solutions reached their limits: the last mile and the real-time issues related to it.
Indeed, last mile professionals know that unforeseen events make it very difficult to use delivery route optimization.
Thus, it is necessary to be able to adapt the tours to the context, and this presupposes that the following two conditions are met:
1) The ability to collect information from the field to adapt the tour, and the ability to inform the field of any changes to their routes. 2) The ability to recalculate rounds almost instantaneously to take into account new data received.
The emergence of smartphones, applications and geolocation over the past few years has made it possible to resolve the first point. At Citodi, we solve the second one.> See Citodi Approach