COMPASS: Ordered Clustered Routing at 100K Scale
COMPASS combines search with learning-accelerated parallel sub-solvers for the Ordered Clustered TSP, scaling to 100K synthetic and 28.5K real e-commerce nodes.
COMPASS is an algorithm for the Ordered Clustered Traveling Salesman Problem (OCTSP) that orchestrates parallel sub-solvers, combining search with learning-accelerated routing. It has no quality ceiling, exploits clustered structure to reach exact solutions exponential in cluster size rather than instance size, and accepts general distance matrices beyond coordinate inputs. The method scales to 100K synthetic nodes and 28.5K real e-commerce nodes, the largest reported routing solution over asymmetric distances, 9x beyond established ATSP benchmarks.
- Orchestrates parallel sub-solvers, reaching exact solutions exponential in cluster size rather than instance size.
- Accepts general distance matrices, not limited to coordinate inputs like common large-scale routing solvers.
- Scales to 100K synthetic nodes and 28.5K real e-commerce nodes, 9x beyond established ATSP benchmarks.
- Solutions keep improving with compute, with no quality ceiling.
Full article136 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.20352