A GREAT Architecture for Edge-Based Graph Problems Like TSP
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915520348946432 |
|---|---|
| author | Lischka, Attila Rydin, Filip Wu, Jiaming Chehreghani, Morteza Haghir Kulcsár, Balázs |
| author_facet | Lischka, Attila Rydin, Filip Wu, Jiaming Chehreghani, Morteza Haghir Kulcsár, Balázs |
| contents | In the last years, an increasing number of learning-based approaches have been proposed to tackle combinatorial optimization problems such as routing problems. Many of these approaches are based on graph neural networks (GNNs) or related transformers, operating on the Euclidean coordinates representing the routing problems. However, such models are ill-suited for a wide range of real-world problems that feature non-Euclidean and asymmetric edge costs. To overcome this limitation, we propose a novel GNN-based and edge-focused neural model called Graph Edge Attention Network (GREAT). Using GREAT as an encoder to capture the properties of a routing problem instance, we build a reinforcement learning framework which we apply to both Euclidean and non-Euclidean variants of vehicle routing problems such as Traveling Salesman Problem, Capacitated Vehicle Routing Problem and Orienteering Problem. Our framework is among the first to tackle non-Euclidean variants of these problems and achieves competitive results among learning-based benchmarks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16717 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A GREAT Architecture for Edge-Based Graph Problems Like TSP Lischka, Attila Rydin, Filip Wu, Jiaming Chehreghani, Morteza Haghir Kulcsár, Balázs Machine Learning Artificial Intelligence In the last years, an increasing number of learning-based approaches have been proposed to tackle combinatorial optimization problems such as routing problems. Many of these approaches are based on graph neural networks (GNNs) or related transformers, operating on the Euclidean coordinates representing the routing problems. However, such models are ill-suited for a wide range of real-world problems that feature non-Euclidean and asymmetric edge costs. To overcome this limitation, we propose a novel GNN-based and edge-focused neural model called Graph Edge Attention Network (GREAT). Using GREAT as an encoder to capture the properties of a routing problem instance, we build a reinforcement learning framework which we apply to both Euclidean and non-Euclidean variants of vehicle routing problems such as Traveling Salesman Problem, Capacitated Vehicle Routing Problem and Orienteering Problem. Our framework is among the first to tackle non-Euclidean variants of these problems and achieves competitive results among learning-based benchmarks. |
| title | A GREAT Architecture for Edge-Based Graph Problems Like TSP |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2408.16717 |