Résolution du problème multi-véhicules multi-dépôts à boucles fermées par k-means++ hiérarchique et réseaux neuronaux combinatoires

Des itinéraires plus intelligents pour de nombreux conducteurs

Des fourgons postaux aux drones de livraison en passant par des convois de secours, les planificateurs font souvent face à une énigme : comment plusieurs véhicules partant de points différents peuvent-ils se partager la visite de centaines ou de milliers d’arrêts sans gaspiller carburant ou temps ? Cet article présente une nouvelle façon de diviser et résoudre ce problème, combinant une astuce classique de clustering avec un réseau neuronal moderne, permettant aux ordinateurs de tracer des itinéraires efficaces en quelques secondes au lieu de minutes ou d’heures.

Le défi des nombreux dépôts et conducteurs

L’étude s’attaque à une version exigeante du célèbre problème du voyageur de commerce, où au lieu d’un seul voyageur il y en a plusieurs, chacun partant et revenant à sa base propre. Ensemble, ils doivent visiter chaque ville exactement une fois tout en minimisant la distance totale. Ce scénario reflète des tâches comme la coordination de flottes de camions, des groupes de robots ou des drones aériens partageant le travail sur une région. Comme le nombre de combinaisons d’itinéraires possibles explose avec la croissance des villes et des conducteurs, les méthodes exactes deviennent trop lentes, et les méthodes classiques d’essai-erreur peinent souvent ou doivent sacrifier la qualité de la solution pour la rapidité.

Limites de la recherche classique et du simple découpage

Pendant des années, les ingénieurs ont recours à des « métaheuristiques » telles que les algorithmes génétiques, la recherche par colonies de fourmis ou les essaims de particules. Elles imitent des processus naturels pour explorer de nombreux itinéraires candidats et les améliorer progressivement. Flexibles, elles présentent cependant deux inconvénients majeurs : elles ne garantissent pas la qualité de la solution et peuvent être très lentes sur de grandes cartes, surtout quand chaque nouvelle instance nécessite de relancer la recherche. Un accélérateur courant consiste à regrouper d’abord les villes en régions avec des outils comme k-means, puis à résoudre un sous-problème plus petit dans chaque cluster. Bien que cette stratégie de découper-puis-résoudre aide, la qualité finale reste limitée par la méthode de recherche sous-jacente, et viser de meilleurs itinéraires signifie généralement accepter des temps de calcul encore plus longs.

Apprendre à un réseau à tracer des routes, puis l’aider à échelle

Ces dernières années ont vu émerger une idée différente : entraîner un réseau neuronal à produire directement de bons itinéraires. Après apprentissage sur de nombreux exemples de dispositions de villes, un tel réseau peut proposer un tour complet en une seule passe avant, un peu comme un modèle de langage écrit une phrase. Ces solveurs neuronaux fonctionnent remarquablement bien sur des problèmes à conducteur unique et de taille modeste, mais ils peinent quand il s’agit de coordonner plusieurs conducteurs ou quand l’ensemble de villes est bien plus grand que ce sur quoi ils ont été entraînés. Le mouvement clé des auteurs est d’encapsuler ce solveur neuronal dans un processus en deux étapes qui transforme une tâche multi-conducteurs massive en nombreux sous-problèmes plus petits et familiers que le réseau peut gérer confortablement.

Comment fonctionne la méthode en deux phases

La méthode proposée, appelée KHC-NCN, commence par utiliser une version améliorée du clustering k-means pour assigner les villes aux différents dépôts et conducteurs. Si une région résultante contient trop de villes pour que le solveur neuronal la gère de manière fiable, la méthode la scinde automatiquement en morceaux plus petits, chacun ayant une taille proche de celles rencontrées lors de l’entraînement du réseau. Les coordonnées de chaque morceau sont ensuite mises à l’échelle dans un carré standard afin qu’elles ressemblent encore davantage aux données d’entraînement. Le réseau neuronal produit alors un itinéraire pour chaque petit morceau. Enfin, une étape de fusion assemble ces sous-itinéraires en une seule boucle pour chaque conducteur, en utilisant des règles géométriques simples pour connecter les morceaux en ajoutant le moins de distance supplémentaire possible.

Vitesse et qualité sur des cartes de référence réelles

Les auteurs testent leur méthode sur un large ensemble de cartes standard issues d’un benchmark public largement utilisé en recherche sur le routage. Ils la comparent à de nombreuses techniques de recherche établies ainsi qu’à un solveur artisanal de premier plan et à une autre approche neuronale. Sur 44 cas de test de tailles et nombres de conducteurs variés, leur méthode trouve des trajets totaux plus courts dans près des trois quarts des cas tout en étant nettement plus rapide, souvent par ordres de grandeur. Elle tient particulièrement bien la route lorsque le nombre de villes atteint des centaines ou des milliers, situations où de nombreuses approches classiques ralentissent ou fournissent des itinéraires moins bons.

Ce que cela signifie pour le routage dans le monde réel

En termes simples, l’étude montre que laisser un réseau neuronal rapide traiter de nombreux petits problèmes bien formés peut être plus efficace que de passer beaucoup de temps sur un seul problème énorme. En regroupant les villes selon la zone de confort du réseau, puis en combinant habilement les réponses partielles, la méthode fournit des itinéraires à la fois courts et rapides à calculer. Pour des applications comme la logistique, la planification multi-robots et les interventions d’urgence, cela offre une voie pratique vers des plans de route quasi-temps réel qui améliorent l’utilisation des véhicules et l’efficacité énergétique par rapport à beaucoup d’outils existants.

Citation: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Mots-clés: routage de véhicules, réseaux neuronaux, clustering, optimisation, logistique