🤖 AI

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

This paper introduces EvoReal, a framework that leverages LLM-guided evolutionary synthesis to generate structurally realistic training instances and progressively adapts neural solvers, significantly narrowing the generalization gap between synthetic data and real-world routing benchmarks like TSPLib and CVRPLib.

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

Published 2026-01-30

📖 4 min read☕ Coffee break read

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Training Wheels" vs. The "Real Road"

Imagine you are teaching a robot to be the world's best delivery driver.

The Current Situation:
Right now, we teach these robots (called Neural Solvers) using "training wheels." We generate millions of fake delivery routes on a computer where the houses are perfectly spaced out in a neat grid, like a chessboard. The robot gets really good at solving these perfect, grid-like puzzles.

The Problem:
When you take that robot out into the real world, it crashes. Real cities aren't grids. They have clusters of houses, winding roads, and weird patterns. The robot, trained only on perfect grids, gets confused and makes terrible delivery routes. This is called the generalization gap. It's like teaching someone to swim in a calm, empty pool, then throwing them into a stormy ocean with waves and currents.

The Solution: EvoReal (The "Smart Simulator")

The authors of this paper created a new system called EvoReal. Instead of just throwing the robot into the real ocean, they built a "Smart Simulator" that teaches the robot how to handle the storm before it leaves the pool.

Here is how it works, step-by-step:

1. The "Architect" (The LLM)

The team used a Large Language Model (LLM)—think of it as a super-smart, creative architect. This architect's job isn't to drive the truck; it's to design the training courses.

Usually, we just make random training courses. But the LLM is asked to look at real-world delivery maps (like the famous TSPLib and CVRPLib benchmarks) and say, "Hmm, real cities have these specific patterns: some areas are crowded, some are spread out, and some have repeating shapes."

2. The "Evolutionary Gym" (Generator Evolution)

The LLM doesn't just design one course; it runs an evolutionary gym.

Generation: The LLM writes code to create fake delivery routes that look exactly like real cities (with clusters, gaps, and weird shapes).
Testing: It tests these fake routes on the robot.
Reflection & Improvement: If the robot struggles with a specific type of fake route, the LLM looks at the code, says, "Ah, this generator didn't make the clusters tight enough," and rewrites the code to make the next batch of fake routes even more realistic.
Result: Over time, the LLM evolves a "generator" that creates synthetic data so realistic that it statistically mimics the real world.

3. The "Progressive Training" (The Ladder)

Once the LLM has built these perfect "Real-World-like" training courses, the robot doesn't jump straight to the hardest level. It climbs a ladder:

Phase 1 (The Bridge): The robot is first trained on the LLM's new, realistic synthetic data. It learns to handle clusters and irregular patterns in a safe, simulated environment. It's like practicing in a pool with artificial waves.
Phase 2 (The Real Deal): Once the robot is confident, it gets a final, short training session on the actual real-world benchmark problems. Because it already learned the "vibe" of real cities in Phase 1, it adapts instantly.

The Results: From "Good at Chess" to "Grandmaster of the City"

The paper tested this on two famous sets of real-world routing problems (TSPLib and CVRPLib).

Before EvoReal: The best AI models were like students who studied only for a specific type of math test. When they saw a real-world problem, their scores dropped significantly (sometimes by 30% or more).
After EvoReal: The models trained with this method became incredibly strong.
- On the TSPLib (Traveling Salesman) benchmarks, the gap between their solution and the perfect solution shrank to just 1.05%.
- On the CVRPLib (Vehicle Routing) benchmarks, the gap shrank to 2.71%.

The Key Takeaway:
The paper claims that by using an LLM to evolve better training data (rather than just evolving the robot itself), they bridged the gap between fake and real. The robot learned to generalize because it was trained on "fake" data that felt exactly like "real" data.

Summary Analogy

Old Way: Teaching a pilot to fly in a simulator with no wind, then sending them into a hurricane.
EvoReal Way: Using an AI to design a simulator that perfectly replicates the turbulence, wind shear, and storms of a hurricane. The pilot trains in this hyper-realistic simulator, then steps into the real plane and flies perfectly.

The paper proves that better training data generation (guided by AI) is a more powerful way to fix these robots than just tweaking the robots themselves.

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

Problem Statement

Neural Combinatorial Optimization (NCO) methods have achieved state-of-the-art performance on synthetic Vehicle Routing Problems (VRPs), particularly those with uniformly distributed nodes. However, a significant generalization gap persists when these models are applied to real-world routing scenarios, such as those found in the TSPLib and CVRPLib benchmarks. Existing neural solvers struggle to adapt to the heterogeneous, non-uniform structural patterns inherent in authentic datasets. While Large Language Models (LLMs) have shown promise in evolving heuristics and solving Combinatorial Optimization Problems (COPs) directly, they often fail to handle medium-to-large instances (e.g., >50 nodes) due to context limitations and coherence issues in processing extended textual descriptions. Consequently, there is a need for a framework that bridges the distributional shift between synthetic training data and real-world benchmarks without requiring architectural changes to the solvers or relying solely on direct fine-tuning, which often yields limited improvements.

Methodology: EvoReal

The authors propose EvoReal, a data-centric framework that leverages LLMs to evolve data generators rather than solving the routing problems directly. The framework consists of two primary components: an LLM-guided evolutionary module for instance synthesis and a progressive fine-tuning strategy for model adaptation.

1. LLM-Guided Evolutionary Instance Synthesis

Instead of prompting LLMs to solve TSP or CVRP instances, EvoReal prompts them to generate code-based data generators that produce synthetic instances mimicking real-world distributions.

Generator Representation: Each generator is defined by a function description, a code implementation (PyTorch-based), and a fitness score.
Structural Alignment: The evolution process aims to minimize the divergence between the synthetic distribution generated by the LLM ( $D(h_\phi(Z))$ ) and the target real-world distribution ( $D_{real}$ ). The divergence is measured via proxy metrics, specifically the average optimality gap on a validation set.
Modularization and Categorization: To capture diverse structural patterns, the validation set (TSPLib/CVRPLib) is segmented into categories based on statistical features:
- FFT Energy: Measures global periodicity or repetitiveness.
- NN-Ratio (Coefficient of Variation): Measures the variation in nearest-neighbor distances to distinguish between grid-like, random, and clustered layouts.
- Based on these metrics, instances are categorized into types (e.g., S1 for repetitive structures, S2 for weak-clustered/grid-like, S3 for local aggregations). Specialized generators are evolved for each category.
Evolutionary Process: The framework adapts the ReEvo (Reflective Evolution) approach with specific modifications:
- Rank-based Selection: Selects offspring based on fitness ranking to accelerate convergence.
- Delayed Selection: Selection occurs after crossover and mutation to prevent premature elimination of diverse candidates.
- Reflection Mechanisms: Uses short-term reflection (comparing parent pairs) and long-term reflection (distilling insights to guide mutation) to iteratively refine the generators.

2. Progressive Fine-Tuning Strategy

Once optimal generators are identified, the pre-trained neural solvers (POMO and LEHD) undergo a two-phase progressive fine-tuning process to bridge the synthetic-real gap:

Phase One (Structural Adaptation): The model is fine-tuned on large-scale synthetic data generated by the evolved LLM-guided generators. This phase exposes the model to diverse, TSPLib-style structural patterns (mixed distributions of S1, S2, S3) without modifying the model architecture. The goal is to align the model's internal representations with the structural priors of real-world data.
Phase Two (Direct Adaptation): The model, now adapted to diverse structures, is further fine-tuned directly on actual benchmark instances (TSPLib/CVRPLib). This phase allows the model to transition from "easy" synthetic tasks to "hard" real-world cases, effectively narrowing the final performance gap.

Key Contributions

EvoReal Framework: The introduction of a novel framework that uses LLMs to evolve data generators rather than solvers. This approach synthesizes structurally realistic VRP instances that statistically mimic real-world distributions, addressing the root cause of the generalization gap.
Progressive Fine-Tuning Strategy: A two-phase adaptation strategy that first aligns neural solvers with diverse, LLM-evolved distributions and then refines them on real benchmark data. This enables effective domain adaptation without architectural changes, outperforming direct fine-tuning on real data alone.
State-of-the-Art Performance: The framework demonstrates significant improvements in generalization across a broad spectrum of problem scales on TSPLib and CVRPLib benchmarks, achieving new state-of-the-art results for neural solvers.

Experimental Results

The authors evaluated EvoReal on 70 TSPLib problems and 100 CVRPLib SetX problems, comparing against classic solvers (Concorde, LKH-3, ORTools) and various neural baselines (POMO, LEHD, SGBS, CNF, etc.).

TSPLib Performance:
- LEHD (ours) with 50 RRC iterations achieved an overall optimality gap of 1.05% on TSPLib, significantly outperforming other learning-based methods and narrowing the gap to Concorde.
- POMO (ours) reduced the overall gap to 11.59%, a substantial improvement over the pre-trained POMO (26.66%).
- The method showed particular strength on large-scale instances (1000–5000 nodes), where traditional neural solvers typically degrade significantly.
CVRPLib Performance:
- LEHD (ours) achieved an overall gap of 2.71% on CVRPLib SetX, outperforming all other neural solvers and remaining competitive with ORTools.
- The progressive fine-tuning strategy notably reduced the performance disparity between small and large instances.
Ablation Studies:
- Removing either Phase 1 or Phase 2 of the fine-tuning strategy resulted in degraded performance, confirming the necessity of the progressive approach.
- Comparing evolved generators against naive distribution generators (Gaussian, Beta, etc.) showed that the LLM-evolved generators consistently achieved lower optimality gaps, validating their ability to capture complex structural characteristics.
- The framework proved robust across different LLMs, with OpenAI o3 yielding the best generator performance.

Significance and Claims

The paper claims that EvoReal successfully bridges the generalization gap between synthetic and real-world routing problems by shifting the focus from evolving solvers to evolving data distributions. The authors emphasize that their approach:

Automates Discovery: It enables the automated discovery of data generators that align with real-world structural priors, a task difficult to achieve with manual heuristic design.
Efficiency: It achieves these gains without requiring costly retraining from scratch or architectural modifications to existing SOTA neural solvers.
Scalability: The method is effective across a wide range of problem sizes, specifically addressing the degradation of neural solvers on large-scale instances where they previously failed to generalize.
Superiority over Direct Fine-Tuning: The results demonstrate that adapting models via evolved synthetic distributions (Phase 1) before direct fine-tuning (Phase 2) yields better generalization than fine-tuning directly on real data, suggesting that the "curriculum" of structural adaptation is critical for robustness.

The authors conclude that this generator-based adaptation pipeline offers a promising direction for enhancing the practical applicability of NCO methods in real-world logistics and transportation scenarios.