提出两种神经网络方法，解决多目标路由在多重图上的难题
Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs
- 直接在多重图上逐边选择，完成路径规划
- 通过学习剪枝简化图结构，提升计算效率
- 在多种场景下表现优于传统启发式与神经基线
近年来，基于学习的路由方法在单目标和多目标场景中受到广泛关注。然而，现有方法难以适用于多重图——即节点对间存在多个属性各异的边，而这类结构在真实场景中具有重要应用价值。本文提出两种基于图神经网络的多目标路由方法：第一种直接在多重图上进行自回归边选择，直至完成路径；第二种更具可扩展性，先通过学习策略对多重图进行剪枝，再在简化后的简单图上执行自回归路由。我们在多种问题和图分布上对两模型进行了实证评估，结果表明其性能显著优于强启发式算法与主流神经基线。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。