Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
8-2025
Abstract
Recent neural heuristics for the Vehicle Routing Problem (VRP) primarily rely on node coordinates as input, which may be less effective in practical scenarios where real cost metrics--such as edge-based distances--are more relevant. To address this limitation, we introduce EFormer, an Edge-based Transformer model that uses edge as the sole input for VRPs. Our approach employs a precoder module with a mixed-score attention mechanism to convert edge information into temporary node embeddings. We also present a parallel encoding strategy characterized by a graph encoder and a node encoder, each responsible for processing graph and node embeddings in distinct feature spaces, respectively. This design yields a more comprehensive representation of the global relationships among edges. In the decoding phase, parallel context embedding and multi-query integration are used to compute separate attention mechanisms over the two encoded embeddings, facilitating efficient path construction. We train EFormer using reinforcement learning in an autoregressive manner. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) reveal that EFormer outperforms established baselines on synthetic datasets, including large-scale and diverse distributions. Moreover, EFormer demonstrates strong generalization on real-world instances from TSPLib and CVRPLib. These findings confirm the effectiveness of EFormer's core design in solving VRPs.
Discipline
Artificial Intelligence and Robotics
Research Areas
Intelligent Systems and Optimization
Areas of Excellence
Sustainability
Publication
IJCAI '25: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, Montreal, Canada, August 16-22
First Page
8582
Last Page
8590
Identifier
10.24963/ijcai.2025/954
Publisher
ACM
City or Country
New York
Citation
MENG, Dian; CAO, Zhiguang; WU, Yaoxin; HOU, Yaqing; GE, Hongwei; and ZHANG, Qiang.
EFormer: An effective edge-based transformer for vehicle routing problems. (2025). IJCAI '25: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, Montreal, Canada, August 16-22. 8582-8590.
Available at: https://ink.library.smu.edu.sg/sis_research/10557
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.24963/ijcai.2025/954