グラフの単純化を超えて：多重グラフ上におけるニューラル多目的ルーティング
なぜ重要か: 企業や社会への影響が見込まれ、一般メディアにも波及する可能性があります。
arXiv:2506.22095v3 発表種別：replace-cross
概要：近年、単一目的および多目的の両方のコンテキストにおいて、学習に基づくルーティング手法が大きな注目を集めている。しかしながら、現実世界のシナリオにおいて高い関連性を持つにもかかわらず、ノードペア間に異なる属性を持つ複数のエッジを特徴とするマルチグラフ上でのルーティングには、既存の手法は適していない。本論文では、マルチグラフ上の多目的ルーティングに対処するための、グラフニューラルネットワークに基づく2つの手法を提案する。最初の方法では、ツアーが完了するまで自己回帰的にエッジを選択することで、直接マルチグラフ上で動作する。2番目のモデルは、よりスケーラブルであり、最初に学習されたプルーニング戦略によってマルチグラフを簡略化し、その後、得られた単純グラフ上で自己回帰的ルーティングを実行する。広範囲の問題とグラフ分布にわたり、両方のモデルを経験的に評価し、強力なヒューリスティックおよびニューラルベースラインと比較して、その競争力のある性能を実証する。
原文（英語）を表示
Title (EN): Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs
arXiv:2506.22095v3 Announce Type: replace-cross
Abstract: 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.
Published: 2025-09-24 19:00 UTC