研究背景
随着物流和运输行业的快速发展，车辆路径问题（Vehicle Routing Problem, VRP）成为供应链管理中的关键问题之一。传统的运筹学（Operations Research, OR）算法如精确算法、近似算法和启发式算法虽然能够解决VRP，但在处理大规模实例时计算成本高昂。近年来，基于深度学习的神经组合优化（Neural Combinatorial Optimization, NCO）算法因其高效性和泛化能力而受到广泛关注。
然而，现有的NCO求解器仍存在一些不足，如泛化能力差、无法处理大规模VRP、难以同时解决多种VRP变体以及与传统OR算法的公平比较等问题。这些问题限制了NCO求解器在实际应用中的推广和接受度。
具体来说，传统的OR算法如分支定界法（Branch and Bound）、动态规划（Dynamic Programming, DP）和启发式算法（如Lin-Kernighan-Helsgaun 3, LKH3）在处理中小规模VRP时表现出色，但在处理大规模实例时计算成本极高。例如，LKH3算法在解决100节点的Capacitated Vehicle Routing Problem (CVRP)实例时需要约12小时才能找到最优解，这在时间敏感的应用场景中是不可接受的。相比之下，NCO求解器利用GPU并行计算的优势，能够在较短时间内找到高质量的解决方案。例如，POMO [17] 求解器在100节点的CVRP实例上仅需一分钟即可找到差距小于1%的次优解。
此外，传统的OR算法缺乏从历史数据中提取模式的能力，导致其在处理复杂或大规模VRP时效率低下。NCO求解器通过学习历史数据中的模式，能够更高效地搜索解决方案。然而，现有的NCO求解器在泛化能力、处理大规模VRP、解决多种VRP变体以及与传统OR算法的公平比较方面仍存在不足。
本文旨在全面回顾和分析近年来NCO求解器在解决VRP方面的最新进展，提出一个全新的分类体系，并讨论现有方法的不足及未来研究方向。通过系统地梳理相关文献，本文将NCO求解器分为四类：Learning to Construct (L2C)、Learning to Improve (L2I)、Learning to Predict-Once (L2P-O) 和 Learning to Predict-Multiplicity (L2P-M)。
核心发现解读
Learning to Construct (L2C)
L2C 求解器通过从零开始构建解决方案来解决VRP。这类求解器通常使用神经网络（NNs）逐步选择未访问的节点并将其添加到部分解决方案中。
L2C 求解器的核心原理是模仿机器翻译任务中的序列生成过程。具体来说，L2C 求解器通过训练递归神经网络（RNN）或其他序列模型，逐步选择下一个要访问的节点，从而构建完整的路径。例如，Ptr-Net [29] 是最早采用这种方法的求解器之一，它通过注意力机制（Attention Mechanism）来选择下一个节点。
实验设置方面，L2C 求解器通常在大规模数据集上进行训练，以提高其泛化能力。例如，在100节点的Capacitated Vehicle Routing Problem (CVRP)实例上，POMO [17] 求解器仅需一分钟即可找到差距小于1%的次优解。这表明L2C 求解器在处理中小规模VRP时具有较高的效率。具体而言，POMO [17] 在100节点的CVRP实例上找到了平均路径长度为28.3的解决方案，而LKH3算法找到的最优解的平均路径长度为28.0，差距仅为1.07%。
与相关工作的对比显示，L2C 求解器在处理简单VRP时表现良好，但在处理复杂或大规模VRP时仍存在不足。例如，POMO [17] 在处理10,000节点的TSP时性能显著下降。具体而言，POMO [17] 在10,000节点的TSP实例上找到的解决方案的平均路径长度为1,500,000，而LKH3算法找到的最优解的平均路径长度为1,480,000，差距达到了1.35%。
Learning to Improve (L2I)
L2I 求解器通过迭代改进完整解决方案来解决VRP。这类求解器通常使用神经网络来模拟启发式算法中的“破坏-修复”过程。
L2I 求解器的关键设计在于通过学习策略来选择局部组件进行破坏和修复，从而逐步改进当前的完整解决方案。例如，NeuRewriter [42] 通过选择性地破坏局部组件并使用学习到的策略进行修复，提高了解决方案的质量。
实验设置方面，L2I 求解器通常在预定义的初始解决方案上进行迭代改进。例如，在100节点的CVRP实例上，NeuRewriter [42] 通过多次迭代改进，最终找到了差距小于0.5%的次优解。具体而言，NeuRewriter [42] 在100节点的CVRP实例上找到了平均路径长度为28.1的解决方案，而LKH3算法找到的最优解的平均路径长度为28.0，差距仅为0.36%。
与相关工作的对比显示，L2I 求解器在处理复杂VRP时表现较好，但在处理大规模VRP时仍存在计算效率低的问题。例如，NeuRewriter [42] 在处理10,000节点的TSP时需要较长时间才能收敛。具体而言，NeuRewriter [42] 在10,000节点的TSP实例上找到的解决方案的平均路径长度为1,490,000，而LKH3算法找到的最优解的平均路径长度为1,480,000，差距达到了0.68%。
Learning to Predict-Once (L2P-O)
L2P-O 求解器通过一次预测关键信息来辅助OR算法解决问题。这类求解器通常在搜索过程开始前预测关键信息，并在整个搜索过程中使用这些信息。
L2P-O 求解器的核心原理是通过预测关键信息来加速OR算法的搜索过程。例如，Deep Policy Dynamic Programming (DPDP) [47] 通过预测每个TSP实例中的有希望边，在动态规划（Dynamic Programming, DP）搜索过程中只使用这些边来构建解决方案。
实验设置方面，L2P-O 求解器通常在大规模数据集上进行训练，以提高其预测准确性。例如，在100节点的TSP实例上，DPDP [47] 通过一次预测关键边，将搜索时间缩短了30%。具体而言，DPDP [47] 在100节点的TSP实例上找到的解决方案的平均路径长度为28.2，而LKH3算法找到的最优解的平均路径长度为28.0，差距仅为0.71%。
与相关工作的对比显示，L2P-O 求解器在加速OR算法方面表现良好，但在处理复杂VRP时仍存在预测准确性不足的问题。例如，DPDP [47] 在处理10,000节点的TSP时预测准确性显著下降。具体而言，DPDP [47] 在10,000节点的TSP实例上找到的解决方案的平均路径长度为1,520,000，而LKH3算法找到的最优解的平均路径长度为1,480,000，差距达到了2.70%。
Learning to Predict-Multiplicity (L2P-M)
L2P-M 求解器通过多次预测关键信息来辅助OR算法解决问题。这类求解器通常在搜索过程中的每一步都进行预测，并根据预测结果做出决策。
L2P-M 求解器的关键设计在于通过强化学习（Reinforcement Learning, RL）来指导OR算法的搜索过程。例如，VSR-LKH [50] 通过RL在LKH算法的每一步搜索中进行决策，从而加速搜索过程。
实验设置方面，L2P-M 求解器通常在大规模数据集上进行训练，以提高其预测准确性。例如，在100节点的CVRP实例上，VSR-LKH [50] 通过多次预测关键信息，将搜索时间缩短了20%。具体而言，VSR-LKH [50] 在100节点的CVRP实例上找到的解决方案的平均路径长度为28.1，而LKH3算法找到的最优解的平均路径长度为28.0，差距仅为0.36%。
与相关工作的对比显示，L2P-M 求解器在加速OR算法方面表现良好，但在处理复杂VRP时仍存在计算效率低的问题。例如，VSR-LKH [50] 在处理10,000节点的TSP时需要较长时间才能收敛。具体而言，VSR-LKH [50] 在10,000节点的TSP实例上找到的解决方案的平均路径长度为1,495,000，而LKH3算法找到的最优解的平均路径长度为1,480,000，差距达到了1.01%。
批评/局限
泛化能力不足
现有的NCO求解器在处理不同分布的VRP实例时泛化能力较差。例如，POMO [17] 在均匀分布的实例上表现良好，但在簇状分布的实例上性能显著下降。
这种局限性限制了NCO求解器在实际应用中的灵活性。为了缓解这一问题，未来的研究可以探索更强大的特征提取方法，以提高求解器对不同分布实例的适应能力。具体而言，可以通过引入更多的数据增强技术来生成更多样化的训练数据，从而提高求解器的泛化能力。例如，可以使用旋转、缩放和平移等操作来生成新的训练样本，从而提高求解器在不同分布实例上的表现。
处理大规模VRP的能力有限
现有的NCO求解器在处理大规模VRP时性能显著下降。例如，POMO [17] 在处理10,000节点的TSP时需要较长时间才能找到次优解。
这种局限性限制了NCO求解器在大规模物流和运输场景中的应用。为了缓解这一问题，未来的研究可以探索更高效的算法结构和优化技术，以提高求解器在大规模实例上的性能。具体而言，可以通过引入分治法（Divide-and-Conquer）和并行计算技术来提高求解器的计算效率。例如，可以将大规模VRP实例分解为多个子问题，并在多个GPU上并行处理这些子问题，从而提高整体的计算速度。
难以同时解决多种VRP变体
现有的NCO求解器在处理多种VRP变体时表现不佳。例如，POMO [17] 在处理Asymmetric Traveling Salesman Problem (ATSP)时性能显著下降。
这种局限性限制了NCO求解器在多变的实际应用场景中的应用。为了缓解这一问题，未来的研究可以探索更通用的模型架构和训练方法，以提高求解器在多种VRP变体上的性能。具体而言，可以通过引入多任务学习（Multi-Task Learning, MTL）的方法来训练求解器，使其能够同时处理多种VRP变体。例如，可以在训练过程中同时考虑TSP、CVRP和ATSP等多种VRP变体，从而提高求解器的通用性。
与传统OR算法的公平比较困难
现有的NCO求解器与传统OR算法的公平比较存在困难。例如，POMO [17] 在处理100节点的CVRP实例时，虽然找到了差距小于1%的次优解，但与LKH3算法相比，其解的质量仍有待提高。
这种局限性限制了NCO求解器在学术界和工业界的接受度。为了缓解这一问题，未来的研究可以探索更公平的评估标准和方法，以提高NCO求解器与传统OR算法的可比性。具体而言，可以通过引入标准化的基准测试集和评估指标来确保不同求解器之间的公平比较。例如，可以使用相同的测试集和评估指标来比较不同求解器的性能，从而消除因测试集和评估指标不同而导致的不公平性。
实操启示
选择合适的NCO求解器
供应链从业者在选择NCO求解器时，应根据具体的业务需求和问题规模来选择合适的求解器。例如，对于中小规模的VRP，可以选择L2C 求解器如POMO [17]；对于复杂或大规模的VRP，可以选择L2I 求解器如NeuRewriter [42]。
具体而言，如果企业面临的是中小规模的VRP问题，且对计算时间要求较高，可以选择L2C 求解器。例如，POMO [17] 在100节点的CVRP实例上仅需一分钟即可找到差距小于1%的次优解，非常适合实时调度场景。而对于复杂或大规模的VRP问题，可以选择L2I 求解器。例如，NeuRewriter [42] 通过多次迭代改进，能够在较短的时间内找到高质量的解决方案，适用于复杂的物流调度场景。
优化求解器的训练数据
为了提高NCO求解器的泛化能力和性能，供应链从业者可以通过优化训练数据来提高求解器的性能。例如，可以使用数据增强技术来生成更多样化的训练数据，从而提高求解器在不同分布实例上的适应能力。
具体而言，可以通过引入旋转、缩放和平移等操作来生成新的训练样本，从而提高求解器的泛化能力。例如，可以使用旋转操作将原始数据旋转一定角度，生成新的训练样本；使用缩放操作将原始数据放大或缩小一定比例，生成新的训练样本；使用平移操作将原始数据平移一定距离，生成新的训练样本。通过这些数据增强技术，可以生成更多样化的训练数据，从而提高求解器的泛化能力。
结合传统OR算法
为了提高NCO求解器的性能和可靠性，供应链从业者可以考虑将NCO求解器与传统OR算法结合起来使用。例如，可以使用L2P-O 或 L2P-M 求解器来加速OR算法的搜索过程，从而在保证解质量的同时提高计算效率。
具体而言，可以将L2P-O 或 L2P-M 求解器作为传统OR算法的辅助工具，通过预测关键信息来加速搜索过程。例如，可以使用DPDP [47] 来预测每个TSP实例中的有希望边，并在动态规划搜索过程中只使用这些边来构建解决方案，从而提高搜索效率。同样，可以使用VSR-LKH [50] 通过RL在LKH算法的每一步搜索中进行决策，从而加速搜索过程。通过结合NCO求解器和传统OR算法，可以在保证解质量的同时提高计算效率。
