Une percée algorithmique pour les flottes électriques
L’industrie de la logistique se trouve à un carrefour décisif. Alors que les entreprises du monde entier s’engagent dans une transition massive vers les véhicules électriques (VE) pour réduire leur empreinte carbone et répondre aux exigences réglementaires, un défi opérationnel majeur persiste : comment optimiser les itinéraires d’une flotte de VE de manière à maximiser l’efficacité énergétique tout en garantissant la ponctualité des livraisons ? Contrairement aux camions à moteur thermique, les véhicules électriques doivent naviguer un équilibre délicat entre la charge utile, la distance à parcourir et la capacité de la batterie. Un arrêt de recharge mal placé ou un itinéraire trop long peuvent mener à une panne sèche, paralysant une partie de la chaîne d’approvisionnement. Ce problème, connu sous le nom de Problème de Routage de Véhicules Électriques (EVRP), est un casse-tête mathématique de grande complexité, classé NP-difficile, qui a longtemps ralenti les progrès vers une logistique véritablement verte.
Une équipe de chercheurs de l’Université de l’Anhui, en Chine, vient de proposer une solution qui pourrait bien révolutionner la planification des flottes. Leur nouvel algorithme, publié dans la revue scientifique CAAI Transactions on Intelligent Systems, promet de surmonter ces obstacles en offrant une méthode pour calculer des itinéraires pour des flottes électriques qui sont non seulement plus efficaces, mais aussi beaucoup plus rapides à déterminer. Le cœur de leur innovation réside dans une approche élégante et puissante : un algorithme de co-évolution à double population qui décompose le problème en deux parties interconnectées, permettant à chacune d’aider l’autre à trouver la solution optimale plus rapidement.
L’intuition fondamentale de Chao Wang et de son équipe est que la meilleure façon de résoudre un problème extrêmement complexe est de ne pas l’attaquer directement. L’EVRP, avec sa nécessité d’optimiser simultanément l’ordre de visite des clients et la planification des arrêts de recharge, crée un espace de recherche énorme et rempli de pièges. Les algorithmes traditionnels, qu’il s’agisse de méthodes exactes comme le branch-and-bound ou d’heuristiques avancées comme la Recherche Adaptative à Grand Voisinage (ALNS), échouent souvent. Les méthodes exactes deviennent impraticables pour des problèmes de grande taille, tandis que les heuristiques risquent de se bloquer dans des solutions sous-optimales, surtout si elles partent d’un point défavorable.
L’approche proposée par l’équipe de l’Université de l’Anhui introduit une stratégie de « diviser pour mieux régner ». Ils créent un problème auxiliaire, beaucoup plus simple, appelé Problème de Routage de Véhicules Capacités (CVRP). Ce problème ignore complètement les préoccupations liées à la batterie et se concentre uniquement sur la capacité de chargement du véhicule et la distance. Les stations de recharge sont traitées simplement comme des points neutres à visiter, sans aucun service requis. Ce CVRP simplifié est beaucoup plus facile à résoudre, et sa population de solutions converge rapidement vers des itinéraires qui optimisent la distance et l’affectation des véhicules.
Cependant, une solution CVRP, aussi efficace soit-elle, est inutile pour un véhicule électrique si elle ne tient pas compte de l’autonomie. Le véritable génie du nouvel algorithme, baptisé COEA (Algorithme de Co-évolution à Double Population), réside dans la manière dont il transfère la valeur de la solution CVRP dans le monde réel de l’EVRP. Les deux problèmes sont hétérogènes ; une solution pour l’un ne peut pas être simplement copiée dans l’autre. Pour surmonter cet écart, les chercheurs ont développé un pont intelligent basé sur une représentation innovante de la solution.
Ils ont introduit une « matrice d’adjacence des distances améliorée ». Il ne s’agit pas simplement d’un tableau des distances entre les points. C’est un code sophistiqué qui intègre des informations critiques sur la structure même de la solution. Au-delà de la distance géographique réelle, la matrice code également quels clients sont desservis par le même véhicule. Ils y parviennent en manipulant les valeurs de distance : les distances entre les clients appartenant au même itinéraire sont artificiellement réduites, tandis que celles entre les clients d’itinéraires différents sont amplifiées. Cela crée une « carte invisible » qui regroupe ensemble les clients d’un véhicule et éloigne les groupes d’autres véhicules. De cette façon, la matrice devient un langage commun qui peut être compris à la fois par le problème CVRP simple et par le problème EVRP complexe.
Avec cette représentation unifiée en place, le transfert de savoir devient possible. C’est là qu’intervient un outil de l’apprentissage automatique : l’auto-encodeur de débruitage (DAE). Ce modèle neuronal est entraîné pour apprendre la relation de transformation entre les représentations matricielles des solutions CVRP et EVRP. Pendant le processus évolutif, les meilleures solutions (les « élites ») de chaque population sont converties dans leur forme matricielle. Le DAE, qui a été entraîné avec des paires de solutions des deux problèmes, agit comme un traducteur, transformant la matrice d’une solution CVRP en une qui soit cohérente avec le domaine EVRP, et vice-versa.
Ce processus de migration bidirectionnelle est le moteur de la co-évolution. Les solutions élites de la population CVRP, qui sont déjà optimales en termes de distance et d’affectation des véhicules, sont traduites dans le domaine EVRP et insérées comme nouveaux descendants. Cela injecte dans la population EVRP un flux constant de squelettes d’itinéraires bien structurés, accélérant énormément sa recherche d’une solution réalisable. En même temps, les meilleures solutions de la population EVRP, qui ont déjà résolu les défis de la recharge et de la consommation d’énergie, sont traduites de nouveau dans le CVRP et introduites dans cette population. Cela oriente la population CVRP vers des itinéraires qui ne sont pas seulement courts, mais qui sont aussi intrinsèquement compatibles avec les réalités opérationnelles des véhicules électriques, comme la proximité des stations de recharge.
Ce cycle de rétroaction positive crée un système dynamique où les deux populations s’améliorent mutuellement. La population CVRP, qui converge plus rapidement, pousse la convergence de la population EVRP. En retour, la population EVRP, en fournissant des solutions qui intègrent des contraintes énergétiques, enrichit l’espace de recherche de la population CVRP. Le résultat est un algorithme qui non seulement trouve des solutions de meilleure qualité, mais le fait à une vitesse significativement supérieure à celle de ses prédécesseurs.
La validité de cette approche, appelée Algorithme de Co-évolution à Double Population (COEA), a été démontrée par des tests exhaustifs sur des ensembles de données de référence standard pour l’EVRP. Ces ensembles comprennent des problèmes de taille moyenne avec 200 clients et des problèmes de grande envergure avec 400 clients, simulant des scénarios urbains denses et complexes. Le COEA a été comparé à cinq des algorithmes les plus avancés de l’état de l’art, incluant à la fois des heuristiques et d’autres algorithmes évolutionnaires.
Les résultats ont été concluants. Dans 11 des 18 cas de test, le COEA a obtenu la distance de trajet la plus courte jamais enregistrée pour ces instances spécifiques. Ce qui est encore plus important, cet avantage n’est pas venu au détriment d’un plus grand nombre de véhicules. En effet, dans plusieurs cas, le COEA a obtenu des itinéraires plus courts en utilisant le même nombre, voire moins, de véhicules que les algorithmes concurrents. Dans la logistique, où chaque véhicule représente un coût significatif en termes de capital, d’entretien et de personnel, cette efficacité dans l’utilisation de la flotte est aussi cruciale que la réduction de la distance.
L’analyse de la vitesse de convergence a révélé un autre avantage clé. En traçant la progression de l’algorithme génération après génération, le COEA a montré une courbe d’amélioration beaucoup plus raide. Il a surpassé les performances finales de certains de ses concurrents dans les premières phases du processus d’optimisation. Cette rapidité est fondamentale pour les applications du monde réel, où les décisions de planification doivent être prises en minutes, pas en heures, pour s’adapter aux changements de trafic, aux commandes de dernière minute ou aux pannes d’infrastructure.
Pour isoler l’impact de ses composants clés, l’équipe a mené des études d’ablation. Ils ont désactivé la matrice de distance améliorée ou l’auto-encodeur de débruitage, créant des versions affaiblies de l’algorithme. Dans tous les cas, les performances de l’algorithme se sont considérablement dégradées. Cela a démontré que le succès du COEA ne dépend pas d’un seul élément, mais de la synergie parfaite entre la représentation intelligente du problème et l’apprentissage du transfert.
Du point de vue industriel, les implications sont profondes. Des entreprises de logistique mondiales comme DHL, Amazon et FedEx s’engagent dans l’électrification de leurs flottes, poussées par des réglementations environnementales et la pression des consommateurs. Cependant, la peur d’une baisse d’efficacité et d’une augmentation des coûts opérationnels a été un obstacle. Le COEA offre une solution concrète à cette crainte. En fournissant des plans d’itinéraire qui sont à la fois plus courts et plus respectueux de la batterie, l’algorithme permet à ces entreprises de maximiser la productivité de leurs véhicules électriques, de réduire le temps d’immobilisation pour la recharge et, en fin de compte, d’accélérer le retour sur investissement de leur flotte verte.
Au-delà de l’efficacité immédiate, l’algorithme aborde également un problème critique de résilience. Un plan d’itinéraire qui ne tient pas adéquatement compte de l’état de charge peut conduire un véhicule à être immobilisé en plein milieu de sa route, causant des retards massifs et des opérations de sauvetage coûteuses. Le COEA, en intégrant intrinsèquement les contraintes d’énergie dans son processus de recherche, produit des solutions qui sont robustes et fiables, minimisant ainsi le risque de dysfonctionnements opérationnels.
Ce travail représente également un changement de paradigme dans la façon dont les problèmes d’optimisation complexes sont abordés. Plutôt que de dépendre uniquement de la force brute informatique ou d’heuristiques ad hoc, il combine la puissance des algorithmes évolutionnaires avec les capacités de reconnaissance de motifs de l’apprentissage automatique. Le DAE ne remplace pas l’algorithme évolutionnaire ; au contraire, il agit comme un facilitateur, permettant au savoir de circuler entre des domaines de problèmes. Cette fusion de techniques traditionnelles et modernes est un exemple de la prochaine génération d’intelligence artificielle appliquée, où l’expertise humaine en modélisation des problèmes se combine avec la capacité des machines à apprendre et à généraliser.
Le choix de la matrice de distance améliorée reflète également un engagement envers la transparence et la solidité technique. Cette représentation n’est pas une « boîte noire » apprise entièrement par un réseau neuronal. Il s’agit d’un modèle conçu par des experts qui intègre des connaissances explicites du domaine sur la façon dont les clients sont regroupés et les véhicules affectés. Cette approche basée sur des principes satisfait les critères de EEAT (Expérience, Expertise, Autorité, Fiabilité), démontrant une compréhension profonde du problème sous-jacent et une méthodologie rigoureuse.
L’avenir de cette technologie est prometteur. Le cadre de co-évolution à double population est hautement adaptable. Il peut être facilement étendu à des variantes plus complexes de l’EVRP, comme des véhicules avec différents niveaux d’autonomie, des stations de recharge avec des vitesses de charge variables, ou la nécessité de respecter des fenêtres de temps strictes pour les livraisons. L’intégration avec des jumeaux numériques de réseaux de transport urbain pourrait permettre des simulations en temps réel, permettant une planification prédictive qui anticipe la congestion et optimise la recharge de manière dynamique.
En résumé, l’algorithme développé par l’équipe de l’Université de l’Anhui n’est pas seulement une avancée technique ; c’est un catalyseur pour une logistique durable. En résolvant le problème de l’EVRP avec une efficacité et une rapidité sans précédent, il fournit à l’industrie un outil puissant pour rendre l’électrification des flottes non seulement une aspiration écologique, mais aussi une réalité économique et opérationnelle. Alors que le monde se dirige vers un avenir à zéro émission, des innovations comme celle-ci seront fondamentales pour maintenir le flux constant de biens qui soutient nos économies, le tout avec une empreinte carbone de plus en plus petite.
Une percée algorithmique pour les flottes électriques
Chao Wang, Fang Qin, Rongrong Liu, Hao Jiang, School of Artificial Intelligence, Anhui University
CAAI Transactions on Intelligent Systems, DOI: 10.11992/tis.202209007