Un nouvel algorithme révolutionne la logistique verte avec les véhicules électriques
Dans le paysage concurrentiel de la logistique moderne, où l’efficacité opérationnelle et la durabilité environnementale sont devenues des piliers incontournables, une percée technologique majeure est en train de redéfinir les règles du jeu. Des chercheurs de l’École d’intelligence artificielle de l’Université d’Anhui, dirigés par Wang Chao, Qin Fang, Liu Rongrong et Jiang Hao, ont mis au point un algorithme de calcul novateur qui promet de transformer radicalement la gestion des flottes de véhicules électriques (VE), en s’attaquant à l’un des défis les plus coriaces de la mobilité urbaine zéro émission : l’optimisation simultanée des itinéraires et des stratégies de recharge.
Le problème, connu dans la communauté scientifique sous le nom de Problème de Routage de Véhicules Électriques (EVRP), est notoirement complexe. Contrairement aux véhicules à moteur thermique, dont la contrainte principale est la capacité de chargement, les véhicules électriques imposent une seconde limitation cruciale : l’autonomie de la batterie. Cela signifie qu’un planificateur de tournée ne peut plus simplement déterminer le chemin le plus efficace pour visiter tous les clients ; il doit également décider avec précision quand, où et pendant combien de temps recharger. Cette double optimisation — de la trajectoire et de l’énergie — fait exploser l’espace des solutions possibles, transformant le EVRP en un problème classé comme NP-difficile. En termes concrets, cela implique que le temps nécessaire pour trouver la solution optimale augmente de façon exponentielle avec le nombre de clients, rendant les méthodes traditionnelles inapplicables pour les opérations réelles impliquant des centaines, voire des milliers de livraisons.
Les approches existantes pour résoudre le EVRP peuvent être regroupées en deux grandes catégories. La première comprend les algorithmes exacts, tels que la programmation linéaire en nombres entiers mixtes. Ces méthodes peuvent garantir la solution optimale, mais leur temps de calcul devient prohibitif pour les problèmes à grande échelle. La seconde catégorie regroupe les algorithmes heuristiques et métaheuristiques, comme le recuit simulé, la recherche tabou, la recherche à voisinage variable (VNS) ou la recherche adaptative à grand voisinage (ALNS). Ces algorithmes parviennent à trouver des solutions satisfaisantes dans un délai raisonnable, mais ils sont vulnérables à un écueil majeur : le piégeage dans des optima locaux. Cela se produit lorsque l’algorithme trouve une solution correcte, mais reste « coincé » dedans, incapable d’explorer d’autres zones de l’espace des solutions qui pourraient contenir une réponse bien meilleure.
Les algorithmes évolutionnaires ont émergé comme une alternative prometteuse, car ils reposent sur une « population » de solutions candidates qui « évoluent » au fil du temps par des processus de sélection, de croisement et de mutation. Leur nature fondée sur une population leur permet d’explorer simultanément plusieurs régions de l’espace des solutions, ce qui réduit considérablement le risque de piégeage dans des optima locaux. Toutefois, même ces méthodes sophistiquées rencontrent des difficultés face à la complexité intrinsèque du EVRP, en particulier lorsqu’il s’agit d’équilibrer la minimisation de la distance totale parcourue, la réduction du nombre de véhicules utilisés et la garantie qu’aucun véhicule ne tombe en panne d’énergie au milieu de sa tournée.
C’est dans ce contexte que le travail de Wang Chao, Qin Fang, Liu Rongrong et Jiang Hao marque une avancée significative. L’équipe de l’Université d’Anhui a proposé un algorithme évolutionnaire coopératif à double population (COEA), une approche qui représente un changement de paradigme dans la manière d’aborder les problèmes d’optimisation complexes. Plutôt que de tenter de résoudre directement le problème intriqué du EVRP, les chercheurs ont adopté une stratégie de « problème auxiliaire ». L’idée centrale est de créer un problème plus simple, mais connexe, qui puisse être résolu rapidement, et d’utiliser la solution de ce problème pour accélérer la résolution du problème principal.
Le problème auxiliaire choisi est une version simplifiée du classique Problème de Routage de Véhicules avec Capacité (CVRP). Le CVRP prend en compte les contraintes de capacité de chargement des véhicules et la nécessité de visiter tous les clients, mais ignore totalement la contrainte d’énergie. En éliminant cette variable, le CVRP devient beaucoup plus facile à résoudre, et sa population de solutions peut converger vers des solutions de haute qualité en un nombre d’itérations bien inférieur.
La véritable ingéniosité de l’algorithme COEA réside dans la manière dont la connaissance est transférée entre ces deux populations : celle du problème simple (CVRP) et celle du problème complexe (EVRP). Un simple échange de solutions serait inefficace, car un itinéraire optimal pour un véhicule thermique ne tient pas compte des bornes de recharge. Pour surmonter cet obstacle, les chercheurs ont mis en œuvre deux innovations fondamentales : une nouvelle méthode de représentation des solutions et un mécanisme de traduction intelligent.
La première innovation est une matrice d’adjacence de distance améliorée. Au lieu de représenter un itinéraire simplement comme une séquence de chiffres (par exemple, 1-3-2-0, où 0 est le dépôt), le COEA utilise une matrice qui code des informations beaucoup plus riches. Chaque cellule de cette matrice ne contient pas seulement la distance physique entre deux points, mais intègre également une valeur relative qui indique l' »affinité » entre eux au sein de la solution. Par exemple, si deux clients sont desservis par le même véhicule, la « distance » entre eux dans cette matrice est artificiellement réduite. S’ils appartiennent à des itinéraires différents, cette « distance » est amplifiée. Ce stratagème permet à la matrice de capturer implicitement la structure de regroupement des clients par véhicule, une information cruciale que peut exploiter un algorithme d’apprentissage pour comprendre la logique sous-jacente à une bonne solution.
La seconde et plus révolutionnaire innovation est l’utilisation d’un auto-encodeur de suppression de bruit (DAE), une technique d’apprentissage automatique. Le DAE agit comme un traducteur entre les deux « langues » des problèmes. Au cours du processus évolutionnaire, les meilleures solutions des deux populations sont converties en leurs représentations matricielles et utilisées pour entraîner le DAE. Le DAE apprend ainsi la cartographie entre la structure d’une solution CVRP (optimale en termes de distance et de capacité) et la manière dont cette même structure pourrait être transformée en une solution EVRP viable (qui tienne également compte des batteries et des stations de recharge).
Une fois entraîné, ce DAE devient un moteur de transfert de connaissance. Il prend les solutions d’élite de la population CVRP, qui a convergé rapidement vers des modèles de regroupement efficaces, et les « traduit » en solutions initiales pour la population EVRP. C’est là l’élément clé : au lieu de commencer la recherche pour le EVRP avec des solutions aléatoires, la population complexe reçoit continuellement des « semences » de haute qualité qui contiennent déjà une logique de regroupement des clients bien optimisée. Cela accélère de manière spectaculaire le processus de convergence, car l’algorithme EVRP n’a pas besoin de perdre du temps à découvrir comment regrouper efficacement les clients ; cette connaissance a déjà été transférée.
Le processus est bidirectionnel. Non seulement des solutions sont transmises du CVRP vers le EVRP, mais aussi des solutions d’élite du EVRP sont renvoyées vers le CVRP. Ce feedback est vital car il oriente l’évolution du problème simple vers des structures qui sont plus utiles et pertinentes pour le problème complexe. C’est un cycle d’amélioration continue, où chaque population aide l’autre à évoluer vers un objectif commun.
Pour valider l’efficacité de leur algorithme, l’équipe de l’Université d’Anhui a mené une série de tests exhaustifs en utilisant un ensemble de tests standard pour le EVRP, comprenant des instances de taille moyenne et grande, avec jusqu’à 400 clients. Ils ont comparé le COEA à cinq des algorithmes les plus performants du moment : BACO, KBEA, HVNS, ALNS et TS-MCWS. Les résultats ont été concluants.
Le COEA a démontré une vitesse de convergence nettement plus rapide. Sur les graphiques représentant le coût moyen de la solution en fonction du nombre d’itérations, la courbe du COEA a chuté beaucoup plus rapidement que celle de ses concurrents, atteignant des solutions de meilleure qualité en moins de temps. En termes de résultats finaux, le COEA a obtenu les meilleures solutions connues dans 11 des 18 instances de test, une performance particulièrement remarquable sur les problèmes à grande échelle, qui sont les plus pertinents pour les opérations logistiques du monde réel.
En comparaison directe, le COEA a systématiquement surpassé BACO, HVNS et TS-MCWS, avec des améliorations du coût total qui ont souvent dépassé 20 %. Même comparé au KBEA, un algorithme évolutionnaire avancé qui utilise des informations historiques de la population pour guider sa recherche, le COEA a obtenu de meilleurs résultats dans la majorité des cas. Cela démontre que la stratégie de transfert de connaissance entre problèmes est plus efficace que les méthodes d’apprentissage intra-population.
Des études d’ablation, dans lesquelles les chercheurs ont désactivé des composants clés du COEA, ont confirmé l’importance de chaque élément de la conception. En supprimant la matrice de distance améliorée, l’algorithme a perdu sa capacité à capturer la structure de regroupement, ce qui a ralenti la convergence. En désactivant le DAE et en le remplaçant par un échange direct de solutions, la performance s’est dégradée sévèrement, confirmant que le mécanisme de traduction est essentiel pour un transfert de connaissance efficace. Ces expériences ont démontré que le COEA n’est pas simplement la somme de ses parties, mais un système intégré où l’interaction entre la représentation de la solution, le DAE et l’évolution coopérative des populations crée un effet synergique.
Les implications pratiques de cette recherche sont profondes. Pour les entreprises de logistique, un algorithme comme le COEA signifie la capacité d’exploiter des flottes de véhicules électriques de manière plus efficace, en réduisant les coûts opérationnels, en prolongeant l’autonomie de leurs véhicules et en améliorant la ponctualité des livraisons. Cela peut faire la différence entre une opération rentable et une autre qui peine à couvrir ses frais.
Pour les villes et les urbanistes, cette technologie offre un outil puissant pour simuler le comportement des flottes électriques et optimiser le positionnement de l’infrastructure de recharge. Plutôt que d’installer des stations de recharge sur la base de simples suppositions, les municipalités peuvent désormais utiliser des modèles comme celui-ci pour prédire avec précision où les points de recharge seront nécessaires, maximisant ainsi leur utilisation et minimisant le coût du réseau.
Au-delà de la logistique, ce travail ouvre une nouvelle voie pour la résolution de problèmes d’optimisation complexes dans divers secteurs. Le concept d’utiliser un problème auxiliaire plus simple pour guider la solution d’un problème plus complexe, facilité par des techniques d’apprentissage automatique, pourrait être appliqué à la planification de réseaux de drones, à la gestion de flottes hybrides ou à l’optimisation de systèmes de transport multimodal.
Dans un contexte où la pression pour atteindre la neutralité carbone est de plus en plus forte, l’intelligence du logiciel qui pilote la logistique verte est aussi importante que la technologie des véhicules. L’algorithme COEA, développé par Wang Chao, Qin Fang, Liu Rongrong et Jiang Hao, n’est pas seulement un progrès technique ; c’est un pas décisif vers un système de transport plus intelligent, plus efficace et véritablement durable.
Un nouvel algorithme révolutionne la logistique verte avec les véhicules électriques
Wang Chao, Qin Fang, Liu Rongrong, Jiang Hao, École d’intelligence artificielle, Université d’Anhui, CAAI Transactions on Intelligent Systems, DOI: 10.11992/tis.202209007