Green IT for Green Logistics

L’optimisation de feuille de route

Notre société est confrontée au double défi de réduire les émissions de CO2 et la consommation d’énergie, notamment de pétrole.

En 2022, le transport terrestre est à l’origine de 18% du total du CO2 relâché dans l’atmosphère [1]. La Commission Européenne estimait qu’à tout moment, 25% des camions en mouvement roulent à vide. Il y a donc une marge de progression possible au niveau de l’optimisation des transports terrestres, notamment par camion.

Le CETIC développe des algorithmes permettant d’optimiser les feuilles de routes. Les applications sont multiples  :

• optimiser le coût du transport et des livraisons,
• optimiser les feuilles de route des techniciens mobiles, des infirmières à domiciles,
• proposer automatiquement du co-voiturage,
• optimiser les centrales de mobilités,
• etc.

La Figure 1 ci-dessous présente une optimisation de feuilles de route effectuée dans la province de Hainaut. Cette optimisation porte sur un problème type comptant 100 positions géographiques et 10 véhicules ; chaque position doit être atteinte par un véhicule, l’objectif est de minimiser le temps total passé sur la route. L’outil RoutaR est utilisé.

Figure 1. Une optimisation de feuille de route dans le Hainaut effectuée par RoutaR

Les algorithmes d’optimisation de feuille de route nécessitent beaucoup de données

Ces données sont principalement des estimations de temps de trajet et de distance liant les différents points géographiques considérés. Elles sont structurées sous forme de matrice de temps.

En pratique, l’optimisation de feuilles de routes donne de meilleurs résultats sur de plus grands problèmes car cela permet de réaliser plus d’économies d’échelle. Dans l’industrie logistique, on utilise souvent le terme «  massifier » pour exprimer le fait qu’un seul trajet permet d’atteindre efficacement un grand nombre de points géographiques. Il est donc pertinent de s’intéresser à des problèmes de grande taille.

Malheureusement, pour traiter un problème d’optimisation, le nombre de ces estimations de durée à calculer est le carré du nombre de points géographiques. Dans la carte ci-dessus, le problème comporte 100 positions géographiques, donc traiter ce problème a nécessité de calculer 10.000 estimations de temps de trajet.

Algorithmes pour le calcul des données

Pour estimer la durée de trajet entre deux points géographiques, les algorithmes calculent la route la plus rapide pour voyager entre ces deux points à partir d’une carte routière.

Pour ce faire, des algorithmes spécifiques ont été développés ; le plus connu étant l’algorithme de Dijkstra. Il existe des algorithmes nettement plus performants tels les algorithmes de hiérarchie de contraction, avec heuristique A* (A*CH). Pour calculer une route, ou une estimation de durée de trajet d’un point à un autre, ce type d’algorithme est parmi ce qui se fait de mieux en 2023.

Pour calculer un trajet en Belgique, le temps de calcul de A* CH est de 1 à 2 millisecondes pour une implémentation de référence, sur base des cartes routières OSM.

Cet algorithme A*CH est donc extrêmement efficace. Cependant, pour être utilisé pour du routage de véhicules, il doit être exécuté un grand nombre de fois. Dans les benchmarks en annexe, pour 500 points géographiques, il faut compter 5 minutes et pour 1000 il faut compter 30 minutes.

Ces temps de calcul pour générer la matrice de temps sont incompatibles avec une utilisation interactive.

Un algorithme accéléré pour générer des matrices

Le CETIC a donc développé une variante de cet algorithme qui permet de calculer toute une matrice en une seule fois (CH Matriciel). Il s’agit d’une profonde modification de l’algorithme A*CH.

D’après les benchmarks en annexe, pour 500 points géographiques, il faut compter 16 secondes et pour 1000 il faut compter une minute et demie.

Les performances sont présentées dans la figure ci-dessous. Elle affiche les temps de calcul de l’algorithme A*CH et de l’algorithme CH Matriciel sur des problèmes types de taille 100 à 1500.

Et le green IT dans tout ça  ?

En réduisant le temps de calcul sans augmenter le nombre de processeurs, nous avons réduit la consommation d’énergie nécessaire pour générer ces données. Avec un gain de 95% en temps de calcul, le processeur tourne en effet 20 fois moins longtemps pour générer le même résultat.

Il aurait été possible de réduire le temps de calcul en utilisant plus de puissance de calcul. A l’aide de 20 processeurs, on pourrait également obtenir une accélération d’un facteur 20 (plus ou moins). Cependant, cela n’aurait pas réduit la consommation d’énergie, et cela aurait augmenté les besoins hardware pour exécuter l’algorithme.

Conclusion

Grâce à ce nouvel algorithme, et à nos autres développements, nous disposons des outils nécessaires pour fournir un service d’optimisation de routage adaptable, performant et abordable.

La contribution technique présentée dans cet article est donc particulièrement intéressante pour des opérateurs logistiques où les points à atteindre changent souvent (Tracking géographique des véhicules, livraisons, taxis, intervention sur site...). Cette contribution leur permettra d’optimiser leurs itinéraires de la manière la plus efficace, en prenant en compte plusieurs contraintes, mais pas que, en maîtrisant aussi leur empreinte écologique, et en augmentant leur flexibilité et agilité face à toute nouvelle demande ou changement.

L’innovation sujet de cet article peut être complétée par d’autres solutions technologiques comme le tracking et suivi des opérations sur le terrain, ainsi que leurs performances en collectant les KPI les plus pertinents.

L’étape suivante de ce travail consiste à augmenter la maturité de la contribution et à l’intégrer dans RoutaR pour se donner les moyens d’une logistique plus verte. D’autre part, qui sait, peut-être y a-t-il déjà des idées chez nos chercheurs pour encore accélérer cet algorithme...

Annexe : données détaillées du benchmark

Il agit d’une seule exécution, pas une moyenne, sur un ordinateur relativement standard en 2023 Intel(R) i7-8750H@2.20GHz pourvu de 16Gb de mémoire RAM. Les points géographiques sont répartis sur le territoire Wallon et la carte utilisée et la carte OSM de la Belgique.

Nous observons que l’algorithme CH Matriciel est nettement plus rapide que A*CH, de l’ordre de 20 fois plus rapide. Il y a un léger ralentissement relatif de l’algorithme à partir de 1400 points géographiques (le gain passe de 95% à 91%) à cause d’une saturation de la mémoire RAM disponible car l’algorithme CH Matriciel est fort gourmand en mémoire RAM.