# GAMA: A Neural Neighborhood Search Method with Graph-aware Multi-modal Attention for Vehicle Routing Problem

arXiv: https://arxiv.org/abs/2511.07850 · HTML: https://mlsanity.com/paper/2511.07850/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 44 references that are in the map.
- First posted on arXiv 11 Nov 2025.

## Builds on (most cited first, 23 of 23)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [Efficient Neural Neighborhood Search for Pickup and Delivery Problems](https://mlsanity.com/paper/2204.11399/) (2022)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Cross-Problem Learning for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2404.11677/) (2024)
- [Neural Deconstruction Search for Vehicle Routing Problems](https://mlsanity.com/paper/2501.03715/) (2025)
- [Solve routing problems with a residual edge-graph attention neural network](https://mlsanity.com/paper/2105.02730/) (2021)
- [Learning from Offline and Online Experiences: A Hybrid Adaptive Operator Selection Framework](https://mlsanity.com/paper/2404.10252/) (2024)
- [Learning to Segment for Vehicle Routing Problems](https://mlsanity.com/paper/2507.01037/) (2025)
- [Edge-DIRECT: A Deep Reinforcement Learning-based Method for Solving Heterogeneous Electric Vehicle Routing Problem with Time Window Constraints](https://mlsanity.com/paper/2407.01615/) (2024)
- [Generalized Phase Pressure Control Enhanced Reinforcement Learning for Traffic Signal Control](https://mlsanity.com/paper/2503.20205/) (2025)

## Abstract (arXiv)

Recent advances in neural neighborhood search methods have shown potential in tackling Vehicle Routing Problems (VRPs). However, most existing approaches rely on simplistic state representations and fuse heterogeneous information via naive concatenation, limiting their ability to capture rich structural and semantic context. To address these limitations, we propose GAMA, a neural neighborhood search method with Graph-aware Multi-modal Attention model in VRP. GAMA encodes the problem instance and its evolving solution as distinct modalities using graph neural networks, and models their intra- and inter-modal interactions through stacked self- and cross-attention layers. A gated fusion mechanism further integrates the multi-modal representations into a structured state, enabling the policy to make informed and generalizable operator selection decisions. Extensive experiments conducted across various synthetic and benchmark instances demonstrate that the proposed algorithm GAMA significantly outperforms the recent neural baselines. Further ablation studies confirm that both the multi-modal attention mechanism and the gated fusion design play a key role in achieving the observed performance gains.