Algorithme d’optimisation hybride pour la résolution de problèmes de planification de trajectoire basé sur l’algorithme d’optimisation du loup gris

Itinéraires plus intelligents dans des villes encombrées

Chaque jour, conducteurs, camionnettes de livraison et robots affrontent le même défi : comment aller de A à B rapidement, en toute sécurité et sans gaspiller de carburant ni de temps ? Cet article présente une nouvelle méthode informatique qui planifie des trajets plus courts et plus fluides à travers des réseaux de rues complexes, saturés d’obstacles et de congestion. En empruntant des idées au mode de chasse du loup gris en meute et aux recherches des prospecteurs d’or, les auteurs montrent comment diriger véhicules et robots plus efficacement dans des environnements urbains denses.

Pourquoi de meilleurs trajets comptent

À mesure que les villes grandissent et que le trafic s’épaissit, même de petites améliorations dans le routage peuvent se traduire par d’importantes économies de temps, d’énergie et de pollution. Les méthodes traditionnelles de recherche de chemin fonctionnent bien lorsque la carte est simple, mais elles ralentissent souvent ou se bloquent quand l’environnement est encombré de nombreux virages et obstacles. Les méthodes « intelligentes » modernes cherchent à imiter la nature — comme les vols d’oiseaux ou les colonies de fourmis — pour explorer plusieurs options à la fois et converger vers de bonnes solutions. L’une de ces méthodes, appelée algorithme d’optimisation du loup gris, est devenue populaire car elle est simple et flexible, mais elle souffre encore de trois problèmes principaux : elle peut se piéger sur des routes sous-optimales, converger trop tôt et ne pas explorer la carte de manière suffisamment exhaustive.

Mêler loups, chaos et prospecteurs d’or

Pour pallier ces faiblesses, les auteurs conçoivent une version améliorée qu’ils appellent CGGWO. Elle conserve l’idée de base d’une meute de loups gris virtuels qui cherchent le meilleur trajet, mais modifie la façon dont la meute se répartit et apprend. D’abord, au lieu de placer les loups à des points de départ aléatoires, la méthode utilise une astuce mathématique appelée cartographie chaotique pour les disperser plus uniformément dans l’espace de recherche. Cela augmente la probabilité qu’au moins certains loups découvrent des régions prometteuses de la carte. Ensuite, la méthode emprunte une règle à une autre technique inspirée des prospecteurs d’or : le loup « alpha » est poussé vers des régions particulièrement riches de l’espace de recherche, à la manière de mineurs qui se déplacent progressivement vers des zones à plus forte teneur en or. Cette étape injecte du hasard contrôlé et de la diversité, aidant la meute à échapper à des choix locaux médiocres.

Croisements astucieux et secousses douces

CGGWO ajoute ensuite deux types de mouvements de « croisement » qui mélangent l’information entre les loups. Dans le mouvement horizontal, deux chemins candidats différents échangent des portions de leur itinéraire, réduisant les angles morts et encourageant la couverture plus complète de la carte. Dans le mouvement vertical, différentes sections au sein d’un même chemin se combinent entre elles, ce qui peut relancer des parties stagnantes de la solution et empêcher la meute de se figer trop tôt sur un trajet défaillant. Enfin, une dose modérée de mutation gaussienne — de petits coups aléatoires guidés par la qualité de chaque loup — maintient l’exploration de la meute. Si le trajet d’un loup est inférieur à la moyenne, il subit une secousse plus forte, ce qui aide l’ensemble du groupe à éviter d’être piégé dans un coin du paysage des solutions.

Mettre la nouvelle méthode à l’épreuve

Les chercheurs testent d’abord CGGWO sur 23 problèmes mathématiques standards largement utilisés pour évaluer les algorithmes de recherche. Ces problèmes vont de paysages lisses avec une seule vallée optimale à des terrains accidentés parsemés de nombreux minima locaux. Sur la plupart de ces tests, CGGWO trouve de meilleures solutions, converge plus rapidement et montre un comportement plus stable que plusieurs concurrents bien connus, y compris la méthode originale du loup gris, l’optimisation par essaim de particules et les algorithmes génétiques. L’équipe applique ensuite la méthode à un problème réaliste de planification de trajet basé sur une grille de rues simplifiée près d’une zone commerciale fréquentée à Lhassa. Les obstacles représentent des tronçons bloqués ou congestionnés, et l’objectif est de relier un point de départ et un point d’arrivée par un itinéraire court et fluide qui les évite.

Trajets plus courts et plus fluides

Dans le test de type trafic, CGGWO produit systématiquement des trajets plus courts avec moins de virages brusques que les autres méthodes tout en nécessitant un temps de calcul modeste. Comparées à l’algorithme original du loup gris et à plusieurs techniques rivales, ses trajectoires planifiées sont plus droites et plus faciles à suivre, réduisant la distance d’environ un quart dans certaines comparaisons. Pour le lecteur non spécialiste, la conclusion est claire : en combinant habilement des idées issues du chaos, de la chasse en groupe et de la prospection aurifère, la nouvelle méthode explore les cartes de manière plus exhaustive et résiste à l’enfermement sur des solutions simplement satisfaisantes. Cela en fait un outil prometteur pour les futurs systèmes de navigation, les robots de livraison et d’autres machines intelligentes qui doivent rapidement trouver des trajets sûrs et efficaces à travers les dédales denses et changeants des villes modernes.

Citation: Cheng, G., Liu, Y. Hybrid optimization algorithm for solving path planning problems based on grey wolf optimization algorithm. Sci Rep 16, 8479 (2026). https://doi.org/10.1038/s41598-026-35037-z

Mots-clés: planification de trajet, algorithme d’optimisation, transport intelligent, intelligence en essaim, navigation robotique