Article · IA & agents
Rendre le routage par clusters praticable à 100 000 nœuds
COMPASS traite le Ordered Clustered TSP comme un problème global de sélection des frontières, plutôt qu'une suite de sous-tournées indépendantes.
Le coût des décisions de frontière
Dans un Ordered Clustered TSP, les nœuds sont répartis en clusters visités dans un ordre imposé. Résoudre chaque cluster séparément puis relier les sous-tours peut produire des frontières incompatibles et enfermer la solution dans un mauvais compromis global.
Une décomposition globale
Ido Greenberg et ses coauteurs proposent COMPASS. La méthode génère des candidats d'entrée et de sortie par cluster, les évalue avec un sous-solveur, puis construit un graphe acyclique dont le plus court chemin choisit une combinaison globale. Un agent de reinforcement learning et une programmation dynamique contribuent à sélectionner et relier les candidats.
Les benchmarks à grande échelle
Les expériences couvrent des instances synthétiques à 10 000 et 100 000 nœuds ainsi qu'un benchmark de commandes Olist à São Paulo. COMPASS obtient les meilleurs coûts dans les benchmarks rapportés et continue de s'améliorer avec le temps, alors que plusieurs méthodes plafonnent. Dans les tableaux, la variante étendue atteint l'écart nul au meilleur connu sur les instances synthétiques 100K et São Paulo 28,5K étudiées.
Limites et statut de la source
Les résultats dépendent de la structure en clusters, des candidats conservés et du sous-solveur. Un écart nul au meilleur connu n'est pas une preuve d'optimalité pour toutes les instances, sauf dans les cas où la construction le permet. Les grands tests utilisent du matériel et des budgets précis ; ils ne constituent pas une garantie de latence sur un autre réseau. Le document est un preprint ArXiv.
Sources
Ido Greenberg, Hugo Linsenmaier, Piotr Sielski, Shie Mannor, Alex Fender, Gal Chechik et Eli Meirom, « COMPASS: Ordered Clustered Routing at 100K Scale », ArXiv 2609.20352v1 : résumé et preprint, PDF.