AI Research Portal

This paper introduces EvoReal, a novel data-centric framework designed to enhance the generalization capabilities of Neural Combinatorial Optimization (NCO) models for real-world Vehicle Routing Problems (VRPs). The core idea involves an LLM-guided evolutionary module that generates synthetic VRP instances with diverse and realistic structural patterns, statistically mimicking real-world distributions. Subsequently, a progressive fine-tuning strategy incrementally adapts pre-trained NCO models, first to these LLM-evolved synthetic distributions and then to actual benchmark instances. EvoReal significantly improves the generalization of state-of-the-art neural solvers, achieving a notable reduced performance gap compared to optimal solutions on TSPLib (1.05%) and CVRPLib (2.71%) benchmarks across various problem scales.

The paper addresses several bottlenecks in existing NCO methods:

Limited Generalization to Real-World VRPs: 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. This distributional shift significantly restricts their practical applicability.

The paper claims the following key contributions:

EvoReal Framework: Proposal of EvoReal, an LLM-guided evolutionary framework to synthesize structurally realistic VRP instances, thereby bridging the distributional gap between synthetic and real-world routing problems.
Progressive Fine-tuning Strategy: Introduction of a progressive fine-tuning strategy that first adapts neural combinatorial solvers to diverse LLM-evolved distributions and then refines them on real benchmark data, enabling effective domain adaptation without architectural changes.
Improved Generalization: Extensive experiments on TSPLib and CVRPLib benchmarks demonstrating that EvoReal significantly improves the generalization of SOTA neural solvers across a wide range of problem sizes, achieving new state-of-the-art results and notably reducing the performance gap between small and large instances.

EvoReal is a novel LLM-guided evolution framework that evolves VRP data generators and employs a progressive fine-tuning strategy. It consists of two main components: LLM-driven evolutionary search and proxy evaluation.

LLM-driven Evolution: This component aims to gradually develop structurally specific generators. LLMs are prompted to transform latent generator configurations into realistic routing distributions. The evolution process iteratively minimizes the divergence between the synthetic distribution generated by an LLM-parameterized data generator and the target real-world distribution.
- Key Equation: The objective for generator evolution is defined as: min Levolve(Φ) = D (Dreal, D (hΦ(Z))) where D(·||·) is a divergence measure (e.g., KL divergence, average gap).
- Generator Representation: Each generator h is described by three components: 1) a function description, 2) a code implementing generation, and 3) a fitness score.
- Evolution Process: The workflow involves initializing a code population of N generators using prompts, expanding the population using four prompt strategies (crossover, mutation, short- & long-term reflection), evaluating each new generator on its structurally-specific validation set, selecting k offspring generators based on rank (calculated from fitness scores), and repeating these steps until a pre-set maximum number of generators is evaluated or no better generator is found for m consecutive iterations.
Proxy Evaluation: During LLM-driven evolution, the performance of each LLM-designed generator is assessed using external proxy metrics, such as average gap on the validation set (the gap between the objective value found and the best-known optimum). Generators are fine-tuned for a small number of epochs (e.g., 10 epochs for LEHD) on the validation set, and the best average gap serves as the fitness score.
Progressive Fine-tuning: After generator evolution, neural models are progressively fine-tuned to real-world distributions in two phases:
- Phase One: The best-performing evolved generators collaboratively generate large-scale synthetic data of the same problem size. Pre-trained models are trained on these diverse, TSPLib-style instances to equip neural solvers with preliminary exposure to similar structures found in real-world scenarios.
- Phase Two: After aligning the neural model with a broader range of structural priors from phase one, the best-performed model is fine-tuned with TSPLib/CVRPLib instances and validated on themselves. This enables the model to transition from synthetic to real-world instances, forming a synthetic-real progression.

Generator Evolution LLM: OpenAI model 03 is used to construct new generators.
Hardware for Evolution: All evolution pipelines can be conducted on a single NVIDIA RTX 3090 Ti GPU with 24GB memory.
Hardware for Fine-tuning: Progressive fine-tuning is performed on one NVIDIA RTX A6000 GPU with 48GB memory.
Validation Set Split (TSPLib): 70 TSPLib problems of size less than 5000 are selected. 48 problems (≈ 70%) are picked for validation and categorized into three types (S1, S2, S3), each serving as a specific validation set for one type of generator. The remaining 22 problems are a held-out unseen set.
Validation Set Split (CVRPLib): 70% problems from CVRPLib (SetX) are randomly selected for validation and direct fine-tuning. The remaining 30% are left as the unseen set.
Fine-tuning Instance Size: For both POMO and LEHD, evolved generators produce TSP or CVRP of size 100 for fine-tuning.
Phase Two Data Handling: Instances from VRPLib are expanded by a pre-set batch size as a single batch, and they are expanded only once in one epoch.
Optimal Solution Acquisition: For LEHD, Concorde solver and HGS are adopted to obtain the optimum of TSP and CVRP, respectively.
Inference Augmentation: 8-fold augmentation for POMO or greedy mode for LEHD is used to calculate the total average gap on the validation set as the performance metric.
Non-neural Solver Time Limits (TSP): LKH-3 and ORTools: Tmax = 1.8 * n seconds. Concorde: Tmax = 10 minutes.
POMO Training: Trained using reinforcement learning (RL) with policy gradient methods.
LEHD Training: Employs a supervised learning (SL) scheme that leverages optimal objective values.
Fine-tuning Epochs (TSPLib): POMO fine-tuning setups are trained for 600 epochs. LEHD fine-tuning setups are trained for 40 epochs.

Datasets:
- TSPLib95 (Reinelt 1991)
- CVRPLib setX (Uchoa et al. 2017)
Metrics:
- Average objective values
- Optimality gap (%) (to the optimal average tour length)
- Total inference time
Baselines:
- Classic Solvers: Concorde, LKH-3, ORTools, HGS (Vidal 2022)
- Deep Neural Solvers: POMO (Kwon et al. 2020), LEHD (Luo et al. 2023), SGBS (Choo et al. 2022), BQ (Drakulic et al. 2023), ELG (Gao et al. 2024), CNF (Zhou et al. 2024), DIFUSCO (Sun and Yang 2023)
Numeric Results (TSPLib - Table 1):
- LEHD (ours): RRC-50: Achieved an overall optimality gap of 1.05% with an average objective of 73919.96 and total inference time of 1h 52min. This is the best among learning-based methods.
- POMO (ours): ×8 aug: Achieved an overall optimality gap of 11.59% with an average objective of 81630.17 and total inference time of 26min.
- Compared to pre-trained LEHD (RRC-50) (2.48% gap) and POMO (×8 aug) (26.66% gap), EvoReal significantly reduced the gap.
Numeric Results (CVRPLib - Table 2):
- LEHD (ours): RRC50: Achieved an overall optimality gap of 2.71% with an average objective of 64817.21 and total inference time of 1h 9min. This is the best among learning-based methods.
- POMO (ours): ×8 aug: Achieved an overall optimality gap of 4.87% with an average objective of 66180.32 and total inference time of 2m 6s.
Ablation Study (TSPLib Fine-tuning - Table 3 & 4):
- POMO (aug×8) Full (ours): Overall gap 6.78% (Time: 6h 37min) vs. w/o Fine-tune 64.84%.
- LEHD - greedy Full (ours): Overall gap 5.37% (Time: 38.5 min) vs. w/o Fine-tune 11.27%.
Ablation Study (LLM Evolution - Table 5):
- Full EvoReal: Achieved an average augmented gap of 16.52 ±0.05 (best: 16.41).
- W/O LLM: Achieved 19.79 ±0.25 (best: 19.46).
- W/O Finetuning: Achieved 22.21 ±0.00.
Runtime/Training Cost:
- TSPLib: LEHD (ours) RRC-50: 1h 52min. POMO (ours) ×8 aug: 26min.
- CVRPLib: LEHD (ours) RRC50: 1h 9min. POMO (ours) ×8 aug: 2m 6s.
- POMO fine-tuning (full): 6h 37min. LEHD fine-tuning (full): 38.5 min.

Potential Overfitting on Small-Size Problems: LEHD (ours) shows even smaller average gap in large-size instances compared to small-size ones, "possibly due to overfitting on small-size problems in the second phase of progressive fine-tuning."
Minor Degradation on Medium-Size Problems: For LEHD-greedy, the full framework shows "only minor degradation (at 0.04%) on the medium-size one" compared to other setups.

Method evidence: "At the core of EvoReal is an LLM-driven evolutionary module, which generates synthetic VRP instances structurally aligned with real-world distributions. This module systematically evolves simplistic synthetic scenarios into diverse and complex distributions, effectively capturing the intricate characteristics of real-world datasets. Subsequently, we introduce a progressive fine-tuning strategy which incrementally adapts pre-trained neural solvers by transitioning through increasingly complex synthetic instances toward actual real-world VRP scenarios." (section: 1 Introduction)
Result evidence: "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." (section: Abstract)
Limitation evidence: "It is worth noting that LEHD (ours) show even smaller average gap in large-size instances compared to small-size ones, possibly due to overfitting on small-size problems in the second phase of progressive fine-tuning." (section: 5 Ablation Studies)

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

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures