Tournées de livraison : comment les maths ont fait gagner 18 % de kilomètres

Chaque matin, un distributeur régional de produits frais préparait ses tournées à la main. Une personne expérimentée, un tableur, une carte, et une heure et demie de travail avant le départ des camions. Le résultat était correct, mais personne ne savait dire s’il était bon.

On m’a posé une question simple : peut-on faire mieux, et plus vite ?

Mettre le problème en équations

Sur le papier, c’est un grand classique : le problème de tournées de véhicules (VRP, pour Vehicle Routing Problem). En pratique, aucun cas réel ne ressemble au manuel. Ici, il fallait tenir compte de :

• fenêtres horaires : certains clients ne peuvent être livrés qu’entre 6 h et 8 h ;
• capacités : chaque camion a une limite en volume et en poids, et deux d’entre eux sont réfrigérés ;
• contraintes humaines : un chauffeur ne connaît pas le centre-ville, un autre doit être rentré à 13 h le mercredi ;
• habitudes clients : certains commerçants tiennent à voir « leur » livreur.

La première étape a donc été de passer du temps avec l’équipe logistique pour lister ces règles, les classer (obligatoires ou simplement souhaitables) et leur donner un poids.

Choisir la bonne méthode

Pour une cinquantaine de livraisons par jour et six véhicules, trouver la solution optimale n’a pas grand intérêt : les données d’entrée (temps de trajet, volumes) sont elles-mêmes approximatives. Ce qui compte, c’est d’obtenir en quelques secondes une solution très bonne et explicable.

J’ai retenu une approche en deux temps :

1. une heuristique de construction rapide pour obtenir une première solution réaliste ;
2. une recherche locale qui améliore cette solution en échangeant ou en déplaçant des arrêts entre tournées, tant qu’elle trouve un gain.

Les contraintes « souhaitables » sont traitées comme des pénalités : l’algorithme peut les enfreindre, mais seulement si le gain le justifie vraiment.

Les résultats

Après trois semaines de tests en parallèle de la méthode manuelle :

• 18 % de kilomètres en moins en moyenne ;
• une tournée supprimée deux jours par semaine ;
• une préparation qui passe d’1 h 30 à 10 minutes, relecture comprise.

Le plus gros gain n’est pas l’algorithme lui-même, c’est d’avoir rendu explicites des règles qui n’existaient que dans la tête d’une seule personne.

Ce qui a fait la différence

L’outil n’a été adopté que parce que la personne qui faisait les tournées a gardé la main. Elle peut verrouiller un arrêt, forcer un chauffeur, relancer le calcul. L’algorithme propose, l’humain dispose.

Si vous avez un processus qui repose sur un tableur, beaucoup d’expérience et une dose de « on a toujours fait comme ça », il y a de fortes chances qu’un peu de modélisation vous fasse gagner du temps. Parlons-en.