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

AI summary

Overview

Research area: Neural Combinatorial Optimization (NCO), specifically neural solvers for Vehicle Routing Problems (VRPs), combined with LLM-driven evolutionary search for synthetic data generation.

Technical level: Advanced. The paper assumes familiarity with attention-based neural routing solvers (POMO, LEHD), reinforcement and supervised training pipelines, and LLM-guided evolutionary program search. The high-level idea is accessible, but the mechanics require domain background.

Scope: This paper introduces EvoReal, a data-centric framework that uses large language models to evolve synthetic VRP instance generators which mimic real-world structures, and then progressively fine-tunes pre-trained neural solvers on that evolved data and on real benchmarks to close the synthetic-to-real generalization gap on TSPLib and CVRPLib.

What This Paper Is About

Neural routing solvers achieve excellent results on synthetic instances where customer locations are drawn uniformly at random, but they degrade sharply on real-world benchmark instances such as those in TSPLib and CVRPLib, which contain clustered, grid-like, and repeating geometric patterns. The paper's goal is to fix this distribution shift without redesigning model architectures or paying the cost of full retraining, by generating training data whose structural statistics match real instances. EvoReal does this by evolving data generators with an LLM rather than evolving heuristics or solvers, then adapting the model in two progressive stages from synthetic to real data.

Key Contributions

1. EvoReal, an LLM-guided evolutionary generator framework. Instead of using LLMs to write heuristics or directly solve problems, the paper uses LLMs to design and iteratively improve lightweight code generators that produce VRP instances whose structural attributes statistically resemble real-world ones.

2. A progressive fine-tuning strategy with two phases. Phase one aligns a pre-trained neural solver with the structurally enriched synthetic distributions produced by the evolved generators; phase two adapts the model on actual benchmark instances. The paper shows this synthetic-to-real progression outperforms direct fine-tuning on real data alone.

3. Structural modularization of real VRP benchmarks. TSPLib instances are categorized into three structural families (S1, S2, S3) using two statistics, FFT energy and nearest-neighbor ratio, and specialized generators are evolved for each family and then combined into a mixed-distribution generator.

4. State-of-the-art generalization results across problem scales. On TSPLib the method reduces the average optimality gap to 1.05% and on CVRPLib to 2.71%, with the largest improvements on large instances, using unmodified POMO and LEHD architectures.

Main Findings

• Large gap reductions on TSPLib. For LEHD with 50 RRC iterations, the overall average optimality gap drops from 2.48% (pre-trained LEHD) to 1.05%. For POMO with 8x augmentation, the gap drops from 26.66% to 11.59%.

• Largest gains occur on big instances. The improvement is most pronounced in the [1000, 5000) node range. Pre-trained POMO shows a 64.84% gap there, while the EvoReal-adapted POMO reduces it to 32.43%, and LEHD drops from 6.47% to 2.54%.

• Consistent gains on CVRPLib. LEHD with RRC-50 improves from 5.90% to 2.71% overall. POMO with 8x augmentation improves from 21.53% to 4.87%. Most of the improvement again concentrates on the largest instance range.

• Gap uniformity across scales. The adapted solvers show much more similar performance between small and large instances than their pre-trained counterparts, indicating the framework narrows both the distributional and the scale gap.

• Both progressive phases are necessary. Removing phase one leaves the model poorly prepared for diverse structures; removing phase two leaves it short of real-world accuracy. The full pipeline performs best in almost all size ranges, with only negligible degradation (0.01% and 0.04%) in one small/medium bracket respectively.

• Evolved generators beat hand-designed distributions. Comparing the evolved mixed-distribution generator against beta, exponential, binomial, Gaussian mixture, and Gaussian stripe generators, the evolved generator starts better and converges to a lower average gap.

• Every LLM mechanism contributes. Fitness scores of top generators improve from 19.79 (no LLM, hand-crafted seed) and 22.21 (no fine-tuning at all) down to 16.52 for the full EvoReal pipeline. Removing rank-based selection, design guidance, or late selection each worsens performance, with rank-based selection mattering most.

• Adaptation is cheap and architecture-agnostic. Inference time changes only marginally because model architectures are untouched; evolution runs on a single RTX 3090 Ti and fine-tuning on a single RTX A6000.

Methodology in Plain English

The researchers start from the observation that real routing benchmarks do not look like uniform random points, so a model trained only on uniform data is being tested on a different kind of problem than it practiced on.

Their first move is to make the training data look more realistic. Rather than hand-designing new distributions, they hand the LLM a small seed generator and ask it to write new generators in code. Each candidate generator is judged by a cheap proxy: the model is briefly fine-tuned on data from that generator, and the resulting average optimality gap on a held-out validation slice of real benchmark problems becomes the generator's fitness score. Generators with better fitness survive. New candidates are produced by four operators: crossover between two parents, mutation of the current best, plus short-term reflection (comparing two parents' relative performance) and long-term reflection (distilling accumulated insights to guide mutation). Two tweaks to the underlying ReEvo framework help: elite generators are kept with a rank-based selection probability, and selection is postponed until after mutation so newly created candidates get a chance to compete.

To keep the generators interpretable and targeted, the authors first split TSPLib into three structural families. FFT energy measures global periodicity or repeated patterns; the nearest-neighbor ratio measures how clustered point spacing is. Thresholds at FFT = 35 and NN-ratio = 0.5 separate S1 (repeating geometric motifs), S2 (grid-like or weakly clustered layouts), and S3 (locally dense clusters). One generator type is evolved for each family, and the best ones are combined into a single mixed-distribution generator.

The second move is progressive fine-tuning. In phase one, the pre-trained solver is trained for many epochs on the large synthetic datasets produced by the evolved generators, monitored continuously on 48 validation problems. This exposes the model to diverse structural patterns that resemble real ones. In phase two, the best phase-one checkpoint is fine-tuned on the actual benchmark instances. The result is a smooth transition from easy synthetic tasks to harder real ones instead of a single abrupt jump.

Evaluation uses 70 TSPLib problems below 5000 nodes (48 for validation, 22 held out) and 100 CVRPLib SetX problems (70% for validation and fine-tuning, 30% unseen). Baselines include exact and heuristic solvers (Concorde, LKH-3, ORTools, HGS-CVRP) and neural solvers (POMO, LEHD, SGBS, BQ, ELG, CNF, DIFUSCO).

Why This Matters

Impact on research. The paper reframes how LLMs should be used in combinatorial optimization: not as solvers and not as heuristic writers, but as designers of training data distributions. This opens a new axis for improving generalization that is orthogonal to architecture design, and it shows that a low-fidelity proxy evaluation loop is enough to guide the search. It also provides a reproducible statistical vocabulary (FFT energy, NN-ratio) for describing why real routing instances are hard.

Real-world applications.

• Last-mile delivery fleet routing, where customer addresses are clustered around apartment blocks, commercial districts, and road grids rather than spread uniformly.
• Ride-hailing and on-demand service dispatch, where pickup and drop-off demand is spatially concentrated and time-varying.
• Public transportation and school-bus route planning, where stops follow corridors and repeated patterns.
• Supply chain and cold-chain logistics, where depot locations, service zones, and capacity constraints create heterogeneous, structured instance geometries.

Industry relevance. Routing is a large operational cost center, and a solver that generalizes to real city layouts without per-deployment retraining is far more deployable than one that needs a bespoke training set for each region. Because EvoReal leaves model architectures untouched and adds only modest training overhead, it can be layered onto existing neural routing stacks. The generator evolution stage runs on commodity hardware, lowering the barrier for logistics firms to adapt general-purpose solvers to their own instance distributions.

Future Directions

1. Extending beyond routing. The authors explicitly plan to apply LLM-driven generator evolution to other combinatorial problems such as maximum independent set and bin packing, which have richer structural and constraint patterns that will demand more expressive generators.

2. Handling richer VRP variants. The current work covers TSP and capacitated VRP; time windows, pickup-and-delivery, and multi-depot constraints would require generators and validation metrics that capture additional feasibility structure.

3. Mitigating phase-two overfitting on small instances. The paper notes that LEHD adapted by EvoReal achieves a smaller gap on large instances than on small ones, possibly from overfitting during the real-data phase, which suggests a need for better regularization or size-aware curricula.

4. Reducing evolution cost and improving feedback quality. Generator search relies on expensive OpenAI o3 calls and low-fidelity proxy fine-tuning. Cheaper or open-weight LLMs, better fitness approximations, and more efficient population management are natural follow-ups, along with asking whether the evolved generators transfer across different backbone solvers without re-evolution.

Target Audience

This paper is most valuable to researchers and practitioners working on neural combinatorial optimization, learning-based routing solvers, and LLM-driven program or heuristic search. It will also interest machine learning engineers at logistics, delivery, and mobility companies who need solvers that transfer from synthetic pretraining to real operational data. Readers should already understand attention-based routing models, reinforcement and supervised training for COPs, and the basic mechanics of evolutionary program search to fully benefit from the methodology sections.

Authors’ abstract

Recent advances in Neural Combinatorial Optimization (NCO) methods have significantly improved the capability of neural solvers to handle synthetic routing instances. Nonetheless, existing neural solvers typically struggle to generalize effectively from synthetic, uniformly-distributed training data to real-world VRP scenarios, including widely recognized benchmark instances from TSPLib and CVRPLib. To bridge this generalization gap, we present Evolutionary Realistic Instance Synthesis (EvoReal), which leverages an evolutionary module guided by large language models (LLMs) to generate synthetic instances characterized by diverse and realistic structural patterns. Specifically, the evolutionary module produces synthetic instances whose structural attributes statistically mimics those observed in authentic real-world instances. Subsequently, pre-trained NCO models are progressively refined, firstly aligning them with these structurally enriched synthetic distributions and then further adapting them through direct fine-tuning on actual benchmark instances. Extensive experimental evaluations demonstrate that EvoReal markedly improves the generalization capabilities of state-of-the-art neural solvers, yielding a notable reduced performance gap compared to the optimal solutions on the TSPLib (1.05%) and CVRPLib (2.71%) benchmarks across a broad spectrum of problem scales.