Learning to Search, Searching to Learn:面向大规模车辆路径问题的闭环框架
NeurIPS 2026
摘要
大规模车辆路径问题 (VRP) 面临两个长期难题。一方面,许多可扩展方法依赖于图划分、邻域候选限制或分阶段决策来控制计算量, 这削弱了模型对全局结构的建模能力;另一方面,虽然许多方法在测试阶段引入搜索以提升解质量,但搜索通常只作为模型预测之后 的一次性后处理——模型给出预测,搜索进行修复,两者之间缺乏持续反馈:改进后的结构状态很少被反馈回模型指导后续推理, 而高质量的搜索解也几乎不会进入后续的训练监督。
为解决这一问题,我们提出 LSSL(Learning to Search, Searching to Learn), 一个面向大规模 VRP 的学习—搜索闭环框架。LSSL 首先在稀疏候选图上预测搜索友好的结构先验,随后搜索在这些先验的引导下 迭代精化当前解。更关键的是,搜索并不在一轮精化后就退出系统:推理阶段,搜索返回的结构状态被反馈给模型,用于下一轮预测; 训练阶段,多条高质量搜索解被组织成行级软目标,用于模型更新。由此形成”学习告诉搜索去哪里探索,搜索告诉模型哪些 结构值得学习”的闭环。实验表明,LSSL 在多个大规模 VRP 基准上同时取得良好的可扩展性、效率和解质量。
研究动机
现有的学习式 VRP 求解器大多通过压缩决策空间来实现可扩展性——对图做划分、限制候选、或分阶段 决策。这些手段让模型能装进有限的显存,但也丢掉了模型本该推理的全局结构。与此同时,测试阶段的 搜索通常是接在最后的固定后处理步骤,它发现的东西从不会回流进模型。
框架
LSSL 把学习和搜索接成一个闭环:
- 稀疏结构先验。 模型在稀疏候选图上预测一个对搜索友好的先验,为搜索提供一个”热启动”方向, 而不是从零开始搜。
- 先验引导的迭代搜索。 局部搜索在该先验的引导下精化当前解,把搜索预算集中在值得探索的地方。
- 推理阶段的结构反馈。 搜索产生的结构状态被反馈给模型,用于下一轮预测——而不是被丢弃。
- 训练阶段的软监督。 多条高质量搜索解被聚合成行级软目标,让模型持续从搜索已经发现的结构中 学习。
两个方向相互强化:“学习告诉搜索去哪里探索,搜索告诉模型哪些结构值得学习。“
图示
结果
在 6 个规模从 10 万到 20 万节点的真实世界 Art-TSP 实例上——每一个都是把一幅名画渲染成一个巨大的 TSP 路径——LSSL 与最优解的 gap 始终保持在 0.023%–0.039% 之间,远优于对比的所有基线:
| 实例 | Random Insertion | L2C-Insert | GLOP | LSSL(C=1,128 trials) | LSSL(C=2,256 trials) |
|---|---|---|---|---|---|
| mona-lisa100K | 6.706% | 3.764% | 3.224% | 0.034%(0.33h) | 0.026%(1.37h) |
| vangogh120K | 6.812% | 4.022% | 3.156% | 0.038%(0.49h) | 0.028%(1.91h) |
| venus140K | 6.581% | 4.102% | 3.067% | 0.027%(0.62h) | 0.023%(2.54h) |
| pareja160K | 6.830% | 4.259% | 3.158% | 0.032%(0.87h) | 0.024%(3.50h) |
| courbet180K | 7.145% | 4.777% | 3.294% | 0.035%(1.04h) | 0.025%(4.00h) |
| earring200K | 7.605% | 4.514% | 3.528% | 0.039%(1.32h) | 0.029%(5.18h) |
| 均值 | 6.947% | 4.240% | 3.238% | 0.034%(0.78h) | 0.026%(3.08h) |
在 10 万节点规模(下图 mona-lisa100K 实例)上,仅需 0.33 小时(约 20 分钟)就能把 gap
压到 0.034%:LSSL 可以在极短的时间内求解 10 万规模的实例。
mona-lisa100K(N = 100,000 个城市),路径长度 5,757,191。