EGAM: Extended Graph Attention Model for Solving Routing Problems
This work addresses routing problems for neural combinatorial optimization, offering an incremental improvement over prior graph attention models.
The paper tackled routing problems by proposing the Extended Graph Attention Model (EGAM), which generalizes graph attention to update both node and edge embeddings, and it matched or outperformed existing methods, showing exceptional performance on highly constrained problems.
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.