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

Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li · 2025

Read Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation by Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-10233.txt.

Introduction

Jianghan Zhu and seven co-authors help neural routing solvers cross from tidy synthetic maps to messy real delivery problems. Neural combinatorial optimization shines on uniform random instances but degrades on real vehicle routing benchmarks. Their system, EvoReal, uses an evolutionary module guided by large language models to synthesize training instances whose structural statistics mimic genuine real-world cases.

Pre-trained solvers are then adapted in stages: first aligned to the enriched synthetic distributions, then fine-tuned directly on benchmark instances from TSPLib and CVRPLib. The staged adaptation markedly improved generalization across problem scales. Remaining gaps to optimal solutions shrank to about one percent on TSPLib and under three percent on CVRPLib, showing that realistic instance generation can substitute for scarce real training data.

Catalog record

CREATORJianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-10233

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li 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. Code — https://github.com/HenryZhu1029/EvoReal 1 Introduction Being a longstanding NP-hard challenge, Vehicle Routing Problems (VRPs) represent a classic family of combinatorial optimization problems (COPs) ( 4 ; 7 ) widely encountered in the field of logistics ( 8 ) and public transportation ( 34 ) . In recent years, Neural Combinatorial Optimization (NCO) methods have demonstrated remarkable success in tackling various VRPs through deep reinforcement learning and attention-based models, achieving state-of-the-art performance on synthetic VRP instances ( 3 ; 35 ; 39 ; 14 ; 46 ) . Despite this progress, existing NCO models frequently exhibit limited generalization when transitioning from synthetic, uniformly distributed training data to real-world problem instances, such as those found in benchmarks like TSPLib ( 50 ) and CVRPLib ( 56 ) . This distributional shift significantly restricts their practical applicability ( 30 ; 5 ; 18 ) . Figure 1: Overall workflow of EvoReal including LLM-guided generator evolution and progressive fine-tuning. Top Left : Validation set and unseen test set are split, with validation problems grouped by distribution category for structural-specific generator design. Top Right : LLM-driven module evolves generators which are evaluated on specific validation sets. Bottom : Pre-trained models are progressively fine-tuned on data from the evolved generators and the validation set’s real instances. On the other hand, LLM solvers exhibit strong generalization capabilities when confronted with new COPs and distributions. Recent works leverage LLMs to dynamically generate heuristics or evolve hyper-heuristics ( 15 ; 13 ) , thus facilitating efficient Evolutionary Search (ES) of heuristic spaces without human bias ( 62 ) . Noteworthy endeavors include FunSearch ( 51 ) , EoH ( 42 ) , and ReEvo ( 63 ) . However, existing LLM-based approaches often encounter challenges when handling tasks that require extensive contextual information, typically demonstrating reduced coherence and accuracy in the processing of extended textual descriptions ( 62 ; 61 ) . Consequently, these approaches exhibit significant limitations when addressing medium- or large-size instances (e.g., instances involving more than 50 nodes), thus compromising their ability to effectively generalize to real-world VRP instances. Motivated by these observations, we propose EvoReal, a novel data-centric framework explicitly designed to enhance the generalization capabilities of NCO models for real-world VRPs. Unlike prior approaches that evolve heuristics or solvers for direct solution construction, we innovatively leverage LLMs to evolve data generators that facilitate model adaptation. 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. Consequently, EvoReal facilitates smoother model adaptation by progressively refining solver parameters and representations , effectively bridging the generalization gap between synthetic data and real-world benchmark instances. We summarize our contributions as follows. (1) We propose EvoReal, an LLM-guided evolutionary framework to synthesize structurally realistic VRP instances, bridging the distributional gap between synthetic and real-world routing problems. (2) We introduce a progressive fine-tuning strategy, which first adapts neural combinatorial solvers to diverse LLM-evolved distributions and then further refines them on real benchmark data, enabling effective domain adaptation without architectural changes. (3) Extensive experiments on TSPLib and CVRPLib benchmarks demonstrate 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. Notably, our results demonstrate that this generator-based adaptation consistently outperforms direct fine-tuning on real data alone. Figure 2: LLM-driven evolution component in Fig. 1 . The pipeline within the blue rectangle block is repeated for N iterations. Dotted arrows represent the proxy-evaluation of each generator; black arrows indicate the flow of generators. For each pair of parents, the reflector LLM performs short-term reflection based on their relative performance, and this insight is used to guide crossover for designing new offspring. Accumulated short-term reflections are further distilled into long-term ones, which guide mutation to improve the current best generator. After mutation, populations are ranked and selected to maintain a fixed size. 2 Related Works Constructive Neural VRP Solvers. Those models learn policies to construct solutions in a step-by-step or one-shot manner: Pointer Network (Ptr-Net) proposed by ( 58 ) employed a transformer-based encoder-decoder network that generates solutions to VRPs in a sequential way. Follow-up works utilize reinforcement learning (RL) to improve Ptr-Net’s gradient update to generate better approximate solutions on TSP ( 3 ) and CVRP ( 47 ) . More recently, more neural VRP models have evolved with their architectures built upon attention mechanisms, starting with the attention-based model (AM) ( 35 ) , which is versatile on a wide range of COPs. Policy optimization with multiple optima (POMO) ( 37 ) , has further promoted the capability of the attention-based model on TSP and CVRP. Other constructive frameworks developed from AM and POMO illustrate their broader scalability ( 38 ; 11 ; 31 ; 10 ; 9 ; 23 ; 40 ) . Recent studies have investigated the severe generalization ability decrement in unseen problem sizes or distributions ( 30 ; 44 ) . In the line of size generalization, there are many attempts to generalize solvers from small instances to larger ones ( 41 ; 32 ; 2 ; 24 ; 52 ) . Unlike approaches focused on scaling, considerable efforts have been devoted to addressing cross-distribution generalization, including works that augment training instances on multi-distribution and multitasks ( 19 ) , and works which synergetically train a backbone model with multi-distribution instances towards a generalizable solver on out-of-distribution tasks ( 65 ; 64 ) . Recently, training LLM for end-to-end CO has been attempted, moving beyond prompting paradigms ( 28 ) . Learning to Optimize with LLMs. Existing approaches to improving generalization in combinatorial optimization (CO) take advantage of the linguistic comprehension and domain-specific competence of LLMs via prompt

Read the complete text