Mathématiques et optimisation du dernier kilomètre : quand la théorie se heurte à la pratique

Pas le temps de lire maintenant ? Recevez cet article en pdf dans votre boîte email  

Cédric Hervet est le Directeur Scientifique 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

Pour comprendre pourquoi l’optimisation de tournées est une problématique complexe, essayez de vous imaginer devant un planning où vous avez 5 chauffeurs disponibles et 100 points de livraison à répartir entre eux, tous dans la même ville. Votre objectif est évidemment d’attribuer les “bons” points de livraisons aux “bons” chauffeurs dans le “bon” ordre, afin que leurs itinéraires soient “optimisés”.
Plan de Paris Mathématiques et optimisation Mathematics last mile optimization

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 :

  1. 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…
  2. 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

3 628 800

1.31 x 10^12

2.43 x 10^18

Temps de calcul

< 1 sec

plusieurs heures

2000 ans

Pour réaliser 25 livraisons par 1 seul chauffeur (ce qui est très fréquent sur une journée), il y a autant de tournées différentes possibles qu’il y a de grains de sable sur Terre. Et nous sommes loin de notre exemple avec 5 chauffeurs et 100 arrêts, qui était déjà lui-même très réducteur puisque nous négligions toutes les contraintes à respecter dans la planification.
Bottes de foin dans un champ Mathématiques et optimisation Mathematics last mile optimization
Trouver la meilleure planification de tournée, même dans des contextes simples, est aussi difficile que de trouver une minuscule aiguille dans une botte de foin monstrueusement vaste. 

C’est presque impossible pour un cerveau humain et reste un défi immense pour les ordinateurs les plus puissants.

Cédric Hervet Kardinal optimisation de tournées pertinente optimize your route what's wrong with route optimization tourne pas rond avec l'optimisation

L'auteur

Cédric Hervet est le Directeur Scientifique 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.