La prise en compte du trafic en amont de l’optimisation de tournées : ce petit rien qui change tout
- 20 février 2021
- 4 mins
[CAS D'ETUDE]
Prise en compte des données trafic en optimisation de tournées
Au sein de la chaîne logistique, le dernier kilomètre est celui de tous les défis : à lui seul, il représente 30% de la circulation des centres urbains, 25% des émissions de CO2 et 20% du coût total de la livraison.
L’optimisation de tournées, en diminuant les coûts par l’optimisation des ressources et la diminution des kilomètres parcourus, se positionne comme une réponse de choix à ces enjeux.
Le caractère changeant du dernier kilomètre le rend toutefois difficile à optimiser : le trafic et ses variations rendent en effet complexe le respect des engagements pris par les transporteurs auprès de leurs clients (respect des créneaux horaires par exemple).
Comment les solutions intègrent elles le trafic dans leur optimisation de tournées ? Quelles conséquences ont le fait de prendre en compte le trafic en amont versus en aval des optimisations ? Découvrez les réponses de notre Directeur Scientifique, Cédric Hervet, sur ce petit détail qui change tout !
Quelle est la méthode classique de prise en compte du trafic dans l’optimisation de tournées ?
Pour fonctionner, les algorithmes d’optimisation basent leurs calculs sur ce qu’on appelle une « matrice de distance ». Ce sont les données qui permettent de savoir quelle est la durée et la distance entre chaque paire de point à optimiser, dans un sens et dans l’autre. L’algorithme d’optimisation va donc chercher à obtenir les tournées qui permettent de minimiser la distance parcourue et/ou le temps de trajet. Or, la matrice de distance ne dépend pas du temps dans les modèles d’optimisation de tournées classiques. Cela implique que l’estimation de durée et/ou de distance entre deux points est unique, quelle que soit l’heure de démarrage du trajet.
C’est seulement une fois que les tournées sont optimisées que le calcul de l’ETA est affiné en tenant compte du trafic prédictif à chaque étape de la tournée.
Afin d’anticiper que le trafic réel va sans doute augmenter les durées de trajet, des correctifs sous la forme de coefficients (plus ou moins raffinés) sont appliqué sur la matrice de distance afin d’obtenir des solutions plus réalistes. Mais même dans ce cas, la matrice ne dépend pas du temps puisque la durée entre chaque point reste la même tout au long de la journée.
Pourquoi cela n’est pas optimal ? Quel problème cela pose-t-il ?
Du point de vue de l’optimisation, la non prise en compte du trafic en amont des calculs de tournées est un problème car en réalité, le trafic a un impact fort, surtout en zone urbaine, tout au long de la journée. En effet, chacun a pu faire l’expérience des bouchons du matin et du soir. Sur une même journée, la durée de trajet entre deux points peut varier du simple au quadruple dans certains cas. Mais si certains trajets vont connaître une forte congestion à certains moments de la journée, il se peut que d’autres subissent beaucoup moins les effets du trafic, ou à des moments différents !
Ainsi, en permettant à l’algorithme d’optimisation d’avoir connaissance des évolutions de trafic pour chaque paire de points en amont de l’optimisation, cela lui permet de réaliser certains trajets à des moments opportuns et ainsi d’éviter purement et simplement certains trajets congestionnés à certains moments de la journée. En calculant a posteriori l’impact du trafic sur la tournée, on ne peut pas anticiper ces variations dans la planification et on peut donc se retrouver avec des tournées qui vont rencontrer beaucoup de bouchons, être en retard sur certaines livraisons, et donc être peu performantes au final.
Quelle est la complexité sous-jacente à la prise en compte du trafic en amont de l’optimisation ?
Si l’on souhaite travailler sur une estimation réaliste de l’impact du trafic sur les durées des trajets, on ne peut pas considérer que cet impact est le même à chaque instant et à chaque endroit.
Idéalement, il faudrait donc connaître à l’avance, pour chaque paire de points à planifier, et à chaque moment de la journée (par exemple toutes les 10 minutes sur une journée de travail de 8 heures, soit 48 instants). Sur un problème de taille raisonnable, où il faut planifier 500 points, cela représente 250 000 trajets possibles à connaître sur les 48 instants de la journée, soit 12 millions de trajets, ce qui peut représenter plusieurs heures de calcul pour un distancier, voire plusieurs jours sur les problématiques à 5000 – 10 000 points.
Une telle approche est inenvisageable en pratique, car elle signifierait qu’il faut attendre plusieurs heures avant de commencer la moindre optimisation, ce qui est en contradiction forte avec les besoins d’optimisation temps réel propre au dernier kilomètre. La question qui se pose alors est la suivante : comment fournir des prédictions de trafic réalistes, qui tiennent compte des particularités de chaque trajet et du moment de la journée, sans augmenter le temps de calcul lors de l’optimisation des tournées ?
Solution d'optimisation de tournées en continu
Comment fonctionne l’optimisation de tournées Kardinal de ce point de vue-là ? Avec quels bénéfices ?
Parce que nous destinons notre solution d’optimisation aux applications les plus exigeantes en termes de dernier kilomètre urbain, nous avons mis beaucoup d’efforts dans la conception d’un système d’optimisation qui tienne véritablement compte du trafic.
Nos docteurs en Mathématiques Appliquées ont mis en place un système d’Intelligence Artificielle capable de collecter et d’agréger des données prédictives de trafic à grande échelle nous permettant ainsi d’estimer, en amont de l’optimisation, à chaque instant et pour chaque trajet quelle sera la durée de ce trajet, avec un temps de calcul quasiment identique à une approche sans trafic.
Très concrètement, cela signifie que nous savons à l’avance quelle sera la durée du trajet avec trafic entre deux points A et B à 10h un mardi. Le modèle prédictif du trafic est ici spécifique à ce trajet A -> B, à cette journée et à cette heure. Ainsi nous ne prédirons pas le même impact trafic pour un trajet A vers C à 10h un mardi, ou pour un trajet A vers B à 16h un vendredi. Nos algorithmes de Machine Learning rafraîchissent quotidiennement ces données pour offrir à nos clients des tournées réalistes.
Exemple d’une courbe d’évolution de trafic entre 2 communes au Nord de Grenoble sur une portion très congestionnée de l’A49
Le modèle est ici calibré pour un Mardi mais il serait différent pour un autre jour de la semaine. Nous rafraichissons les modèles toutes les deux semaines de façon automatique pour tenir compte des évolutions, travaux ou situation exceptionnelle (Covid-19, par exemple).
Sur cet itinéraire, le temps de trajet sans trafic est de l’ordre de 15 minutes. Or en pratique, cet axe (l’A49) est très souvent congestionné et rend la circulation difficile, notamment pour les camions. Ainsi, on peut voir que le temps de trajet sur la journée se situe toujours entre 27 et 29 minutes, avec deux légers pics qui correspondent aux périodes de plus forte affluence de la journée.
Exemple d’une courbe d’évolution de trafic entre le Nord et le Sud de Grenoble, qui emprunte le périphérique :
Ces deux exemples démontrent qu’on peut capter les évolutions de trafic de façon différenciées pour deux trajets et ainsi attraper les spécificités « trafic » du réseau routier dans le temps.
Nos algorithmes d’optimisation de tournées sont nativement conçus pour travailler sur la base de matrices de distances dépendantes du temps. Cela leur permet de construire des tournées qui évitent si nécessaire les axes congestionnés aux heures de pointes et qui profitent des heures creuses pour livrer les zones très urbaines quand c’est possible. Nos utilisateurs bénéficient ainsi de tournées plus performantes et plus fiables car plus réalistes.
