arXiv：cs.AI· Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya, Gal Chechik·· 4 小时前
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