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.