Edisco improves euclidean routing and traveling salesman solutions
EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization
Machine LearningArtificial Intelligence
Summary
Certain routing and delivery problems, like the traveling salesman problem, have patterns that stay the same even if you rotate or move the map. Existing AI methods try to learn these patterns by showing many rotated or flipped examples, but they don't capture the math perfectly. The authors created EDISCO, a new AI that exactly understands these rotation and movement patterns, which helps it learn faster and solve problems better. EDISCO works well on tests with large numbers of points and can handle changes in map layout or delivery rules.
What this means in practice
- •For logistics planners: Optimize delivery routes more efficiently using a model that respects spatial symmetries exactly.
- •For operations managers: Handle vehicle routing problems under different geographical and constraint shifts with improved solution robustness.
Authors
Ruogu Chen, Jie Han
Abstract
Euclidean combinatorial optimization problems (ECOPs), such as the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP), possess inherent symmetries under the two-dimensional Euclidean group E(2), including rotations, reflections, and translations. Existing learning-based methods, including recent diffusion-based methods, rely on data augmentation or regularization to approximate E(2)-equivariance. This paper presents EDISCO, the first discrete diffusion model for ECOPs with exact E(2)-invariant generative distributions over node-index solutions. EDISCO introduces an E(2)-equivariant edge-score network coupled with a categorical continuous-time Markov chain over discrete edge variables, and exact posterior sampling provides efficient multi-step inference. This design gives EDISCO a local geometric inductive bias: edge neighborhoods with the same relative geometry and combinatorial context are represented consistently regardless of absolute position or orientation, making learning more efficient and inference more robust than non-equivariant methods. EDISCO outperforms previous learning-based state-of-the-art solvers on synthetic TSP from 100 to 10000 nodes and CVRP from 50 to 2000 customers, while using only 33-50% of the training instances. Trained only on uniform synthetic data, EDISCO also outperforms competing learning-based baselines under spatial distribution shift and CVRP constraint-tightness shift. Code is available at https://github.com/ValleyC/EDISCO.