Le futur de l’optimisation de tournées est déjà là !

[RAPPORT]
Les différents niveaux d'optimisation de tournées

En dépit de la puissance des algorithmes d’optimisation, les solutions d’optimisation de tournées restent généralement extrêmement limitées dans leur capacité à gérer la plupart des problèmes rencontrés dans la vie de tous les jours par les planificateurs : imprévus, données erronées ou inconnues, contraintes et priorités non exprimables à l’algorithme, etc.

Le point clé ici est que les logiciels d’optimisation de tournées ont hérité de leurs fondations mathématiques une notion purement théorique d’”optimal absolu” qui ne trouve pas véritablement de déclinaison pratique. Dans la réalité, la meilleure décision à un instant donné, si tant est qu’elle existe, peut être fortement challengée quelques minutes plus tard, car de nouvelles informations arrivent, que le temps passe, et que le contexte lui-même évolue.

En conséquence, si l’optimisation de tournées améliore indéniablement l’efficacité des tournées par rapport à une planification manuelle, elle fait perdre à l’utilisateur une grande part de sa réactivité dans la prise de décision. En effet, malgré des performances théoriques souvent impressionnantes sur le papier, ils échouent souvent à véritablement englober la complexité du monde réel, où tout change constamment. De nouveaux standards de qualité de service émergent dans toutes les industries, tels que la livraison/service le jour même ou encore l’interaction en temps réel avec le client final, et rendent les contextes encore plus changeants que par le passé.

C’est pourquoi, même encore aujourd’hui, la plupart des organisations s’appuient sur une planification manuelle, car la réalité à laquelle ils font face est bien trop complexe pour la plupart des logiciels d’optimisation de tournées.

Une optimisation de tournées en continu et adaptée au contexte

Chez Kardinal, nous pensons qu’il est possible de dépasser les limitations présentées précédemment. Pour nous, cela requiert de concevoir l’optimisation de tournées autour des 2 concepts suivants :

  • Optimiser en continu : des événements se produisent en permanence, des décisions sont prises à chaque instant. Un logiciel d’optimisation de tournées doit aider en permanence : avant, pendant et après les tournées.
  • Etre sensible au contexte : sans contexte, les logiciels d’optimisation de tournée se limitent à des recommandations génériques, pas toujours pertinentes, qui font souvent plus de mal que de bien. La sensibilité au contexte est la clé pour prendre les meilleures décisions quel que soit le moment.

Ces deux concepts ne peuvent pas être envisagés séparément. Bien évidemment, concevoir un logiciel d’optimisation de tournées qui ne s’arrête jamais de calculer tout en étant capable d’obtenir et d’utiliser une connaissance structurée du contexte en temps réel est un véritable challenge technique, que ce soit en termes de conception logicielle pure ou sur le plan des algorithmes mathématiques nécessaires à l’exécution de l’ensemble de la chaîne. Mais nous croyons fermement que c’est la seule voie réaliste pour amener l’optimisation de tournées sur le terrain, aux côtés des hommes et des femmes qui font tourner la logistique.

Dans la suite, nous allons montrer comment ces deux concepts se traduisent dans le monde réel en amont des opérations, quand les conducteurs sont sur la route et même après que les tournées soient réalisées.

Solution d'optimisation de tournées en continu

Avant les opérations

Dans la plupart des environnements, les données du problème d’optimisation de tournées ne peuvent jamais être complètement et parfaitement connues à l’avance. Pour les visites d’aides à domicile par exemple, il est impossible de connaître à l’avance avec exactitude qui sont tous les patients qui auront besoin d’une visite dans la journée puisque cette activité, comme beaucoup d’autres, implique de gérer quotidiennement des interventions urgentes.

Dans la livraison de colis express, les ordres de livraison arrivent dans le système d’information en continu et il est impossible d’attendre le dernier moment pour lancer l’optimisation avant de commencer à trier les colis.

Les tournées doivent donc être adaptées en permanence, mais sans faire abstraction du contexte et du timing : on ne peut pas charger la totalité des colis dans un camion quelques minutes avant de partir sans le mettre en retard. Ainsi, les algorithmes d’optimisation doivent être en capacité de “comprendre “ le statut de chaque tournée à l’instant t, pour suggérer les modifications appropriées dont les impacts seront acceptables du point de vue de l’organisation du dépôt.

Pendant les opérations

Une fois que les tournées sont sur le terrain, différents événements peuvent encore se produire. Le premier et le plus important étant, bien sûr, le trafic. Même avec des prévisions de trafic précises, qui seront justes en moyenne, la congestion routière ou la disponibilité des transports publics peuvent évoluer de façon très différentes de ce qui a été anticipé, faisant peser une menace importante sur la qualité de service quand les choses se passent mal, ou ouvrant des opportunités quand elles se passent mieux que prévu. Pendant les opérations, le contexte peut être décrit avec le trafic en temps réel ainsi que les options de mobilité à la disposition de la ressource.

De plus, de nouvelles tâches peuvent devoir être incluses dans des tournées en cours de réalisation, comme de nouveaux enlèvement de colis ajoutés à la volée. Pour les visites à domicile, un aide à domicile mobilisé chez un patient ayant besoin de plus de soins que prévu annulera ses prochaines visites, qui pourront alors être affectées optimalement à d’autres aides à domicile disponibles.

Schéma optimisation de tournées en continu futur optimisation de tournées

Après les opérations

Une fois les tournées terminées, de nouvelles tournées vont bientôt prendre leur place. Cette période de temps devrait être utilisée pour travailler sur la donnée collectée afin d’améliorer le système dans son ensemble. En effet, les durées réelles ont été mesurées : temps de trajet, temps de travail sur site, etc. Elles peuvent varier en fonction d’une grande variété de facteurs, il faut donc acquérir une compréhension de ces variations afin de l’utiliser dans la prochaine optimisation des tournées.

Pour la livraison de colis, il est connu que les chauffeurs sont en général plus rapides dans les zones qu’ils connaissent le mieux. Peut-on quantifier cet effet ? Le type de véhicule utilisé, la séniorité du chauffeur, l’heure de la journée, le niveau de chargement du véhicule, la période de l’année ou encore les conditions météorologiques vont tous avoir un impact sur sa vitesse, au même titre que le type d’environnement dans lequel ils évoluent (des tours de bureaux avec beaucoup d’étages ou des zones pavillonnaires vont impacter fortement le temps de livraison).

Pour les visites à domicile, on peut s’attendre à ce que les aides débutants prennent plus de temps pour faire les soins, du fait de leur moindre expérience. De plus, les patients eux-mêmes peuvent avoir besoin d’un temps variable pour la même prestation. Tous ces paramètres rendent une approche basique allouant X minutes par patient non pertinente en pratique.

Dans les deux cas, des algorithmes de Machine Learning vont apprendre sur l’historique de données afin de comprendre comment tous ces facteurs impactent les durées réelles. Avec le temps, à mesure que la quantité de données stockée augmentera, c’est l’ensemble du système qui gagnera en précision. Un cercle vertueux sera en place, respectueux de la courbe d’apprentissage des Hommes sur le terrain, et qui n’optimisera pas seulement les tournées les unes après les autres, mais qui s’optimisera lui-même avec le temps.

Nous avons tenté de le démontrer, l’optimisation en continu et sensible au contexte est la prochaine étape vers une connexion plus forte entre les processus et les algorithmes. Ce lien renforcé donnera aux organisations une plus grande capacité de réaction et surtout des tournées plus efficaces et plus réalistes permettant de réels gains de performances et un confort de travail pour les équipes terrain.

Partager