Compass algorithm solves massive ordered routing problems efficiently
COMPASS: Ordered Clustered Routing at 100K Scale
Machine Learning
Summary
Some routing problems require visiting groups of places in a specific order, which is tricky to solve fast when there are many places. The authors developed an algorithm called COMPASS that cleverly combines searching possible routes with learned shortcuts and can solve these problems even with very large numbers of places. Unlike other methods, COMPASS can work with general distances and not just places on a map. It performs well on tens of thousands of locations and finds better routes than other methods.
What this means in practice
- •For logistics planners: Optimize delivery routes that require visiting customer groups in sequence with improved accuracy at large scales.
- •For e-commerce operations teams: Manage and route orders across clustered warehouse or customer locations using real-world asymmetric distance data.
Authors
Ido Greenberg, Hugo Linsenmaier, Piotr Sielski, Shie Mannor, Alex Fender, Gal Chechik, Eli Meirom
Abstract
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.