🤖 AI

Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation

Ce document présente EvoReal, un cadre qui exploite la synthèse évolutive guidée par les LLM pour générer des instances d'entraînement structurellement réalistes et adapter progressivement les solveurs neuronaux, réduisant ainsi considérablement l'écart de généralisation entre les données synthétiques et les benchmarks de routage du monde réel tels que TSPLib et CVRPLib.

Auteurs originaux : Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

Publié 2026-01-30

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le gros problème : Les « roues stabilisatrices » vs la « vraie route »

Imaginez que vous enseigniez à un robot à devenir le meilleur chauffeur de livraison au monde.

La situation actuelle :
Actuellement, nous enseignons à ces robots (appelés Solveurs Neuraux) en utilisant des « roues stabilisatrices ». Nous générons des millions de faux itinéraires de livraison sur un ordinateur où les maisons sont parfaitement espacées dans une grille nette, comme un échiquier. Le robot devient très doué pour résoudre ces puzzles parfaits et géométriques.

Le problème :
Quand vous sortez ce robot dans le monde réel, il s'écrase. Les vraies villes ne sont pas des grilles. Elles ont des grappes de maisons, des routes sinueuses et des motifs étranges. Le robot, entraîné uniquement sur des grilles parfaites, est confus et crée des itinéraires de livraison terribles. C'est ce qu'on appelle le fossé de généralisation. C'est comme apprendre à quelqu'un à nager dans une piscine calme et vide, puis le jeter dans un océan tempétueux avec des vagues et des courants.

La solution : EvoReal (Le « Simulateur Intelligent »)

Les auteurs de cet article ont créé un nouveau système appelé EvoReal. Au lieu de simplement jeter le robot dans l'océan réel, ils ont construit un « Simulateur Intelligent » qui apprend au robot à gérer la tempête avant qu'il ne quitte la piscine.

Voici comment cela fonctionne, étape par étape :

1. L'« Architecte » (Le LLM)

L'équipe a utilisé un Grand Modèle de Langage (LLM) — voyez cela comme un architecte super intelligent et créatif. Le travail de cet architecte n'est pas de conduire le camion, mais de concevoir les parcours d'entraînement.

D'habitude, nous créons simplement des parcours d'entraînement aléatoires. Mais le LLM est invité à regarder les cartes de livraison du monde réel (comme les célèbres benchmarks TSPLib et CVRPLib) et à dire : « Hmm, les vraies villes ont ces motifs spécifiques : certaines zones sont encombrées, d'autres sont dispersées, et certaines ont des formes répétitives. »

2. La « Salle de sport évolutive » (Évolution du générateur)

Le LLM ne conçoit pas seulement un parcours ; il gère une salle de sport évolutive.

Génération : Le LLM écrit du code pour créer de faux itinéraires de livraison qui ressemblent exactement aux vraies villes (avec des grappes, des vides et des formes bizarres).
Test : Il teste ces faux itinéraires sur le robot.
Réflexion et Amélioration : Si le robot éprouve des difficultés avec un type spécifique de faux itinéraire, le LLM examine le code, dit : « Ah, ce générateur n'a pas rendu les grappes assez serrées », et réécrit le code pour que la prochaine série de faux itinéraires soit encore plus réaliste.
Résultat : Avec le temps, le LLM fait évoluer un « générateur » qui crée des données synthétiques si réalistes qu'elles imitent statistiquement le monde réel.

3. L'« Entraînement Progressif » (L'échelle)

Une fois que le LLM a construit ces parcours d'entraînement « semblables au monde réel », le robot ne saute pas directement au niveau le plus difficile. Il grimpe une échelle :

Phase 1 (Le Pont) : Le robot est d'abord entraîné sur les nouvelles données synthétiques réalistes du LLM. Il apprend à gérer les grappes et les motifs irréguliers dans un environnement simulé sûr. C'est comme s'entraîner dans une piscine avec des vagues artificielles.
Phase 2 (Le Monde Réel) : Une fois que le robot est confiant, il reçoit une dernière session d'entraînement courte sur les réels problèmes de référence. Comme il a déjà appris l'« ambiance » des vraies villes en Phase 1, il s'adapte instantanément.

Les Résultats : De « Bon aux Échecs » à « Grand Maître de la Ville »

L'article a testé cela sur deux ensembles célèbres de problèmes de routage du monde réel (TSPLib et CVRPLib).

Avant EvoReal : Les meilleurs modèles d'IA étaient comme des étudiants qui n'ont étudié que pour un type spécifique de test de mathématiques. Lorsqu'ils voyaient un problème réel, leurs scores chutaient considérablement (parfois de 30 % ou plus).
Après EvoReal : Les modèles entraînés avec cette méthode sont devenus incroyablement performants.
- Sur les benchmarks TSPLib (Voyageur de commerce), l'écart entre leur solution et la solution parfaite est tombé à seulement 1,05 %.
- Sur les benchmarks CVRPLib (Routage de véhicules), l'écart est tombé à 2,71 %.

L'idée clé :
L'article affirme qu'en utilisant un LLM pour faire évoluer de meilleures données d'entraînement (plutôt que de simplement faire évoluer le robot lui-même), ils ont comblé le fossé entre le faux et le réel. Le robot a appris à généraliser parce qu'il a été entraîné sur des données « fausses » qui ressemblaient exactement à des données « réelles ».

Analogie de synthèse

L'ancienne méthode : Apprendre à un pilote à voler dans un simulateur sans vent, puis l'envoyer dans un ouragan.
La méthode EvoReal : Utiliser une IA pour concevoir un simulateur qui reproduit parfaitement les turbulences, les cisaillements de vent et les tempêtes d'un ouragan. Le pilote s'entraîne dans ce simulateur hyper-réaliste, puis monte dans le vrai avion et vole parfaitement.

L'article prouve que la génération de meilleures données d'entraînement (guidée par l'IA) est un moyen plus puissant de corriger ces robots que de simplement modifier les robots eux-mêmes.

Résumé Technique : Combler le fossé entre les problèmes de routage synthétiques et réels via la génération d'instances guidée par LLM et l'adaptation progressive

Énoncé du Problème

Les méthodes d'Optimisation Combinatoire Neuronale (NCO) ont atteint des performances de pointe sur les problèmes de tournées de véhicules (VRP) synthétiques, particulièrement ceux avec des nœuds distribués uniformément. Cependant, un écart de généralisation significatif persiste lorsque ces modèles sont appliqués à des scénarios de routage du monde réel, tels que les benchmarks TSPLib et CVRPLib. Les solveurs neuronaux existants peinent à s'adapter aux motifs structurels hétérogènes et non uniformes inhérents aux jeux de données authentiques. Bien que les Grands Modèles de Langage (LLM) aient montré un potentiel pour faire évoluer les heuristiques ou résoudre directement des Problèmes d'Optimisation Combinatoire (COP), ils échouent souvent à traiter des instances de taille moyenne à grande (ex: >50 nœuds) en raison des limites de contexte et des problèmes de cohérence lors du traitement de descriptions textuelles étendues. Par conséquent, il est nécessaire de concevoir un cadre capable de combler le décalage de distribution entre les données d'entraînement synthétiques et les benchmarks du monde réel sans nécessiter de changements architecturaux dans les solveurs ou de compter uniquement sur un ajustement fin (fine-tuning) direct, qui produit souvent des améliorations limitées.

Méthodologie : EvoReal

Les auteurs proposent EvoReal, un cadre centré sur les données qui exploite les LLM pour faire évoluer des générateurs de données plutôt que de résoudre directement les problèmes de routage. Le cadre se compose de deux composantes principales : un module d'évolution guidé par LLM pour la synthèse d'instances et une stratégie d'ajustement fin progressif pour l'adaptation du modèle.

1. Synthèse d'instances par évolution guidée par LLM

Au lieu de solliciter les LLM pour résoudre des instances TSP ou CVRP, EvoReal les incite à générer des générateurs de données basés sur du code qui produisent des instances synthétiques imitant les distributions du monde réel.

Représentation du générateur : Chaque générateur est défini par une description de fonction, une implémentation de code (basée sur PyTorch) et un score de fitness.
Alignement structurel : Le processus d'évolution vise à minimiser la divergence entre la distribution synthétique générée par le LLM ( $D(h_\phi(Z))$ ) et la distribution réelle cible ( $D_{real}$ ). La divergence est mesurée via des métriques de substitution, spécifiquement l'écart d'optimalité moyen sur un ensemble de validation.
Modularisation et catégorisation : Pour capturer diverses structures, l'ensemble de validation (TSPLib/CVRPLib) est segmenté en catégories basées sur des caractéristiques statistiques :
- Énergie FFT : Mesure la périodicité globale ou la répétitivité.
- Ratio NN (Coefficient de variation) : Mesure la variation des distances de plus proches voisins pour distinguer les configurations de type grille, aléatoires ou regroupées (clusters).
- Sur la base de ces métriques, les instances sont classées par types (ex: S1 pour les structures répétitives, S2 pour les structures de type grille/faible regroupement, S3 pour les agrégations locales). Des générateurs spécialisés sont fait évoluer pour chaque catégorie.
Processus évolutif : Le cadre adapte l'approche ReEvo (Évolution Réflexive) avec des modifications spécifiques :
- Sélection basée sur le rang : Sélectionne les descendants selon le classement de fitness pour accélérer la convergence.
- Sélection différée : La sélection intervient après le croisement et la mutation pour éviter l'élimination prématurée de candidats diversifiés.
- Mécanismes de réflexion : Utilise la réflexion à court terme (comparaison de paires de parents) et la réflexion à long terme (distillation d'idées pour guider la mutation) pour affiner les générateurs de manière itérative.

2. Stratégie d'ajustement fin progressif

Une fois les générateurs optimaux identifiés, les solveurs neuronaux pré-entraînés (POMO et LEHD) subissent un processus d'ajustement fin progressif en deux phases pour combler l'écart synthétique-réel :

Phase Un (Adaptation Structurelle) : Le modèle est ajusté sur des données synthétiques à grande échelle générées par les générateurs évolués et guidés par LLM. Cette phase expose le modèle à diverses structures de type TSPLib (distributions mixtes de S1, S2, S3) sans modifier l'architecture du modèle. L'objectif est d'aligner les représentations internes du modèle avec les a priori structurels des données réelles.
Phase Deux (Adaptation Directe) : Le modèle, désormais adapté à diverses structures, est ensuite ajusté directement sur les instances réelles de référence (TSPLib/CVRPLib). Cette phase permet au modèle de passer de tâches synthétiques "faciles" à des cas réels "difficiles", réduisant ainsi efficacement l'écart de performance final.

Contributions Clés

Cadre EvoReal : L'introduction d'un nouveau cadre qui utilise les LLM pour faire évoluer des générateurs de données plutôt que des solveurs. Cette approche synthétise des instances de VRP structurellement réalistes qui imitent statistiquement les distributions du monde réel, traitant ainsi la cause profonde du fossé de généralisation.
Stratégie d'ajustement fin progressif : Une stratégie d'adaptation en deux phases qui aligne d'abord les solveurs neuronaux avec des distributions diversifiées issues de l'évolution par LLM, puis les affine sur des données réelles. Cela permet une adaptation de domaine efficace sans modification architecturale, surpassant l'ajustement fin direct sur les données réelles seules.
Performances de pointe (SOTA) : Le cadre démontre des améliorations significatives de la généralisation sur un large spectre d'échelles de problèmes sur les benchmarks TSPLib et CVRPLib, atteignant de nouveaux résultats de pointe pour les solveurs neuronaux.

Résultats Expérimentaux

Les auteurs ont évalué EvoReal sur 70 problèmes TSPLib et 100 problèmes CVRPLib SetX, en comparaison avec les solveurs classiques (Concorde, LKH-3, ORTools) et diverses bases neuronales (POMO, LEHD, SGBS, CNF, etc.).

Performance TSPLib :
- LEHD (notre méthode) avec 50 itérations RRC a atteint un écart d'optimalité global de 1,05 % sur TSPLib, surpassant nettement les autres méthodes d'apprentissage et réduisant l'écart avec Concorde.
- POMO (notre méthode) a réduit l'écart global à 11,59 %, une amélioration substantielle par rapport au POMO pré-entraîné (26,66 %).
- La méthode a montré une force particulière sur les instances de grande échelle (1000–5000 nœuds), là où les solveurs neuronaux traditionnels se dégradent généralement de manière significative.
Performance CVRPLib :
- LEHD (notre méthode) a atteint un écart global de 2,71 % sur CVRPLib SetX, surpassant tous les autres solveurs neuronaux et restant compétitif avec ORTools.
- La stratégie d'ajustement fin progressif a notablement réduit la disparité de performance entre les petites et les grandes instances.
Études d'ablation :
- La suppression de la Phase 1 ou de la Phase 2 de la stratégie d'ajustement fin a entraîné une dégradation des performances, confirmant la nécessité de l'approche progressive.
- La comparaison des générateurs évolués avec des générateurs de distribution naïfs (Gaussienne, Beta, etc.) a montré que les générateurs évolués par LLM atteignaient systématiquement des écarts d'optimalité plus faibles, validant leur capacité à capturer des caractéristiques structurelles complexes.
- Le cadre s'est avéré robuste face aux différents LLM, OpenAI o3 offrant les meilleures performances de génération.

Signification et Revendications

L'article affirme qu'EvoReal parvient à combler le fossé de généralisation entre les problèmes de routage synthétiques et réels en déplaçant l'attention de l'évolution des solveurs vers l'évolution des distributions de données. Les auteurs soulignent que leur approche :

Automatise la découverte : Elle permet la découverte automatisée de générateurs de données qui s'alignent sur les a priori structurels du monde réel, une tâche difficile à accomplir avec une conception heuristique manuelle.
Efficacité : Elle réalise ces gains sans nécessiter de réentraînement coûteux à partir de zéro ou de modifications architecturales des solveurs neuronaux SOTA existants.
Scalabilité : La méthode est efficace sur une large gamme de tailles de problèmes, traitant spécifiquement la dégradation des solveurs neuronaux sur les instances de grande échelle où ils échouaient auparavant.
Supériorité sur l'ajustement fin direct : Les résultats démontrent qu'adapter les modèles via des distributions synthétiques évoluées (Phase 1) avant l'ajustement fin direct (Phase 2) offre une meilleure généralisation que l'ajustement fin direct sur les données réelles, suggérant que le "curriculum" d'adaptation structurelle est crucial pour la robustesse.

Les auteurs concluent que ce pipeline d'adaptation basé sur les générateurs offre une direction prometteuse pour améliorer l'applicabilité pratique des méthodes de NCO dans les scénarios de logistique et de transport du monde réel.