《Computers & Operations Research》：TuneNSearch: A hybrid transfer learning and local search approach for solving vehicle routing problems
编辑推荐：
车辆路径问题（VRP）的求解是物流优化的核心挑战。现有方法往往受限于泛化能力弱或计算成本高。本研究提出TuneNSearch框架，将Transformer架构与边缘感知图注意力网络（E-GAT）结合，并集成高效的局部搜索算法。该框架先以多仓库VRP（MDVRP）进行预训练，再通过微调适配多种VRP变体。实验表明，TuneNSearch在CVRPLIB和TSPLIB数据集上，与已知最优解的偏差保持在3%以内，显著优于现有神经网络方法，为实际物流系统提供了高效、通用的决策支持。
车辆路径问题（Vehicle Routing Problem, VRP）是组合优化领域的经典难题，其目标是为车队设计访问一系列客户点的最优路线，以最小化总行驶距离。从城市配送、外卖物流到无人机投递，VRP的解决方案直接关系到运营成本与效率。然而，VRP家族庞大，包括带容量约束的VRP（CVRP）、多仓库VRP（MDVRP）、带时间窗的VRP（VRPTW）等诸多变体，且问题本身是NP-Hard的，这意味着随着问题规模增大，精确求解将变得不可行。
传统上，研究者们依赖元启发式算法（如遗传算法、模拟退火）来寻找高质量的解。近年来，基于神经网络的方法崭露头角，它们能够从数据中学习策略，快速生成解决方案。但这些方法通常存在两大局限：其一，大多数模型是针对单一VRP变体专门训练的，缺乏跨不同问题的泛化能力；其二，对于大规模实例，纯神经网络方法的求解质量往往不及成熟的元启发式算法。此外，现有的多任务或迁移学习方法，其预训练通常基于较简单的单仓库问题（如CVRP），这使得模型难以应对现实世界中更复杂的多仓库物流场景。
为了解决这些挑战，来自葡萄牙科英布拉大学的研究团队在《Computers 》上发表论文，提出了TuneNSearch——一个创新的混合框架。该框架巧妙地将迁移学习与高效的局部搜索相结合，旨在开发一个既能泛化到多种VRP变体，又能与顶尖元启发式算法性能相媲美的通用求解器。
为了开展这项研究，作者们主要运用了以下几个关键技术方法：首先，在模型架构上，他们采用了基于Transformer的编码器-解码器框架，并创新性地集成了边缘感知图注意力网络（Edge-aware Graph Attention Network, E-GAT）。E-GAT能够将节点间的距离信息直接融入注意力机制，从而更好地捕捉路径问题中固有的空间关系。其次，在训练策略上，他们使用了强化学习中的REINFORCE算法，并采用了带有多重最优策略优化（Policy Optimization with Multiple Optima, POMO）的框架，以利用问题的对称性提升解的质量。第三，他们设计了一套包含多种算子的高效局部搜索程序，用于对神经网络初步生成的解进行迭代优化。最后，在验证阶段，研究使用了大规模的公开基准数据集（CVRPLIB, TSPLIB）和随机生成的实例进行评估，确保了结论的可靠性。
研究结果
1. 模型架构的有效性
研究者将E-GAT编码器与POMO框架相结合。结果表明，这种组合增强了模型对图结构的编码能力，使其在评估从不同起点出发的解决方案轨迹时更为精准。在MDVRP的50节点和100节点实例上，该模型显著优于之前提出的多仓库多类型注意力（MD-MTA）方法。
2. 基于MDVRP预训练的迁移学习优势
TuneNSearch选择在更为复杂的MDVRP上进行预训练，而非传统的CVRP。实验发现，以此为基础模型，经过微调后，其在单仓库变体（如CVRP）上的表现与专门在CVRP上训练的模型相当；而在多仓库变体上，其性能则远超后者。例如，在100节点的多仓库问题上，TuneNSearch比在CVRP上预训练的模型性能高出44%。这证明了从复杂问题中学习到的知识更易于向简单问题迁移。
3. 局部搜索的显著提升作用
在神经网络推断出初始解后，集成的高效局部搜索算法被用于进一步优化。该算法使用了多种搜索算子。结果显示，这一步骤以很小的额外计算成本，带来了显著的性能提升，使得TuneNSearch在多个数据集上达到了神经网络方法中的最新领先水平。
4. 广泛的泛化与卓越的性能
TuneNSearch在CVRPLIB和TSPLIB的多个数据集上进行了测试。平均而言，其求解结果与文献中已知最优解的偏差不到3%。相比之下，其他神经网络方法的偏差在6%到25%之间，具体取决于问题的复杂程度。在数千个随机生成的实例上，对于100节点的各种VRP变体，TuneNSearch的平均相对性能偏差与高性能元启发式求解器PyVRP相比小于4%，而所需计算时间仅为后者的一小部分。这表明该方法在跨问题规模、跨实例分布和跨任务形式上都展现了强大的泛化能力。
结论与讨论
本研究的核心结论是，TuneNSearch成功地将迁移学习与局部搜索相结合，为解决多样化的车辆路径问题提供了一个高效、通用的框架。其重要意义体现在三个方面：
首先，在方法学上，它打破了神经网络模型通常局限于特定问题变体的桎梏。通过从复杂的MDVRP进行预训练，模型学习到了更丰富的特征表示，从而能够有效地适应包括单仓库和多仓库在内的各种VRP变体。
其次，在性能上，它通过集成局部搜索，弥补了纯神经网络方法在大规模实例上求解质量不足的缺点，使其性能能够与当前先进的元启发式算法（如PyVRP的混合遗传搜索）竞争，同时保持了神经网络固有的快速推理优势。
最后，在实践上，TuneNSearch为物流和供应链管理提供了强大的决策支持工具。企业无需为每个不同的路由场景开发和维护多个专用模型，从而可以节省大量的计算资源和人力资源，并能快速应对不断变化的路由条件或新出现的问题变体，具有显著的运营优势和经济效益。
总之，这项工作为神经组合优化领域提供了一条可行的路径，即通过结合机器学习与传统优化技术的优势，来开发既强大又灵活的求解器，为应对现实世界中复杂的优化挑战开辟了新的可能性。
