.png){kind=icon}
Return
StructFormer: A Transformer-Based Multi-Structure Attention Model for Solving Routing Problems
.png){kind=icon}
PRE
AI
DOI：10.1109/tits.2026.3709289.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Vehicle Routing Problems (VRPs), fundamental NP-hard challenges in intelligent transportation systems, often pose scalability challenges and require expert-dependent design when solved with traditional heuristics. Neural VRP solvers offer data-driven alternatives but suffer from limitations such as the “averaging effect” in self-attention, which impairs key-node differentiation and the modeling of salient structural relationships. Existing feature enhancement methods also overlook key structural patterns, limiting representation quality. To address these challenges, we propose StructFormer, a transformer-based improvement solver with multiview structural attention. Its core Multi-StructAttn module integrates multiview structural embeddings to mitigate the averaging effect, enhancing node differentiation and capturing salient structural relationships. Additionally, a global-centrality-based feature enhancement module embeds optimal connection patterns, enriching structural representation. A novel decoder further incorporates search-state-dependent dynamic heuristic information to improve step-wise decision-making during iterative refinement. Experiments on diverse TSP and CVRP benchmarks demonstrate that StructFormer consistently outperforms state-of-the-art models. Furthermore, some modules of StructFormer are compatible with other learning-based solvers, offering significant performance gains on both TSP and CVRP.
Keywords:
Vehicle routing problems
deep reinforcement learning
averaging effect
node structural embeddings
feature enhancement
local search
Journal
IF:
8.4
Papers:
9.5K
Citations:
6.3W
Organization
View more organizations
Cited Papers
No cited papers available