复杂路径问题的新范式：机器学习赋能旅行商与车辆路径求解综述

一、研究背景与问题提出

近年来，运筹学（Operations Research，OR）与计算机科学（Computer Science，CS）日益交融，特别是机器学习（ML）技术的发展为运筹领域带来了新的可能。传统OR通过数学建模与优化技术解决交通与物流难题，但在面对大规模、复杂路由问题时常因计算成本过高而受限。ML 的到来使得模型能够从数据中学习、适应动态环境，但目前在优化问题的应用仍然不足。为填补这一研究空白，论文针对两类典型路由问题——旅行商问题（TSP）与车辆路径问题（VRP）展开梳理。

• TSP 要求给定城市集合，寻找一条经过所有城市且只访问一次的闭合回路，目标是最小化总行程距离。在欧几里得对称距离假设下，TSP 可视为完全图上寻找最短汉密尔顿回路的 NP 难问题；其变体包括时间窗、奖惩收集和巡游类问题。
• VRP 是 TSP 的推广，涉及多辆车从仓库出发服务若干客户，每个客户有固定需求。目标是确定车辆路线使得所有需求得到满足且总成本最小。常见变体有容量限制（CVRP）、配送与取货（PDP）、时间窗（VRPTW）、拆分配送等。
• 两个问题均为 NP 难，传统精确算法如分支定界仅能解决小规模实例，启发式算法（如k‑opt、Lin‑Kernighan）提供近似解，但缺乏保证。因此，利用 ML 构建高质量且具一般性的路由求解器成为新趋势。

本文综述了 2016‑2025 年 253 篇相关论文，构建了机器学习在路由问题中的分类体系，评估不同方法的优势与局限，并提出标准化的基准测试建议与未来研究议程。

二、机器学习基础

2.1 神经网络架构

为理解后续方法，论文先介绍常见神经网络（NN）架构：

• 多层感知机（MLP）：由多层线性变换和非线性激活组成，用于小规模决策或函数逼近。
• 图神经网络（GNN）：专门处理图结构数据，通过聚合邻居节点特征生成节点表示，适用于路由问题等图形结构。变体包括图注意网络（GAT）和图卷积网络（GCN）等。
• 循环神经网络（RNN）：处理序列数据，利用隐藏状态记忆历史信息，变体 LSTM 有效缓解梯度消失。
• Transformer：使用注意力机制并行处理序列，可与 GNN 组合用于编码城市或客户位置。Transformer 模型参数较多，需要大量数据训练。

2.2 学习范式

论文总结了三种学习范式：

• 监督学习（SL）：需要真实标签，适合小规模问题，模型根据输入输出差异更新参数。在路由中可用来预测最短路径的边，但获取高质量标签困难且计算代价高。
• 无监督学习（USL）：无须标签，通过聚类或自定义损失自动发现结构，可用于划分城市群进行“分而治之”的策略。
• 强化学习（RL）：智能体通过与环境交互学习策略，奖励通常与行程长度或成本相关。RL 不需要标签，适用于包含复杂约束的大规模路由问题，但训练耗时且需平衡探索与利用。

多数研究采用 SL 或 RL，USL 常作为辅助模块，例如用于城市聚类。

三、机器学习在路由问题中的方法分类

作者提出了一套结构化的分类体系，将 ML 方法划分为构造型与改进型，并根据使用的学习技术区分纯 ML 和混合方法。

3.1 构造型方法

构造型方法从无到有生成解决方案，分为增量式和一次性两种。

3.1.1 增量式方法

• 流程：模型从部分解出发，每次选择下一个城市，不断扩展直到构成完整路线。这类方法通常由编码器与解码器组成：编码器为每个城市生成特征嵌入，并根据已访问城市的嵌入生成部分解表示；解码器据此选择下一个访问的城市。
• 优点：易与强化学习结合，能够逐步考虑约束，例如防止重复访问或超出车辆容量。
• 局限：训练需要大量计算资源；模型推断速度虽快，但可能受限于训练规模。

下图展示增量式方法在 TSP 中构造解的过程：不同颜色表示当前路径及待扩展的候选边（图中绿色边表示选择的下一个城市）。

下图展示增量式方法：

3.1.2 一次性方法

• 流程：训练的神经网络一次生成中间结果（如概率热图），再由传统搜索算法生成完整路线。热图表示从城市i到城市j的转移概率，中间输出引导搜索算法更快地找到高质量解。
• 优点：推断阶段无需多次调用神经网络，训练可通过监督学习进行。
• 局限：需大量准确标签；推断需与搜索算法结合，整体速度受限；难处理复杂约束。

下图展示一次性方法中输入图、输出热图以及最终解的关系，颜色深浅表示边的选择概率。

3.2 改进型方法

改进型方法在一个有效初始解的基础上进行改进，包括启发式方法、子问题法和基于精确算法的方法。

3.2.1 启发式方法

• 思路：在现有解中使用启发式规则（如 k‑opt）删除并替换若干边，提高解的质量。2‑opt 方法每次删除两条边并连接新的边形成更短回路，可以迭代应用直至收敛。
• 机器学习作用：模型学习删除和添加边的规则，从而指导改进过程。

下图展示基于 k‑opt 的启发式操作流程：选择边、删除、添加并形成新解。

3.2.2 子问题法

• 思路：在大规模实例中选择一部分子路径或子线路进行重新优化，然后替换原解中的相应部分。这特别适用于 CVRP 等含有多条子路线的问题。
• 机器学习作用：可以学习如何选择子问题或优化子问题的策略。

下图展示了子问题法在 VRP 和 TSP 中的示意：不同颜色的子路线被选中并重新优化后重新组合。

3.2.3 基于精确算法的方法

• 核心：将 ML 嵌入精确算法，如分支定界、列生成或商业求解器，通过预测变量顺序、调整分支策略或生成初始解来减少搜索空间。
• 特点：兼具构造和改进特性，可用于指导精确算法优先探索更有希望的分支，从而提高求解效率。

3.3 方法比较

作者总结了各类方法的优缺点：一次性方法需要昂贵标签且推断慢；增量式方法易融入 RL 并能直接生成解，但训练资源消耗大；启发式/子问题法适用于大规模或特定结构问题，可获得高质量解但代价较高。

四、机器学习方法实践综述

为了展现不同方法在 TSP 和 CVRP 中的应用，论文对近十年研究进行了详细梳理。以下仅总结部分代表性工作及其亮点。

4.1 增量式方法

• Pointer Network（Vinyals et al., 2017）与 Bello et al., 2017 率先利用 RNN+ 注意力机制迭代输出城市序列，使用策略梯度训练。
• Nazari et al., 2018 将 CVRP 客户需求和位置信息编码后输入 LSTM，通过注意力选择下一客户，首创 CVRP 增量 RL 框架。
• Kool et al., 2019; Kwon et al., 2020 采用 Transformer 编码器与注意力解码器，使用策略梯度和轨迹平衡训练，引入批量归纳目标实现高效训练。
• Ling et al., 2023; Jiang et al., 2022 结合 CNN 或 GCN 对图进行编码，改进模型的普适性和对非均匀分布的泛化。

4.2 一次性方法

• Joshi et al., 2019 使用 GNN 预测 TSP 边选择概率，通过蒸馏策略引导搜索算法；Min et al., 2023 结合 GNN 和搜索，实现 TSP100 零误差，并能推广到更大规模。
• Cvitanić et al., 2021 将深度图学习用于 CVRP 一次性求解，引入动态图卷积估计边权热图。
• 大型实例推广：Fu et al., 2021 使用分而治之策略将大实例拆分成模型熟悉的规模求解，随后合并整体解。

4.3 启发式和子问题法

• NeuRewriter（Chen & Tian, 2019）结合区域选择与规则选择网络，使用 RL 学习在 TSP 上执行局部改进的顺序。
• Lu et al., 2020 将 Transformer 编码器与 MLP 解码器应用于 CVRP 的 k‑opt 改进，所获解优于传统 LKH 启发式。
• Kim et al., 2021 通过 Transformer 选择 VRP 子路线并对选中子图进行优化，实现大规模 CVRP 的改进。
• Cheng et al., 2023 结合子问题法与 Transformer，在 TSP500 上实现较小的最优差距。

4.4 精确算法与混合方法

研究将 ML 与精确算法结合，改善分支顺序或列生成过程：

• ML 辅助列生成：学习定价问题的变量顺序，减少迭代次数。
• ML 预解初始化：先用增量式模型生成高质量初始解，再交给精确求解器进一步优化。

4.5 实际应用与扩展

论文还调查了除 TSP/CVRP 外的实践研究，并基于问题特征（异构车队、时间窗、电动车、电网耦合、协同配送、时变和随机性等）分类。这些研究显示 ML 在即时调度、电动车充电优化、多式联运协同等场景的潜力，并强调与传统算法结合的重要性。

五、性能评估与比较

文章对 ML 方法与 OR 算法及启发式算法的性能进行对比。为了公平评估，作者建议使用最佳解差距和相对偏差等指标，并提供了计算公式：

当存在精确或公认的基准解时，最优差距定义为

当仅有近似解时，相对偏差定义为

作者强调近似解仅作为折衷，必须谨慎解读。

对运行效率的评估不应只看绝对时间，而要采用标准化运行时间和可扩展性因子：

其中参考算法通常选择LKH等公认算法。

此外，作者建议标准化实验设置，包括一致的问题规模、明确的约束条件、报告硬件与训练资源、模型参数量以及推理时间，以便公平比较。

通过上述指标与实践比较，论文总结：

• 对于 TSP100 及 TSP500 等中等规模问题，最新 GNN/Transformer‑RL 模型能达到零或很小的最优差距，并具有秒级至分钟级运行时间；
• 传统精确算法如 Concorde 在小规模实例上仍然最优，但在大规模或非标准问题上计算时间长；
• 启发式算法如 LKH3 在许多实例上是坚实的基准，ML 方法常以此为参照；
• 对于 CVRP 等带容量约束问题，ML 模型在 100 节点规模上接近甚至超越传统启发式，展示了潜力。

六、数据生成与一般化挑战

6.1 数据获取

大多数 ML 路由框架依赖于合成数据，通常在单位正方形上均匀随机采样坐标，然后计算欧式距离。然而这样的分布与现实世界相差甚远，导致模型泛化能力差。 为此，作者提出了一种更真实的数据生成器：

1. 在单位正方形内随机采样节点；
2. 应用爆炸、收缩、聚类、扩展、压缩、线性投影、网格等十个突变算子，使坐标呈现聚类、线状或网格分布。
3. 使用这些实例训练模型，可提高对现实分布的适应性。

下图展示该生成器产生的三种 100 节点实例：分别呈现网格状、随机聚类与线性聚类。

6.2 探索–利用与泛化难题

论文指出，强化学习需平衡探索与利用。常用的ε‑贪婪策略在稀疏奖励环境中易陷入局部最优，策略梯度方法虽具内在随机性，但需良好调参。神经架构搜索、生成对抗网络等在寻找新架构或新分布时也面临模式坍塌等问题。 此外，合成数据与真实数据分布差异显著，过度依赖均匀数据会导致模型在实际应用中表现不佳。作者建议开发更贴近现实的生成器，并将其与实际数据结合，构建统一的基准数据集。

其它挑战包括：

• 尺寸泛化：让模型适应不同规模问题，可采用分而治之策略或设计可伸缩网络；
• 跨问题泛化：将模型从 TSP 推广到 CVRP 甚至其他组合优化问题仍处于探索阶段。

七、基准测试与标准化建议

作者指出，ML 路由研究缺乏统一的评测标准。为了确保结果的可比性和 reproducibility，应遵循以下建议：

• 明确基准：小规模问题使用精确解（如 Gurobi），大规模问题使用公认启发式（如 LKH）作为基准。
• 规范评估指标：使用最优差距、相对偏差、标准化运行时间和可扩展因子等指标统一衡量。
• 标准实验设置：统一问题规模、约束描述，报告硬件环境、参数数量、内存占用、训练数据量和训练/推理时间。
• 合理选择数据集与算法：根据问题规模选择 TSPLib、CVRPLib、Solomon 等数据集；对小规模问题采用精确求解器，对中等规模使用 LKH 等启发式，对大规模问题可以采用 Pointer Network 或注意力模型。

这些标准化建议有助于提升研究透明度、比较不同方法的效率，并促进社区协作。

八、未来研究议程

论文以联合国可持续发展目标（SDGs）为导向，提出多项优先研究方向，强调将经济、环境与社会视角引入 ML‑OR 交叉领域。

8.1 弹性与稳健性

• 开发适应性强的路由系统，使其在环境变化和不确定性下仍能运行，通过数据驱动的随机优化、稳健优化或分布鲁棒优化实现。
• 平衡保守性与计算复杂度，可以探索深度学习与分布式算法融合，甚至利用量子技术加速求解。

8.2 跨领域与多目标方法

• 拓展研究对象到非均匀和非欧几里得距离问题，解决实际场景中距离不对称的问题。
• 处理多目标优化（如排放与服务水平），结合演化算法、博弈论等学习相互合作的策略。
• 推动协同配送与多式联运，例如卡车‑无人机协同等，以降低成本和能源消耗。

8.3 气候中和与新能源

• 在 EV 路由中考虑充电行为、能耗模型和电网耦合，研究如何平衡车队效率与电网稳定。
• 探索用太阳能、风能驱动的充电设施及氢燃料、电动船舶等多种新能源模式。
• 建立智能充电基础设施，利用 AI 和物联网动态调整充电策略。

8.4 人本与环境友好

• 利用实时传感和 IoT 数据动态调整路线，实现对交通和环境条件的快速响应。
• 引入人本物流概念，兼顾驾驶员舒适性和客户个性化需求。

8.5 新型智能与社会合规

• 大型语言模型（LLM）已在解决 TSP 等问题上初露端倪，未来可能通过直接生成解或超启发式进一步提升性能。
• 强调结合 ML 与经典优化算法，开发可解释且适合边缘部署的轻量模型，以应对实时和资源受限场景。
• 重视伦理和隐私问题，采用差分隐私、数据匿名化等技术保护用户数据，确保模型在动态环境中安全可靠运行。
• 发展安全验证与对抗鲁棒性方法，保障自动驾驶和紧急调度等高风险应用的可靠性。

九、结论与启示

综述的主要贡献在于：

• 构建全面的分类体系：将机器学习路由方法划分为构造型（增量式与一次性）和改进型（启发式、子问题、精确算法混合）。这一分类帮助研究者理解不同技术的适用场景与优势。
• 梳理典型研究与性能比较：总结了近十年主要工作，说明 ML 方法在中等规模 TSP/CVRP 上已接近精确解，具备较快推断速度，但仍需解决训练资源与泛化问题。
• 提出基准测试与数据生成建议：强调使用标准化评测指标（最优差距、相对偏差、标准化运行时间等），发布更真实的训练数据生成器，呼吁构建统一基准数据集。
• 设定未来研究议程：围绕可持续发展目标提出弹性与稳健性、跨领域与多目标、气候中和、以人为本、社会合规等研究方向，为社区提供行动指南。

总之，机器学习为解决复杂路由问题提供了强大的工具，但其成功依赖于真实数据、多目标平衡、合理的评测框架和人本、伦理视角。未来研究需要在理论创新与实践应用之间架起桥梁，使 ML 驱动的路由优化更好地服务于可持续发展与社会需求。