# Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 66 references that are in the map.
- First posted on arXiv 27 Jun 2025.

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [pymoo: Multi-objective Optimization in Python](https://mlsanity.com/paper/2002.04504/) (2020)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Learning the Pareto Front with Hypernetworks](https://mlsanity.com/paper/2010.04104/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Deep Reinforcement Learning for Multi-objective Optimization](https://mlsanity.com/paper/1906.02386/) (2019)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Pareto Set Learning for Neural Multi-objective Combinatorial Optimization](https://mlsanity.com/paper/2203.15386/) (2022)
- [Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem](https://mlsanity.com/paper/2304.09407/) (2023)
- [GOAL: A Generalist Combinatorial Optimization Agent Learner](https://mlsanity.com/paper/2406.15079/) (2024)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization](https://mlsanity.com/paper/2310.15196/) (2023)
- [Meta-Learning-Based Deep Reinforcement Learning for Multiobjective Optimization Problems](https://mlsanity.com/paper/2105.02741/) (2021)
- [Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement](https://mlsanity.com/paper/2310.15195/) (2023)
- [MODRL/D-AM: Multiobjective Deep Reinforcement Learning Algorithm Using Decomposition and Attention Model for Multiobjective Optimization](https://mlsanity.com/paper/2002.05484/) (2020)
- [Unsupervised Training for Neural TSP Solver](https://mlsanity.com/paper/2207.13667/) (2022)
- [Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem](https://mlsanity.com/paper/2403.05318/) (2024)
- [GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costs](https://mlsanity.com/paper/2408.16717/) (2024)

## Built on by (most cited first, 2 of 2)

- [Two-Stage Learned Decomposition for Scalable Routing on Multigraphs](https://mlsanity.com/paper/2605.05389/) (2026)
- [When Evidence Changes the Subject: Subject-Typed Claim Licensing for Learned Routing](https://mlsanity.com/paper/2609.33505/) (2026)

## Abstract (arXiv)

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.