arXiv cs.AI· Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya, Gal Chechik·· 3 天前AI 评分27
ResizeCO：扩散路由求解器的规模泛化方法
Size Generalization for Diffusion Routing Solvers
AI 导读
ResizeCO 是一种无标签规模泛化方法，通过强化学习（适配 GRPO，以路径长度为训练信号）在大规模实例上微调小规模训练的扩散模型，并将 k-opt 建模为树搜索、用 GPU 上的 beam search 求解。
正文 · 原文
Abstract:Routing problems, like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are NP-hard and slow to solve for large instances. Diffusion-based solvers can be trained in a supervised way using sets of optimal solutions, and then quickly solve new test instances. However, for large instances, optimal solutions are hard to find, and diffusion models fail to generalize to instance sizes outside their training distribution. Here we describe ResizeCO, a label free size-generalization approach that addresses both the change in statistical properties of larger instances, and the computational challenge of solving them quickly. It uses reinforcement learning on large-scale instances to adapt a diffusion model trained on small instances. Specifically, we adapt GRPO to this problem, using route length as the training signal. ResizeCO also formulates k-opt as a tree search, solved by a beam search on the GPU. In size-generalization experiments on TSP and CVRP instances with up to 10000 nodes, ResizeCO achieves a Pareto front over route quality and time that dominates learned solvers, and also outperforms other solvers at short run times, setting a new state of the art.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.17192 [cs.AI] |
| (or arXiv:2610.17192v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.17192 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Barak Itzchak Davidovitch [view email]
[v1]
Mon, 12 Oct 2026 17:56:25 UTC (338 KB)
来源：arXiv cs.AI · arxiv.org