RADAR: Learning to Route with Asymmetry-aware DistAnce Representations

2026-03-05 · Source: cs.LG updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Robotics & Autonomous Systems · Depth: Expert, extended

Summary

RADAR is a novel neural framework designed to enhance existing neural Vehicle Routing Problem (VRP) solvers by effectively handling asymmetric distance matrices, which are common in real-world scenarios due to factors like one-way streets and traffic. Most neural VRP solvers assume symmetric Euclidean distances, limiting their practical applicability. RADAR addresses asymmetry from both static and dynamic perspectives. For static asymmetry, it uses Singular Value Decomposition (SVD) on the asymmetric distance matrix to create compact, generalizable node embeddings that capture inbound and outbound costs. For dynamic asymmetry, it replaces the standard softmax in attention mechanisms with Sinkhorn normalization, imposing joint row and column distance awareness in attention weights. Extensive experiments on 17 synthetic and 3 real-world VRP benchmarks demonstrate that RADAR consistently outperforms strong baselines, showing robust generalization and superior performance on both in-distribution and out-of-distribution instances, including ATSP and ACVRP variants.

Key takeaway

For research scientists developing neural combinatorial optimization models for real-world routing, RADAR demonstrates that explicitly modeling static and dynamic asymmetry is crucial. You should consider integrating SVD-based initialization for robust, generalizable node embeddings and Sinkhorn normalization in attention mechanisms to capture global directional dependencies. This approach significantly improves performance and generalization across diverse asymmetric VRPs, making your models more applicable to complex, real-world logistical challenges.

Key insights

RADAR enhances neural VRP solvers by integrating SVD-based initialization and Sinkhorn normalization for robust asymmetric distance handling.

Principles

• Asymmetry requires both static and dynamic modeling.
• SVD can capture global directional relationships.
• Sinkhorn normalization ensures balanced bidirectional attention.

Method

RADAR initializes node embeddings using truncated SVD of the cost matrix to capture static asymmetry. It then employs Sinkhorn normalization in the encoder's attention mechanism to model dynamic asymmetry by jointly normalizing rows and columns.

In practice

• Use SVD for initial node embeddings in asymmetric graphs.
• Apply Sinkhorn normalization in attention for directional flow consistency.

Topics

• Vehicle Routing Problems
• Neural Combinatorial Optimization
• Asymmetric Distance Matrices
• Singular Value Decomposition
• Sinkhorn Normalization

Code references

• yihang0410/RADAR

Best for: Research Scientist, AI Researcher, AI Scientist, Machine Learning Engineer

Related on AIssential

• Optimal Transport for Machine Learners — Optimal Transport offers a robust mathematical framework for comparing probability distributions, crucial for generative AI model design.
• Asymmetric-Loss-Guided Hybrid CNN-BiLSTM-Attention Model for Industrial RUL Prediction with Interpretable Failure Heatmaps — A hybrid CNN-BiLSTM-Attention model with asymmetric loss improves turbofan RUL prediction and interpretability.
• STAR: Rethinking MoE Routing as Structure-Aware Subspace Learning — STAR rethinks MoE routing as structure-aware subspace learning for stable expert specialization.
• Representation Gap: Explaining the Unreasonable Effectiveness of Neural Networks from a Geometric Perspective — Neural network generalization is geometrically characterized by the Representation Gap, scaling with intrinsic data dimension and model equivariance.
• Space Is Intelligence: Neural Semigroup Superposition for Riemannian Metric Generation — Intelligence can be embedded in a scene's Riemannian metric, allowing agents to navigate by following geodesics, bypassing traditional planners.
• Sinkhorn-CPD: Robust point cloud registration via unbalanced entropic optimal transport — Sinkhorn-CPD uses unbalanced entropic optimal transport with dual KL penalties for robust point cloud registration, automatically handling outliers and partial overlap.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.LG updates on arXiv.org.