《Machine Learning and Knowledge Extraction》：HRC: A Hybrid Reconstruction Framework for Neural Combinatorial Optimization Solvers
编辑推荐：
摘要译文：近期研究提出了后处理策略，通过使用神经组合优化（Neural Combinatorial Optimization, NCO）求解器迭代地重建当前解的部分片段，从而提升求解器在大规模车辆路径问题（Vehicle Routing Problem, VR
摘要译文：近期研究提出了后处理策略，通过使用神经组合优化（Neural Combinatorial Optimization, NCO）求解器迭代地重建当前解的部分片段，从而提升求解器在大规模车辆路径问题（Vehicle Routing Problem, VRP）实例上的性能。然而，该重建子问题本质上是一个最短哈密顿路径问题（Shortest Hamiltonian Path Problem, SHPP）实例，与求解器所训练的原VRP变体存在根本性差异。因此，NCO求解器在重建过程中可能因跨问题变体的泛化能力有限而出现性能下降。此外，仅依赖求解器可能不足以有效识别和修正复杂的交叉边或次优拓扑结构。针对上述局限，研究人员提出了一种名为混合重建框架（Hybrid Reconstruction Framework, HRC）的后处理策略。具体而言，HRC首先在SHPP实例上对NCO求解器进行微调，然后利用增强后的求解器执行大邻域随机重建。随后，HRC使用2-opt和kNN-DGR执行小邻域重建。在合成数据集和真实世界数据集上的旅行商问题（Traveling Salesman Problem, TSP）以及带容量约束的车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）实验结果表明，HRC显著提升了两类代表性NCO求解器在大规模实例上的性能，并且整体性能优于最先进的重建策略。最后，消融研究进一步验证了所提出设计的有效性。
论文解读文章：
研究背景与动机：车辆路径问题（Vehicle Routing Problem, VRP）是一类经典的组合优化问题（Combinatorial Optimization Problem, COP），其目标是在满足特定约束条件下，为服务客户规划成本最小的路径。近年来，神经组合优化（Neural Combinatorial Optimization, NCO）求解器利用深度神经网络从大量历史实例中学习，能够高效地搜索（近似）最优解，相较于传统启发式算法具有减少人工设计和支持GPU加速计算的优势。然而，现有NCO求解器在大规模VRP实例上仍存在性能不足的问题。为此，Luo等人提出了一种名为随机重建（Random Reconstruction, RRC）的后处理策略，通过迭代地重建求解器生成的初始解中的部分片段来提升求解质量。具体而言，RRC从当前解中随机采样一个连续片段，将片段内连接全部移除，并在保持端点固定的情况下将该片段重构为一个最短哈密顿路径问题（Shortest Hamiltonian Path Problem, SHPP）实例，随后用NCO求解器对该片段进行重建。但RRC存在两个关键局限：其一，NCO求解器通常在原始问题变体（如TSP或CVRP）上训练，而重建子问题本质上是SHPP，训练问题与SHPP之间的不匹配会导致求解器因跨问题变体泛化能力有限而产生性能下降；其二，RRC仅依赖求解器进行大邻域重建，当初始解中包含规模超过采样片段范围的复杂交叉边或次优拓扑结构时，RRC无法有效捕获和修正这些结构。为解决上述问题，研究人员提出了混合重建框架（Hybrid Reconstruction Framework, HRC）。
研究内容与结论：研究人员首先探究了一个研究问题：能否通过对原始问题训练的求解器在SHPP实例上进行微调，使其获得改进的重建性能？为此，HRC提出了一种微调方法，使基础求解器适应SHPP，得到专门的SHPP特化求解器。此外，HRC采用两阶段重建策略：在每次迭代中，首先使用特化求解器对所选片段执行大邻域随机重建；随后，基于特化求解器得到的解，应用2-opt和kNN-DGR算子在小邻域内进行二次重建。通过整合大邻域与小邻域算子，HRC在全局探索和局部开发之间取得平衡，既缓解了大邻域算子的优化盲区，也降低了小邻域算子陷入局部最优的风险，从而更有效地探索解空间。在合成数据集和真实世界数据集（TSPLIB和CVRPLIB Set-X）上的大量实验表明，HRC显著提升了DGL和LEHD两种代表性NCO求解器在大规模TSP和CVRP实例上的性能，并且整体性能优于最先进的重建策略。消融研究进一步验证了所提出的微调方法和两阶段重建策略的有效性。
关键技术方法：研究人员使用了以下主要技术方法：（1）基于梯度冲突分析的微调方法，通过构造SHPP子图并利用模仿学习对基础求解器进行全参数微调，获得SHPP特化求解器（DGL-S和LEHD-S）；（2）构建经验回放池（experience replay pool），存储高质量子解作为伪标签用于训练，并采用阈值触发的延迟更新策略；（3）两阶段重建策略，第一阶段采用特化求解器进行大邻域随机重建，第二阶段采用2-opt和kNN-DGR算子进行小邻域重建；（4）在训练过程中，从原始问题实例中随机采样SHPP子图，形成统一经验回放池，以缓解过拟合并提高泛化能力。实验使用了合成数据集MSVDRP以及TSPLIB和CVRPLIB Set-X真实世界基准。
研究结果：实验结果表明，在所有对比基线中，HRC是唯一能够在TSP-10000和CVRP-5000等大规模实例上将与（近似）最优解的偏差分别保持在1%和0.5%以内的求解器。Wilcoxon符号秩检验证实，DGL+HRC在所有评估规模上均显著优于DGL（p值小于0.05），而微调DGL-S仅需约150分钟，额外成本合理。在真实世界实例上，由于数据分布复杂且异构，HRC虽未达到合成数据集上的极小差距，但仍取得所有对比方法中的最佳整体性能。针对需求容量比分布偏移的分析表明，X-n247-k50实例因需求容量比与训练分布差异显著，导致较大差距。消融研究显示，HRC在TSP-10000上相比单独使用DGL-S重建、2-opt和kNN-DGR分别提升66.54%、33.07%和71.85%，在CVRP-5000上分别提升76.19%、69.58%和75.18%。设置4和设置5将三种算子分阶段组合，性能不如HRC，说明交替使用大小邻域算子更为有效。设置6和设置7改变迭代内算子顺序，性能与HRC几乎相同，表明主要优势来自互补邻域算子的迭代协调而非特定顺序。敏感度分析显示，增大子图规模可改善解质量（gap从2.6322%降至2.2385%），但同时增加推理时间（从134.82秒增至187.26秒），存在效果与效率的权衡。
讨论与结论：HRC依赖于若干简化假设，包括不考虑时间窗约束、实例规模和分布相对稳定、以及采用欧氏距离作为成本度量。在真实应用中，这些假设可能不完全成立。未来工作可考虑引入时间窗等复杂运营约束，利用域泛化技术（如不变表示学习）提升跨分布鲁棒性，并扩展支持更实际的旅行成本模型。研究人员在论文中提出HRC，通过微调方法增强基础求解器在SHPP上的性能，并采用两阶段重建策略实现更充分的解空间探索。合成数据和真实数据上的实验均表明HRC优于对比的重建策略，消融研究验证了所有设计组件的有效性。该论文发表于《Machine Learning and Knowledge Extraction》。
