🤖 AI

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

本文介绍了 EvoReal，这是一个利用大语言模型（LLM）引导的进化合成技术来生成结构真实训练实例，并逐步适配神经求解器，从而显著缩小合成数据与 TSPLib 和 CVRPLib 等真实世界路由基准测试之间泛化差距的框架。

原作者： Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

发布于 2026-01-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大问题：“辅助轮”与“真实道路”

想象一下，你正在教一个机器人成为世界上最优秀的快递司机。

现状：
目前，我们使用“辅助轮”来训练这些机器人（称为神经求解器/Neural Solvers）。我们在电脑上生成数百万条虚假的配送路线，其中的房屋分布得非常完美，就像棋盘上的格子一样整齐划一。机器人非常擅长解决这些完美的、网格状的谜题。

问题：
当你把那个机器人带到现实世界时，它会发生碰撞。真实的城市并不是网格状的。它们有房屋集群、蜿蜒的道路和奇特的模式。只在完美网格上接受过训练的机器人会感到困惑，并做出糟糕的配送路线。这被称为泛化差距（generalization gap）。这就像是在平静、空旷的泳池里教一个人游泳，然后突然把他扔进一个有波浪和洋流的暴风雨海洋中。

解决方案：EvoReal（“智能模拟器”）

该论文的作者创建了一个名为 EvoReal 的新系统。他们并没有直接把机器人扔进真实的海洋，而是构建了一个“智能模拟器”，让机器人在离开泳池之前，就能学会如何应对风暴。

以下是其工作原理，分步详解：

1. “建筑师”（大语言模型/LLM）

团队使用了一个大语言模型（LLM）——把它想象成一个超级聪明、富有创造力的建筑师。这个建筑师的任务不是去驾驶卡车，而是设计训练课程。

通常情况下，我们只是随机制作训练课程。但 LLM 被要求观察真实的城市配送地图（例如著名的 TSPLib 和 CVRPLib 基准测试），并分析道：“嗯，真实的城市具有这些特定的模式：有些区域很拥挤，有些区域很分散，还有一些具有重复的形状。”

2. “进化健身房”（生成器进化）

LLM 不仅仅设计一个课程，它运行的是一个进化健身房。

生成（Generation）： LLM 编写代码来创建看起来完全像真实城市的虚假配送路线（带有集群、间隙和奇特的形状）。
测试（Testing）： 它在机器人身上测试这些虚假路线。
反思与改进（Reflection & Improvement）： 如果机器人在处理某种特定类型的虚假路线时遇到困难，LLM 会检查代码并说：“啊，这个生成器没能让集群足够紧密，”然后重写代码，使下一批虚假路线更加逼真。
结果： 随着时间的推移，LLM 进化出了一个“生成器”，它生成的合成数据在统计学上模仿了真实世界。

3. “渐进式训练”（阶梯）

一旦 LLM 构建好了这些完美的“类真实世界”训练课程，机器人并不会直接跳到最难的等级，而是爬上一把阶梯：

第一阶段（桥梁）： 机器人首先在 LLM 开发的这种全新的、真实的合成数据上进行训练。它学习如何在安全的模拟环境中处理集群和不规则模式。这就像是在一个带有人工波浪的泳池里练习。
第二阶段（实战）： 一旦机器人变得自信，它会进行最后一次简短的训练，使用的是实际的真实世界基准问题。因为在第一阶段它已经学习了真实城市的“感觉”，所以它能瞬间完成适应。

结果：从“擅长下棋”到“城市大师”

论文在两个著名的真实路由问题集（TSPLib 和 CVRPLib）上进行了测试。

使用 EvoReal 之前： 最好的 AI 模型就像是只针对某种特定数学考试进行复习的学生。当他们看到现实世界的问题时，他们的得分会显著下降（有时下降 30% 或更多）。
使用 EvoReal 之后： 使用这种方法训练的模型变得异常强大。
- 在 TSPLib（旅行商问题）基准测试中，它们的解与完美解之间的差距缩小到了仅 1.05%。
- 在 CVRPLib（车辆路径问题）基准测试中，差距缩小到了 2.71%。

核心要点：
论文声称，通过使用 LLM 来进化更好的训练数据（而不是仅仅进化机器人本身），他们弥合了虚假与真实之间的差距。机器人之所以能够实现泛化，是因为它是在感觉完全像“真实”数据的“虚假”数据上进行训练的。

总结类比

旧方法： 教一名飞行员在没有风的模拟器中飞行，然后将他送入一场飓风中。
EvoReal 方法： 使用 AI 来设计一个能够完美复制飓风中的湍流、风切变和风暴的模拟器。飞行员在这个超真实的模拟器中进行训练，然后步入真实的飞机，并完美飞行。

论文证明了，通过 AI 指导的更优化的训练数据生成，是修复这些机器人的一种比仅仅微调机器人本身更强大的方式。

技术摘要：通过 LLM 引导的实例生成与渐进式适配实现合成与真实路由问题的桥接

问题陈述

神经组合优化（NCO）方法在合成车辆路径问题（VRPs）（特别是节点均匀分布的场景）上已取得了最先进的性能。然而，当这些模型应用于真实的路由场景（如 TSPLib 和 CVRPLib 基准测试）时，仍然存在显著的泛化差距。现有的神经求解器难以适应真实数据集中固有的异构、非均匀结构模式。虽然大语言模型（LLMs）在演化启发式算法和直接解决组合优化问题（COPs）方面展现出了潜力，但由于上下文限制以及处理扩展文本描述时的连贯性问题，它们往往无法处理中大规模实例（例如超过 50 个节点）。因此，需要一种框架来弥合合成训练数据与真实世界基准之间分布偏移的问题，且该框架无需对求解器进行架构更改，也不应仅仅依赖于效果有限的直接微调。

方法论：EvoReal

作者提出了 EvoReal，这是一个利用 LLM 来演化数据生成器而非直接求解路由问题的以数据为中心的框架。该框架由两个主要部分组成：用于实例合成的 LLM 引导进化模块，以及用于模型适配的渐进式微调策略。

1. LLM 引导的进化实例合成

EvoReal 并不是提示 LLM 去求解 TSP 或 CVRP 实例，而是提示它们生成基于代码的数据生成器，用以产生模拟真实世界分布的合成实例。

生成器表示： 每个生成器由一个函数描述、一个代码实现（基于 PyTorch）和一个适应度分数（fitness score）定义。
结构对齐： 进化过程旨在最小化 LLM 生成的合成分布 ( $D(h_\phi(Z))$ ) 与目标真实世界分布 ( $D_{real}$ ) 之间的差异。这种差异通过代理指标进行衡量，具体为验证集上的平均最优性差距（optimality gap）。
模块化与分类： 为了捕捉多样化的结构模式，验证集（TSPLib/CVRPLib）根据统计特征被划分为不同的类别：
- FFT 能量： 衡量全局周期性或重复性。
- NN-Ratio（变异系数）： 衡量最近邻距离的变异程度，以区分网格状、随机分布或聚类布局。
- 基于这些指标，实例被归类为不同类型（例如，S1 代表重复结构，S2 代表弱聚类/网格状结构，S3 代表局部聚合）。针对每种类型都演化了专门的生成器。
进化过程： 该框架改编了 ReEvo（反思进化）方法并进行了特定修改：
- 基于排名的选择： 根据适应度排名选择后代，以加速收敛。
- 延迟选择： 选择过程发生在交叉和变异之后，以防止过早消除多样化的候选方案。
- 反思机制： 使用短期反思（比较父代对）和长期反思（提炼见解以指导变异）来迭代优化生成器。

2. 渐进式微调策略

一旦确定了最优生成器，预训练的神经求解器（POMO 和 LEHD）将经历一个两阶段的渐进式微调过程，以弥合合成与真实之间的差距：

第一阶段（结构适配）： 模型在由演化的 LLM 引导生成器产生的大规模合成数据上进行微调。这一阶段使模型接触到多样化的、具有 TSPLib 风格的结构模式（S1、S2、S3 的混合分布），而无需修改模型架构。其目标是将模型的内部表示与真实数据的结构先验进行对齐。
第二阶段（直接适配）： 已经过适配的模型随后在实际的基准实例（TSPLib/CVRPLib）上进行直接微调。这一阶段允许模型从“简单”的合成任务过渡到“困难”的真实案例，从而有效地缩小最终的性能差距。

核心贡献

EvoReal 框架： 引入了一种全新的框架，该框架使用 LLM 来演化数据生成器而非求解器。这种方法能够合成在统计上模拟真实世界分布的结构化真实 VRP 实例，解决了泛化差距的根本原因。
渐进式微调策略： 一种两阶段适配策略，首先通过多样化的、由 LLM 演化的分布来对齐神经求解器，然后再在真实基准数据上进行精炼。这实现了无需架构更改的高效领域适配，其表现优于仅在真实数据上的直接微调。
最先进的性能： 该框架在广泛的问题规模下，在 TSPLib 和 CVRPLib 基准测试中展示了显著的泛化能力提升，为神经求解器刷新了最先进的结果。

实验结果

作者在 70 个 TSPLib 问题和 100 个 CVRPLib SetX 问题上评估了 EvoReal，并将其与经典求解器（Concorde, LKH-3, ORTools）以及各种神经基准（POMO, LEHD, SGBS, CNF 等）进行了对比。

TSPLib 性能：
- LEHD (本文方法) 在 50 次 RRC 迭代后，在 TSPLib 上的整体最优性差距达到 1.05%，显著优于其他学习型方法，并缩小了与 Concorde 的差距。
- POMO (本文方法) 将整体差距降低至 11.59%，相比预训练的 POMO（26.66%）有了实质性的提升。
- 该方法在处理大规模实例（1000–5000 个节点）时表现尤为强劲，而传统的神经求解器在这些规模下通常会出现性能大幅下降。
CVRPLib 性能：
- LEHD (本文方法) 在 CVRPLib SetX 上实现了 2.71% 的整体差距，优于所有其他神经求解器，并与 ORTools 保持竞争水平。
- 渐进式微调策略显著缩小了小规模实例与大规模实例之间的性能差异。
消融研究：
- 移除第一阶段或第二阶段的微调策略都会导致性能下降，证实了渐进式方法的必要性。
- 将演化后的生成器与朴素分布生成器（高斯、Beta 分布等）进行对比显示，LLM 演化的生成器始终能获得更低的最优性差距，验证了其捕捉复杂结构特征的能力。
- 该框架在不同 LLM 之间表现出鲁棒性，其中 OpenAI o3 在生成器性能方面表现最佳。

意义与主张

论文声称，EvoReal 通过将重点从演化求解器转向演化数据分布，成功弥合了合成路由问题与真实世界路由问题之间的泛化差距。作者强调，其方法：

自动化发现： 它实现了自动发现与真实世界结构先验相一致的数据生成器，而这在手动设计启发式算法时是难以实现的。
高效性： 它无需昂贵的从头开始的重新训练或架构修改即可实现这些收益。
可扩展性： 该方法在广泛的问题规模上都是有效的，特别解决了神经求解器在以往无法泛化的规模化实例上的性能退化问题。
优于直接微调： 结果表明，在直接进行真实数据微调之前，先通过演化的合成分布进行适配（第一阶段），可以获得更好的泛化效果，这表明结构适配的“课程学习”对于鲁棒性至关重要。

作者总结道，这种基于生成器的适配流程为增强 NCO 方法在现实物流和运输场景中的实际应用价值提供了一个极具前景的方向。