4.1.1 路径规划问题
路径规划问题（Routing Problem）是一类受到广泛关注的组合优化问题，旨在满足一定约束的情况下，寻找从源节点到目标节点的最优路径。旅行商问题（Traveling Salesman Problem，TSP）、汽车路由问题（Vehicle Routing Problems，VRP）均为典型的路径规划问题。求解路径规划问题的传统启发式算法往往基于局部搜索技术，求解一个实例往往需要较长的时间，无法满足实际应用场景中的效率要求。基于图学习方法求解路径规划问题，挑战在于图学习方法需要设计和训练模型来处理大量可能的路径组合。另外，路径的顺序影响着求解的质量。因此，在图学习过程中，需要在处理图结构时采用特殊的策略模拟路径的先后顺序选择。路径规划问题需要在全局层面找到问题的解，而不仅仅是在局部找到较好的解决方案。如何寻找问题的全局结构是一个挑战，因为大多数图神经网络都基于邻域信息聚合，可能无法有效的捕捉全局结构信息。
路径规划问题的直接求解思路是利用端到端学习方法进行训练
求解。为了克服端到端学习方法中的路径规划节点顺序问题，Kool 等人[2] 提出了一种基于图注意力机制的模型，来学习 TSP 问题节点序列之间的公共模式，并基于训练得到的特征构造路径解。Chen 等人[3]提出了一种称为 NeuRewriter 的方法，通过深度图神经网络学习重写当前路径解的局部模块，改进路径选择过程。NeuRewriter 可以分解为 region-picking 和 rule-picking 两个模块，每个模块由 actor-critic 方法分别进行训练，分别负责路径规划中的路径顺序选择和路径重新规划决策。Lu 等人[4] 提出一种新的学习方法（L2I）。基于一个随机初始解，L2I 从一系列由图编码特征预训练得到的运算符中进行选择，通过选定的最优运算符改进路径顺序。尽管上述路径规划训练方法考虑了节点选择的先后顺序特征，但训练过程缺乏有效的搜索策略，这也导致这些方法在路径规划问题上的求解质量难以保证。
为了进一步提高路径规划问题的求解质量，Fu 等人[5] 考虑首先在子图中训练一个小规模神经网络模型，然后利用图采样、图转换和图合并等技术构建完整图的热力图。基于合成得到的热力图，通过蒙特卡洛树搜索获得高质量路径解。Jin 等人[6] 提出了一种基于多指针 Transformer 的端到端图深度学习方法（Pointerformer）。通过可逆残差网络和多指针网络，Pointerformer 有效的控制了编码器-解码器架构的内存消耗。同时，Pointerformer 通过引入特征增强和上下文增强方法，可以获取更优的搜索决策，从而提升了路径解的质量。
虽然图神经网络算法的计算速度优势明显，但其求解路径规划问题的质量相对于传统启发式搜索方法仍有很大的提升空间。为了结合二者的优势，人们提出利用图神经网络指导传统启发式搜索共同改进路径规划解的质量。Hottung 等人[7] 基于注意力深度图神经网络，提出了一种新的邻域搜索框架求解车辆路径规划问题，并通过更广泛邻域信息的学习来指导搜索算法的求解过程。Delarue 等人[8] 设计了基于值函数的深度图卷积网络框架，将搜索过程的动作选择问题建模为
混合整数优化问题，并通过启发式搜索算法进行改进。Hottung 等人
[9] 使用了条件变分自编码器，学习如何将潜在搜索空间中的点映射到特定实例的图编码特征中，并通过无约束连续优化方法对所学习的图特征进行导向性搜索。
利用图神经网络指导传统启发式搜索的图学习方法在求解速度和求解质量上相较于传统启发式方法有了很大的提升。然而，由于大规模图神经网络具有较高的计算复杂性，大规模路径规划问题实例的搜索空间庞大，这些方法只能够依赖于小规模图神经网对生成实例小样本进行训练。为了提高问题求解泛化能力，人们尝试用 Transformer、多阶段学习等方法进行改进。Li 等人[10] 提出了在图神经网络中引入一种基于 Transformer 模型的局部搜索框架，利用空间局部性原理从原始指数级解空间中选择线性数量的子问题，最终调用启发式求解器来迭代优化路径解，提高了求解大规模路径规划实例的能力。Choo 等人[11] 提出在图神经网络中引入模拟引导的束搜索算法，在固定宽度的树搜索中识别候选解，减小了问题的搜索空间，提高了问题求解的泛化能力。Hou 等人[12] 提出两阶段划分方法，对 VRP 问题子路径序列进行编码。在求解过程中首先根据子路径编码将大实例划分为小实例，通过调用传统启发式算法进行求解，提升了问题的求解效率和求解能力。
尽管基于端到端的学习方法可以有效求解路径规划问题，但它需要大量的训练数据生成和计算资源来对模型进行预训练。路径规划问题的另一种求解方法是利用决策配置学习方法进行求解。在决策配置学习方法中，训练模型将学习图实例的抽象特征并直接学习算法决策的重要性，进而获得较好的求解决策。Xin 等人[13] 设计了一种多解码器注意力模型（MDAM）对路径序列特征进行学习，获得了问题求解的自主决策。Joshi 等人[14] 使用图卷积网络学习节点与边特征的重要性，随后使用高度并行化的集束搜索（Beam search）算法生成路径
解，并在配置学习过程中不断改进启发式算法的决策搜索效率。Kool等人[15] 将机器学习算法与动态规划算法的优势相结合，提出了 DPDP 方法。具体来说，DPDP 训练一个深度神经网络对实例中的边进行打分，并基于网络打分结果减少动态规划算法决策状态空间，以提高求解速度与求解质量。