Two-Stage Learned Decomposition for Scalable Routing on Multigraphs
Most neural methods for Vehicle Routing Problems (VRPs) are limited to Euclidean settings or simple graphs. In this work, we instead consider multigraphs, where parallel edges represent distinct travel options with varying trade-offs (e.g., distance vs time). Few methods are designed for such formulations and those that do exist face major scalability issues. We mitigate these scalability issues via a Node-Edge Policy Factorization (NEPF) approach, which splits the routing policy into a node permutation stage and an edge selection stage. To enable the decomposition, we introduce a pre-encoding edge aggregation scheme and a non-autoregressive architecture for the edge stage, as well as a hierarchical reinforcement learning method to train the stages jointly. Our experiments across six VRP variants demonstrate that NEPF matches or outperforms the state-of-the-art in terms of solution quality, while being significantly faster in training and inference.
Code (0)
등록된 구현이 없습니다.
Tasks
Hierarchical Reinforcement LearningSimilar Papers 제목 키워드 기반
LAR-MoE: Latent-Aligned Routing for Mixture of Experts in Robotic Imitation Learning
Imitation learning enables robots to acquire manipulation skills from demonstrations, yet deploying a policy across tasks with heterogeneous dynamics remains challenging, as models tend to average over distinct behaviora…
Multigraph Message Passing with Bi-Directional Multi-Edge Aggregations
Graph Neural Networks (GNNs) have seen significant advances in recent years, yet their application to multigraphs, where parallel edges exist between the same pair of nodes, remains under-explored. Standard GNNs, designe…
Graph LearningTowards Resource-Efficient Multimodal Intelligence: Learned Routing among Specialized Expert Models
As AI moves beyond text, large language models (LLMs) increasingly power vision, audio, and document understanding; however, their high inference costs hinder real-time, scalable deployment. Conversely, smaller open-sour…
Visual Question AnsweringA Nonparametric Bayesian Model for Sparse Dynamic Multigraphs
As the availability and importance of temporal interaction data--such as email communication--increases, it becomes increasingly important to understand the underlying structure that underpins these interactions. Often t…
ClusteringConvolutional Learning on Multigraphs
Graph convolutional learning has led to many exciting discoveries in diverse areas. However, in some applications, traditional graphs are insufficient to capture the structure and intricacies of the data. In such scenari…