mlsanityData to 14 Oct 2026

EGAM: Extended Graph Attention Model for Solving Routing Problems

arXiv 2601.21281 ↗First posted 29 Jan 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Neural combinatorial optimization (NCO) solvers, implemented with graph neural networks (GNNs), have introduced new approaches for solving routing problems. Trained with reinforcement learning (RL), the state-of-the-art graph attention model (GAM) achieves near-optimal solutions without requiring expert knowledge or labeled data. In this work, we generalize the existing graph attention mechanism and propose the extended graph attention model (EGAM). Our model utilizes multi-head dot-product attention to update both node and edge embeddings, addressing the limitations of the conventional GAM, which considers only node features. We employ an autoregressive encoder-decoder architecture and train it with policy gradient algorithms that incorporate a specially designed baseline. Experiments show that EGAM matches or outperforms existing methods across various routing problems. Notably, the proposed model demonstrates exceptional performance on highly constrained problems, highlighting its efficiency in handling complex graph structures.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 42 of its 59 references that are in the map. First posted on arXiv 29 Jan 2026.

Builds on

42 of 59 references.

References · 42

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  4. 2020Denoising Diffusion Probabilistic Modelscited by 21,076
  5. 2017Graph Attention Networkscited by 8,923
  6. 2020End-to-End Object Detection with Transformerscited by 7,414
  7. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  8. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  9. 2016Instance Normalization: The Missing Ingredient for Fast Stylizationcited by 1,198
  10. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,026
  11. 2015Pointer Networkscited by 895
  12. 2021How Attentive are Graph Attention Networks?cited by 835
30 more
  1. 2018Attention, Learn to Solve Routing Problems!cited by 656
  2. 2020A Survey on Visual Transformercited by 654
  3. 2023A Comprehensive Overview of Large Language Modelscited by 648
  4. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  5. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  6. 2014Recurrent Models of Visual Attentioncited by 349
  7. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  8. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  9. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  10. 2024TimeXer: Empowering Transformers for Time Series Forecasting with Exogenous Variablescited by 248
  11. 2021Attention Mechanisms in Computer Vision: A Surveycited by 232
  12. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  13. 2016A Decomposable Attention Model for Natural Language Inferencecited by 215
  14. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  15. 2016Long Short-Term Memory-Networks for Machine Readingcited by 161
  16. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  17. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 131
  18. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  19. 2020Learning the Travelling Salesperson Problem Requires Rethinking Generalizationcited by 98
  20. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  21. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  22. 2021The Transformer Network for the Traveling Salesman Problemcited by 59
  23. 2024Body Transformer: Leveraging Robot Embodiment for Policy Learningcited by 32
  24. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  25. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  26. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  27. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  28. 2018Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networkscited by 22
  29. 2024GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costscited by 8
  30. 2024Neural Solver Selection for Combinatorial Optimizationcited by 5

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems
  2. 2026Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization
  3. 2025EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems
  4. 2024An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem
  5. 2026Two-Stage Learned Decomposition for Scalable Routing on Multigraphs
  6. 2025Vehicle Routing Problems via Quantum Graph Attention Network Deep Reinforcement Learning
  7. 2024Graph Q-Learning for Combinatorial Optimization
  8. 2026MViewRouter: Internalizing Geometric Equivariance via Multi-view Alternating Attention for Combinatorial Routing