Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs
This addresses routing challenges in real-world scenarios like transportation or logistics where multigraphs are common, representing an incremental advancement by adapting neural methods to this specific graph structure.
The paper tackles the problem of multi-objective routing on multigraphs, where existing methods are unsuitable, and proposes two graph neural network-based approaches that achieve competitive performance compared to strong heuristics and neural baselines across various problems and graph distributions.
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.