Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910027433902080 |
|---|---|
| author | Rydin, Filip Lischka, Attila Wu, Jiaming Chehreghani, Morteza Haghir Kulcsár, Balázs |
| author_facet | Rydin, Filip Lischka, Attila Wu, Jiaming Chehreghani, Morteza Haghir Kulcsár, Balázs |
| contents | Learning-based methods for routing have gained significant attention in recent years, both in single-objective and multi-objective contexts. Yet, existing methods are unsuitable for routing on multigraphs, which feature multiple edges with distinct attributes between node pairs, despite their strong relevance in real-world scenarios. In this paper, we propose two graph neural network-based methods to address multi-objective routing on multigraphs. Our first approach operates directly on the multigraph by autoregressively selecting edges until a tour is completed. The second model, which is more scalable, first simplifies the multigraph via a learned pruning strategy and then performs autoregressive routing on the resulting simple graph. We evaluate both models empirically, across a wide range of problems and graph distributions, and demonstrate their competitive performance compared to strong heuristics and neural baselines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22095 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs Rydin, Filip Lischka, Attila Wu, Jiaming Chehreghani, Morteza Haghir Kulcsár, Balázs Machine Learning Artificial Intelligence Learning-based methods for routing have gained significant attention in recent years, both in single-objective and multi-objective contexts. Yet, existing methods are unsuitable for routing on multigraphs, which feature multiple edges with distinct attributes between node pairs, despite their strong relevance in real-world scenarios. In this paper, we propose two graph neural network-based methods to address multi-objective routing on multigraphs. Our first approach operates directly on the multigraph by autoregressively selecting edges until a tour is completed. The second model, which is more scalable, first simplifies the multigraph via a learned pruning strategy and then performs autoregressive routing on the resulting simple graph. We evaluate both models empirically, across a wide range of problems and graph distributions, and demonstrate their competitive performance compared to strong heuristics and neural baselines. |
| title | Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2506.22095 |