Mais qu’est-ce qui ne tourne pas rond avec l’optimisation de tournées ?
- 12 février 2021
- 4 mins
Comme pour beaucoup de problèmes à résolution complexe, les mathématiques sont la clé en optimisation de tournées.
Le domaine de la recherche opérationnelle notamment, fournit de nombreux algorithmes efficaces pour résoudre ces problèmes, comme la programmation linéaire en nombres entiers ou les métaheuristiques. Et ce, y compris pour les problèmes d’optimisation de tournées avec des centaines de points à visiter et de nombreuses contraintes à respecter.
Dans ces contextes, trouver l’optimum mathématique est presque impossible, même avec ces algorithmes. Mais ils sont capables de produire de très bonnes solutions, bien meilleures que celles élaborées manuellement par des humains, rodés à l’exercice.
Un gouffre entre la théorie et la pratique
En fonction du contexte et du temps disponible pour laisser la machine chercher une bonne solution, un algorithme peut produire des tournées jusqu’à 40% plus performantes que celles d’un humain sur des indicateurs tels que le nombre de kilomètres parcourus ou le nombre de véhicules utilisés.
Outre les gains de performance, les algorithmes produisent des tournées dont la faisabilité sera assurée, compte tenu de contraintes telles que : la capacité des véhicules, les créneaux horaires de passage, les horaires de travail, etc. Et si c’est mathématiquement possible, ils produiront des tournées avec un retard théoriquement nul sur chaque point de livraison, améliorant ainsi considérablement la qualité de service.
Avec autant d’avantages, il parait logique que les logiciels d’optimisation de tournées soient l’outil de travail incontournable des planificateurs dans toute entreprise dont l’activité implique des déplacements.
Mais c’est loin d’être le cas.
D’après notre expérience, la grande majorité des sociétés dont les équipes ont à effectuer des déplacements nécessitant une planification n’utilisent pas de solution d’optimisation de tournées, et ce pour 4 raisons principales :
- Elles n’ont pas atteint le niveau de digitalisation minimum requis pour pouvoir envisager de la mettre en œuvre (c’est parfois le cas pour les petites structures)
- Elles estiment que les gains possibles en optimisant leurs tournées (versus une planification manuelle) n’en valent pas la peine
- Elles estiment que leur activité présente des contraintes trop spécifiques pour qu’elles puissent être prises en compte par une solution d’optimisation de tournées
- Elles l’ont déjà mis en œuvre mais ont été déçues par les tournées obtenues (souvent manque de réalisme ou non applicabilité sur le terrain).
Des causes bien identifiées mais rarement solutionnées
1 – La donnée n’est pas de bonne qualité
Un des premiers freins à la mise en place d’une solution d’optimisation de tournées est qu’elle nécessite des données « propres » pour fonctionner.
L’adage “garbage in, garbage out” souvent cité à propos des cas d’usages de l’IA s’applique ici. Les adresses, les poids, les volumes sont des données difficiles à collecter et à nettoyer. Dans de nombreux cas, les adresses sont remplies manuellement, comportent de nombreuses erreurs ou sont incomplètes, ce qui rend le géocodage difficile et les calculs de distances erronés. Les poids et les volumes des marchandises et des colis à transporter sont encore souvent déclarés et non mesurés, lorsqu’ils sont disponibles.
Ce n’est que récemment que la plupart des entreprises ont atteint un niveau de digitalisation suffisant pour que la qualité de leurs données permette d’envisager une bonne optimisation de tournées.
2 – La donnée est dans la tête des planificateurs mais pas dans la base de données
Le deuxième problème en optimisation de tournées est qu’il arrive régulièrement que certaines données nécessaires aux calculs ne se trouvent dans aucune base de données. Il peut s’agir d’informations circonstancielles qui ne sont vraies qu’un jour donné ou de données qui n’ont pas été renseignées en base de données (volontairement ou non) :
- Ce chauffeur est en retard ce matin et commencera sa tournée 1h plus tard
- Le magasin du client est ouvert toute la journée mais il préfère être livré avant que ses premiers clients n’arrivent à 9 heures
- Cette rue est réservée aux piétons après 13 heures
- Ce chauffeur souhaite terminer sa tournée près de chez lui pour aller chercher son fils à l’école
- Ce chauffeur connaît très bien telle zone et y est plus rapide que n’importe qui d’autre
- Ce client a eu une dispute avec un chauffeur et il ne veut plus être livré par lui
- Etc.
Ces quelques exemples illustrent la complexité infinie à laquelle les planificateurs et les chauffeurs sont confrontés chaque jour. Les contraintes suscitées doivent être prises en compte dans l’optimisation de tournées pour que la solution soit réaliste mais la donnée n’est disponible nulle part en base de données pour l’algorithme.
3 – Les contraintes de l’activité sont très spécifiques
De nombreuses activités doivent répondre à des contraintes très spécifiques, comme par exemple :
- La livraison de meubles nécessite 2 livreurs à partir d’un certain poids,
- Certaines interventions nécessitent le passage des techniciens dans un centre PUDO (Pick-Up Drop Off) afin d’y retirer du matériel,
- Le temps passé par un technicien chez un client peut aller du simple au quadruple en fonction de la complexité technique de l’intervention,
- Dans le transport de vrac, certains sites de collecte ne peuvent accueillir qu’un véhicule à la fois
- Etc.
Il en existe autant que de sociétés.
Si ces contraintes ne sont pas prises en compte lors de la planification des tournées, les solutions rendues ne seront ni adaptées, ni réalistes, obligeant l’utilisateur à compléter la planification obtenue d’un grand nombre d’ajustements manuels. Ajustements qui ne manquent pas de dégrader la performance globale des tournées calculées…
4 – Le contexte de l’activité est très dynamique
Un problème majeur en optimisation de tournées provient de la nature ultra-dynamique et changeante des opérations de terrain.
Embouteillage, client absent, adresse erronée, difficulté pour stationner : le dernier kilomètre est semé d’embûches.
Alors qu’une grande majorité de solutions d’optimisation de tournées fonctionne en statique (calculs des tournées puis cutt-off), le dernier kilomètre est quant à lui on ne peut plus dynamique et nécessite une réactivité absolue. Les tournées calculées à un instant T ne sont déjà plus réalistes quelques minutes plus tard.
En optimisation de tournées, il y a un gouffre entre la théorie et la pratique que les solutions des éditeurs ont souvent bien du mal à combler.
Chez Kardinal, au-delà des algorithmes, notre principale préoccupation est de concevoir pour nos clients une solution d’optimisation de tournées capable de mettre sur le terrain des solutions performantes, mais aussi réalistes et en cohérence avec leurs objectifs métier.
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é 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.
