Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

Large-scale routing often requires visiting clusters of nodes in a prescribed order, giving rise to the Ordered Clustered Traveling Salesman Problem (OCTSP). Optimizing each cluster independently seems natural, but misses non-local dependencies. We introduce the COMPASS algorithm for OCTSP, which combines search with learning-accelerated routing by orchestrating parallel sub-solvers. COMPASS has no quality ceiling and its solutions keep improving with compute. It exploits the clustered structure, and can reach exact solutions in time exponential in cluster size rather than instance size. Empirically, COMPASS consistently outperforms alternative methods. Unlike common large-scale routing solvers, COMPASS consumes general distance matrices and is not limited to coordinate inputs. We demonstrate scaling to 100K synthetic nodes and to 28.5K real e-commerce nodes. To our knowledge, the latter is the largest reported routing solution over asymmetric distances, 9x beyond established ATSP benchmarks.

We propose Tiny Recursive Models for Combinatorial Optimization (\ours{}), a general neural method for combinatorial optimization that scales both depth (how often we recursively invoke our network) and width (how much we sample in parallel). Both are fundamental for combinatorial optimization: hard instances demand a large amount of compute, while a small network is essential to avoid overfitting and capture the algorithmic essence of optimization. In particular, our method consists of a graph-aware tiny recursive model that iterates on a latent state with adaptive halting and needs only a lightweight problem-specific decoder. Compared with previous heatmap-based general neural solvers, it achieves a better balance between solution quality and inference speed on both the Traveling Salesman Problem~(TSP) and the Maximum Independent Set~(MIS) problem, and remains competitive with hybrid methods that combine neural components with heuristics specific to each problem. With the same backbone architecture for both tasks, \ours{} outperforms every diffusion-based solver on TSP from 500 to 10,000 cities at a lower inference cost, and on the standard Erdős--Rényi-[700-800] MIS benchmark it surpasses all neural solvers except those that only work well on MIS. We then explore self-relabeling for self-supervised training. We periodically replace the current set of training labels with the model's own better solutions, as an alternative training signal. Self-relabeling can, while forgoing supervision from near-optimal solutions, still result in on-par quality.

Although Vehicle Routing Problems (VRP) are essential to many real-world systems, they remain computationally intractable at scale due to their combinatorial complexity. Traditional heuristics rely on handcrafted rules for local improvements and occasional \textit{jumps} to escape local minima, but often struggle to generalize across diverse instances. We introduce \textbf{COAgents}, a cooperative multi-agent framework that models the search process as a graph: nodes represent solutions, and edges correspond to either local refinements or large perturbations for diversification (i.e., jumps). A \textit{Partial Search Graph} (PSG) is dynamically constructed during search, enabling COAgents to train a Node Selection Agent and a Move Selection Agent to guide intensification, and a Jump Agent to trigger well-timed explorations of new regions. Unlike end-to-end learning approaches, COAgents cleanly separates problem-agnostic search control from compact domain-specific encoding, facilitating adaptability across tasks. Extensive experiments on the CVRP and VRPTW benchmarks show that COAgents remains competitive with several learn-to-search baselines on CVRP and sets a new state of the art among learning-based methods on the more challenging VRPTW instances, reducing the gap to the best-known solutions by 14% at $N\!=\!100$ and 44% at $N\!=\!50$ relative to the strongest neural solver (POMO), and by 21% and 40% respectively relative to ALNS. Code is available at https://github.com/mahdims/COAgents.