Mathématiques et optimisation du dernier kilomètre : quand la théorie se heurte à la pratique
- 12 février 2021
- 3 mins
Cédric Hervet est le co-fondateur et Chief Product Officer de Kardinal, une startup tech dédiée au secteur du transport et de la logistique qu’il a co-fondée en 2015. Kardinal propose une solution d’optimisation de tournées basée sur des algorithmes innovants et ambitionne de devenir le leader technologique de l’intelligence logistique de ses clients.
Introduction
L’optimisation de tournées est une problématique classique chez de nombreuses entreprises dont l’activité nécessite le déplacement de biens ou de personnes. De la livraison de colis aux tournées de maintenance technique en passant par les activités d’aide et de soins à domicile, il existe de nombreuses situations où l’optimisation de tournées est la solution évidente au casse-tête de la planification.
Dans cet article, je vais tenter de vous expliquer en quoi consistent les techniques d’optimisation de tournées, quels sont les problèmes des approches classiques et comment chez Kardinal, nous essayons de remédier à leurs lacunes.
PARTIE I : Optimiser les tournées ou trouver une aiguille dans un champ de bottes de foin
Intuitivement, vous pourriez regarder la position géographique du premier chauffeur et lui attribuer en premier le point de livraison le plus proche de lui, puis le point le plus proche de ce point et ainsi de suite jusqu’à ce que son planning soit plein.
Ensuite, vous allez réitérer la même procédure pour le 2nd chauffeur, et ce jusqu’à ce que tous les points de livraisons soient planifiés. Si vous êtes assez chanceux pour avoir une carte affichant tous les points de livraison à visiter, la planification pourrait même être relativement rapide. Quelques ajustements si nécessaire et ça y est, votre planning est prêt !
Alors, c’est tout ? Un peu de bon sens et une carte pourraient suffire ?
Malheureusement non. Et ce pour deux raisons :
- Notre exemple est ultra simplifié et nous y avons négligé un paramètre très important en optimisation de tournées : les contraintes. Il n’existe pas d’activité qui ne s’accompagne pas de contraintes spécifiques. Dans notre exemple sur la livraison, ces contraintes pourraient être : la capacité des véhicules, le poids et la taille des colis, les créneaux horaires de livraison à respecter, le trafic et les embouteillages, les clients absents qui nécessitent un deuxième passage du chauffeur…
- Le nombre total de tournées différentes possibles est tellement important qu’il est presque impossible de trouver les tournées optimales via un processus aussi simple. En fait, il y a de fortes chances que votre planification via cette technique soit très sous-optimale.
Vous pouvez objecter que ce n’est pas votre métier et qu’un planificateur expérimenté ferait mieux que vous. Et vous auriez raison, il ferait effectivement (bien) mieux, mais sa solution serait toujours loin de l’optimal. Et pour cause, puisque les experts qui planifient des tournées manuellement s’attaquent à l’un des problèmes les plus difficiles à résoudre d’un point de vue mathématique, même pour les ordinateurs les plus puissants.
Pour comprendre pourquoi, imaginez un chauffeur qui doit réaliser N livraisons, au départ d’un dépôt puis revenir au dépôt. Essayons de compter le nombre total de tournées possibles. Pour le premier arrêt, il y a N choix possibles. Pour le deuxième choix, il y a donc N-1 choix possibles. N-2 pour le troisième, et ainsi de suite jusqu’à la fin. Ainsi, le nombre total de tournées possibles est de 1 x 2 x 3 x 4 x … x N.
Et c’est beaucoup.
Le tableau ci-dessous montre le nombre de tournées possibles en fonction du nombre de points à visiter, et combien de temps il faudrait approximativement à un ordinateur normal pour énumérer toutes les tournées possibles afin de trouver la meilleure :
Nombre de points à visiter
10
15
20
Nombre de tournées possibles
1.31 x 10^12
Temps de calcul
plusieurs heures
2000 ans
C’est presque impossible pour un cerveau humain et reste un défi immense pour les ordinateurs les plus puissants.
L'auteur
Cédric Hervet est le Chief Product Officer de Kardinal, une startup tech dédiée au secteur du transport et de la logistique qu’il a co-fondée en 2015. Docteur en Mathématiques, depuis plus de 10 ans, il étudie et conçoit des systèmes d’Intelligence Artificielle pour des applications industrielles dans les secteurs des télécommunications, du marketing digital et du transport.
