RADAR: Learning to Route with Asymmetry-aware DistAnce Representations
New neural framework tackles one-way streets and traffic flows that break traditional routing assumptions.
A team of researchers has introduced RADAR (Learning to Route with Asymmetry-aware DistAnce Representations), a novel neural framework designed to solve a critical flaw in current AI-powered routing systems. Most neural solvers for Vehicle Routing Problems (VRPs) assume symmetric, Euclidean distances—meaning the cost from point A to B equals the cost from B to A. This breaks down in real-world logistics where one-way streets, traffic patterns, and tolls create inherently asymmetric travel costs. RADAR augments existing neural architectures to directly encode these complex, real-world relationships, moving AI routing beyond simplified map models.
The technical innovation is two-fold. First, RADAR applies Singular Value Decomposition (SVD) to the raw asymmetric distance matrix, creating compact, generalizable node embeddings that inherently capture static inbound/outbound cost differences. Second, it replaces the standard softmax in attention mechanisms with Sinkhorn normalization, which enforces joint row and column awareness to model dynamic asymmetry during the encoding process. Extensive testing shows RADAR outperforms strong baselines on both in-distribution and out-of-distribution instances across various VRP types. This represents a significant step toward deployable AI for complex logistics, where generalization beyond training data is essential.
- Enables neural VRP solvers to handle real-world asymmetric travel costs (e.g., one-way streets, traffic).
- Uses SVD for static asymmetry and Sinkhorn normalization in attention for dynamic asymmetry.
- Demonstrates superior performance and robust generalization on synthetic and real-world benchmarks.
Why It Matters
Enables practical AI optimization for logistics, delivery, and ride-sharing where travel time and cost are not bidirectional.