StructFormer: A Transformer-Based Multi-Structure Attention Model for Solving Routing Problems

doi:10.1109/tits.2026.3709289

StructFormer: A Transformer-Based Multi-Structure Attention Model for Solving Routing Problems

2026-07-10

0

PRE

AI

DOI：10.1109/tits.2026.3709289

原文链接

原文求助

摘要

En 中文

车辆路径问题（VRPs），作为智能交通系统中的基础NP难挑战，在采用传统启发式算法求解时，常面临可扩展性挑战并需要依赖专家设计。神经VRP求解器提供数据驱动替代方案，但受限于自注意力机制中的“平均效应”，损害了关键节点区分和显著结构关系的建模。现有特征增强方法也忽视了关键结构模式，限制了表示质量。为解决这些挑战，我们提出StructFormer，一种基于Transformer的改进求解器，具有多视图结构注意力机制。其核心Multi-StructAttn模块通过整合多视图结构嵌入来缓解平均效应，增强节点区分并捕捉显著结构关系。此外，一个基于全局中心性的特征增强模块嵌入最优连接模式，丰富结构表示。一种新颖的解码器进一步整合了搜索状态依赖的动态启发式信息，以改进迭代优化过程中的逐步决策。在多种TSP和CVRP基准上的实验表明，StructFormer持续优于当前最优模型。此外，StructFormer的部分模块与其他学习型求解器兼容，在TSP和CVRP上均带来显著的性能提升。

Keyword:

Vehicle routing problems

deep reinforcement learning

averaging effect

node structural embeddings

feature enhancement

local search

StructFormer: A Transformer-Based Multi-Structure Attention Model for Solving Routing Problems

摘要

期刊

机构