《Neurocomputing》：Heterogeneous graph neural networks for scalable asymmetric traveling salesman problem optimization
编辑推荐：
本文针对非对称旅行商问题（ATSP）中非欧几里得、非对称成本结构及现有图神经网络（GNN）可扩展性受限的挑战，提出了一种结合新型异构图线图（HL(G)）、关系感知GNN（Het-GAT）和遗憾引导优化（EB3O）的三阶段流水线。该研究通过将定向边转化为具有四种邻接类型的节点，有效保留非对称关系并降低图密度；利用Het-GAT学习边级遗憾值；并通过批量选择遗憾引导边构建启发式算法（BS-RG-EBH）与遗憾引导预评估3-Opt（RG-PE-3-Opt）进行路径构建与优化。实验表明，该方法在ATSP50上无需局部搜索即可达到91.88%的遗憾相关性和9.96%的最优性差距，在ATSP100-1000规模问题上较Nearest Neighbor + 2-Opt + Relocation（NN2R）平均差距降低29.0%，时间减少27.2%，且训练时间减少98%，训练数据仅需25%，显著优于GLOP和LKH-3，为实时物流优化提供了新方案。
在物流配送、路线规划等现实场景中，旅行商问题（Traveling Salesman Problem, TSP）的求解至关重要。然而，大多数研究聚焦于欧几里得TSP（Euclidean TSP, ETSP）或对称TSP（Symmetric TSP），其边成本是对称的，这与真实世界中存在单向道路、时间依赖通行成本等复杂情况的非对称旅行商问题（Asymmetric TSP, ATSP）相去甚远。ATSP的边成本依赖于方向，但其非欧几里得结构、非对称性以及现有图神经网络（Graph Neural Network, GNN）方法在处理方向依赖性上的不足，使其求解面临巨大挑战。传统求解器如LKH-3虽然对小规模ATSP有效，但在可扩展性和应对动态约束（如实时交通调整）方面表现不佳，而将ATSP转换为TSP的方法又会使得图规模翻倍，计算成本激增。现有GNN方法多针对对称或欧几里得环境设计，缺乏对方向依赖性的专门建模，难以直接应用于ATSP。
为解决上述问题，来自匈牙利厄特沃什·罗兰大学（ELTE E?tv?s Loránd University）人工智能系的Walid Guettala、ákos Levente Holló-Szabó、László Gulyás和János Botzheim在《Neurocomputing》上发表了一项研究，提出了一种全新的三阶段流水线框架，专门用于优化ATSP。该框架的核心创新在于引入了一种异构图线图（Heterogeneous Line Graph, HL(G)）来转换原始问题图，从而显式地保留和处理非对称关系。
研究人员开展此项研究，旨在克服当前GNN应用于ATSP时面临的三大障碍：非对称边需要专门的消息传递来建模方向依赖性、非欧几里得结构缺乏特征表示的几何约束，以及稠密邻接矩阵增加计算开销。他们的解决方案首先通过HL(G)将原始ATSP有向图中的边转化为节点，并通过四种明确的邻接类型（并行、源-源、源-目标、目标-目标）连接，在保留方向语义的同时将图密度降低了25%。接着，他们设计了异构图注意力网络（Het-GAT）来处理HL(G)，该网络使用关系特定的注意力机制，独立处理每种边类型的子图，然后通过求和、拼接或注意力机制融合关系信息，以预测每条边被纳入路径的“遗憾值”（即成本惩罚）。最后，他们提出了一个遗憾引导的优化阶段，结合了批量选择遗憾引导边构建启发式算法（Batch-Selecting Regret-Guided Edge Builder Heuristic, BS-RG-EBH）和遗憾引导预评估3-Opt（Regret-Guided Pre-Evaluating 3-Opt, RG-PE-3-Opt），共同称为EB3O，用于构建和优化路径。
为开展研究，作者主要应用了以下几项关键技术方法：1) 异构图线图变换：将ATSP有向图转换为包含四种边类型（并行、源-源、源-目标、目标-目标）的异构图线图（HL(G)）。2) 异构图注意力网络：设计Het-GAT模型，包含关系特定的图注意力层，分别处理HL(G)中的不同边类型子图，并采用三种融合策略（Concat, Sum, Attn）聚合信息，预测边级遗憾值。模型在ATSP50实例（2500个样本）上训练，使用Adam优化器和均方误差损失函数。3) 遗憾引导优化启发式算法：开发了EB3O流程，包括BS-RG-EBH用于基于预测遗憾值批量选择边构建初始路径，以及RG-PE-3-Opt用于局部优化，该过程针对高遗憾值边进行优化，避免无效子路径反转。对于大规模实例（如ATSP1000），采用子图覆盖推理策略，将大图分割成重叠的子图（如250个节点）分别处理后再合并结果。
4. 结果
4.1. 图变换与GNN架构的有效性
研究通过系统比较验证了HL(G)变换和Het-GAT架构的优越性。与传统的同质线图变换相比，HL(G)显式区分四种关系类型，能更有效地捕捉ATSP的非对称依赖性。在ATSP50上，Het-GAT-Concat模型仅使用GNN遗憾矩阵就达到了91.88%的遗憾相关性和9.96%的最优性差距。消融实验表明，四种关系类型均对性能有贡献，缺少任何一类都会导致性能下降。在聚合机制上，注意力（Attn）通常获得最低的优化差距，而拼接（Concat）在效率和精度之间取得了最佳平衡。
4.2. 与基线方法的比较
研究人员将提出的方法（Het-GAT-Concat-EB3O和Het-GAT-Attn-EB3O）与现有先进方法进行了比较，包括GLOP（Global and Local Optimization Policies）和经典的LKH-3启发式算法。在ATSP250上，Het-GAT-Concat-EB3O取得了8.34%的差距，显著优于GLOP的27.96%；在ATSP500上，差距为7.89%，远低于GLOP的38.96%。在运行时间方面，该方法也展现出巨大优势，在ATSP250和ATSP500上分别仅需0.75秒和7.20秒，而LKH-3则需要14.86秒和17.06秒，速度提升约86%。即使与使用类似GNN思想的MatNet相比，该方法在泛化到更大规模问题（如ATSP150以上）时也表现更优。
4.3. 遗憾引导优化的贡献
EB3O优化流程被证明比传统的最近邻加2-Opt加重定位（NN2R）策略更有效。 across ATSP100-1000问题规模，EB3O consistently lowers the final gap by 5.07–9.14% relative to NN2R。例如，在ATSP500上，Het-GAT-Concat-EB3O将差距从NN2R的17.03%降低到7.89%。同时，EB3O的启发式阶段运行时间也显著低于NN2R，体现了其高效性。
4.4. 可扩展性分析
通过子图覆盖推理策略，该方法成功扩展到1000个节点的ATSP实例。虽然在大规模问题上（ATSP1000）最优性差距有所增加（Het-GAT-Attn-EB3O为53.14%），但仍优于NN2R（58.94%），且运行时间远低于LKH-3（52.73秒 vs. 424.92秒），证明了该框架处理大规模问题的潜力。
5. 结论与意义
本研究成功开发并验证了一个用于高效求解非对称旅行商问题的三阶段神经组合优化框架。该框架的核心贡献在于：1）提出了异构图线图（HL(G)）变换，显式地对非对称关系进行建模，有效降低了计算复杂度；2）设计了关系感知的异构图注意力网络（Het-GAT），能够精准学习边级的遗憾值，为后续优化提供高质量引导；3）引入了高效的遗憾引导优化流程（EB3O），显著提升了路径构建和局部搜索的效率与效果。
实验结果表明，该框架在求解质量和计算效率方面均显著优于现有的主流方法（如GLOP、LKH-3、MatNet等），特别是在处理中大规模ATSP实例时优势明显。该方法仅需少量训练数据即可达到优异性能，降低了训练成本，并具备良好的可扩展性，能够通过子图推理处理超大规模问题。这项工作不仅为ATSP这一经典的组合优化难题提供了新的解决方案，也为将GNN应用于其他具有复杂约束和非对称结构的组合优化问题（如带时间窗的车辆路径问题、优先约束TSP等）提供了重要的方法论启示。其采用的关系感知建模思想和遗憾引导优化策略，有望在更广泛的物流、调度和网络优化领域发挥价值。
