RADAR: Learning to Route with Asymmetry-aware DistAnce Representations

RADAR is a scalable neural framework that enhances vehicle routing problem solvers for asymmetric scenarios by leveraging Singular Value Decomposition to encode static distance asymmetry and Sinkhorn normalization to model dynamic interaction asymmetry, thereby achieving superior generalization and performance on both synthetic and real-world benchmarks.

The Gist

Imagine you are a delivery company manager trying to figure out the most efficient way to deliver packages to 100 different houses in a city. This is the Vehicle Routing Problem (VRP).

In a perfect, imaginary world, the distance from House A to House B is exactly the same as from House B to House A. It's like walking on a flat, open field. Most computer programs (AI) designed to solve this problem assume this "perfect world" exists. They look at a map, see two dots, and calculate the straight-line distance between them.

But the real world isn't a flat field.

In reality, you have one-way streets, traffic jams that only happen in the morning, and bridges that are closed in one direction. The trip from A to B might take 10 minutes, but the trip back from B to A could take 40 minutes because of a massive traffic jam. This is called asymmetry.

Current AI models are like drivers who only know how to drive on a perfect, symmetrical grid. When you give them a real city map with one-way streets, they get confused, get lost, or take terrible routes.

Enter RADAR: The "Smart Navigator"

The paper introduces a new AI system called RADAR. Think of RADAR as a super-smart navigator that doesn't just look at a map; it understands the flow of the city. It solves the problem in two clever ways, which the authors call "Static" and "Dynamic" awareness.

1. The "Static" Problem: Reading the Map Before You Start

The Analogy: Imagine you are given a list of 100 houses and a giant spreadsheet showing the travel time between every single pair.

• Old AI: It tries to memorize the list of houses one by one, like a student memorizing a phone book. It doesn't really "see" the connections between the houses until it starts driving.
• RADAR's Trick (SVD): RADAR looks at that giant spreadsheet and performs a mathematical magic trick called Singular Value Decomposition (SVD).
  • Think of the spreadsheet as a complex, tangled knot of string.
  • SVD is like a pair of scissors that cuts the knot into two neat, organized bundles: one bundle representing "outgoing" trips (leaving a house) and one representing "incoming" trips (arriving at a house).
  • By separating these two directions immediately, RADAR creates a "mental map" where every house knows exactly how hard it is to leave it and how hard it is to enter it. It doesn't have to guess; it starts with the answer already built into its brain.

2. The "Dynamic" Problem: Driving with the Flow

The Analogy: Now imagine the AI is actually driving the route, deciding which house to visit next.

• Old AI (Softmax): Imagine a driver who only looks at the houses right next to them. They ask, "Which of these 5 neighbors is closest?" They make a decision based only on their immediate surroundings. They ignore the fact that the neighbor they picked might be a "dead end" or a traffic trap for the rest of the city.
• RADAR's Trick (Sinkhorn Normalization): RADAR uses a different decision-making tool called Sinkhorn Normalization.
  • Imagine the driver is in a room with 100 people. Instead of just asking the people standing next to them, RADAR asks the whole room: "If I go to Person A, how does that affect everyone else's ability to get to their destination?"
  • It balances the attention. It ensures that if a house is a "hub" (a place everyone wants to go), the AI doesn't get stuck there. It spreads the traffic out evenly. It understands that the relationship between House A and House B isn't just about A; it's about how A and B fit into the entire city's traffic pattern.

Why Does This Matter?

The paper tested RADAR on:

1. Fake Cities: Made-up maps with random one-way streets.
2. Real Cities: Actual maps from real-world data (like New York or London) with real traffic patterns.

The Results:

• Better Routes: RADAR found routes that were significantly shorter and faster than the previous best AI models.
• Scalability: It worked great on small problems (100 houses) and huge problems (1,000 houses) without getting confused.
• Real-World Ready: Unlike other models that break when you take away the "perfect map" coordinates and just give them a list of travel times, RADAR thrives on that messy, real-world data.

The Bottom Line

Think of previous AI solvers as tourists who only know how to walk in a straight line on a grid. They get lost as soon as the streets get complicated.

RADAR is a local taxi driver. It knows that the way in is different from the way out. It studies the traffic patterns before it starts (Static SVD) and constantly adjusts its route based on how the whole city is moving, not just the immediate street (Dynamic Sinkhorn).

This makes it a massive step forward for using AI to solve real-world logistics problems like delivery trucks, garbage collection, and emergency response, where "straight lines" don't exist.

Technical Summary

1. Problem Statement

The Vehicle Routing Problem (VRP) is a classic NP-hard combinatorial optimization problem. While recent Neural Combinatorial Optimization (NCO) solvers have achieved strong performance, they predominantly rely on symmetric Euclidean distances derived from node coordinates. This limits their applicability to real-world scenarios where travel costs are asymmetric due to factors like one-way streets, traffic directionality, and physical barriers.

In asymmetric settings, the cost from node $i$ to $j$ ($D_{i,j}$) differs from $j$ to $i$ ($D_{j,i}$). Existing neural solvers face two main challenges in this domain:

1. Static Asymmetry: Difficulty in encoding the global directional structure of the input distance matrix into initial node embeddings. Most architectures operate on node-level representations, whereas asymmetric costs are edge-level properties.
2. Dynamic Asymmetry: Standard attention mechanisms (using row-wise Softmax) only capture the local context of the source node $i$, ignoring how the target node $j$ interacts with the rest of the graph. This fails to model the bidirectional dependencies inherent in asymmetric routing.

2. Methodology: RADAR Framework

The authors propose RADAR (Learning to Route with Asymmetry-aware DistAnce Representations), a scalable neural framework that augments existing VRP solvers to handle asymmetric inputs. It addresses the two types of asymmetry through distinct components:

A. Static Asymmetry: SVD-Based Initialization

To capture the global directional structure of the distance matrix $D$ without relying on coordinates, RADAR employs Truncated Singular Value Decomposition (TSVD).

• Mechanism: The asymmetric distance matrix $D \in \mathbb{R}^{n \times n}$ is decomposed as $D \approx U_k \Sigma_k V_k^\top$.
• Embedding Construction:
  • $U_k$ (Left singular vectors) encodes outgoing signals (source roles).
  • $V_k$ (Right singular vectors) encodes incoming signals (destination roles).
  • The node embedding $X$ is formed by concatenating the scaled singular vectors: $X = [U_k \Sigma_k^{1/2} \mid V_k \Sigma_k^{1/2}]$.
• Theoretical Guarantee: This construction ensures the existence of linear transformations $W_1, W_2$ such that $X W_1 (X W_2)^\top \approx D$. This allows the attention mechanism (which computes $QK^\top$) to naturally reconstruct the asymmetric distance structure from the initial embeddings, preserving global directionality.
• Implementation: The authors use the top-10 singular values as a trade-off between information retention and generalization.

B. Dynamic Asymmetry: Sinkhorn Normalization

To model dynamic asymmetry during the encoding process, RADAR replaces the standard row-wise Softmax in the attention mechanism with Sinkhorn Normalization.

• Mechanism: Instead of normalizing attention scores only across rows (outgoing from $i$), Sinkhorn normalization iteratively normalizes both rows and columns of the attention matrix.
• Effect: This enforces doubly stochastic attention weights, ensuring that the interaction score $A_{i,j}$ reflects not just $i$'s local context but also $j$'s relationship with the rest of the graph. This captures the "balanced bidirectional flow" required for asymmetric problems, preventing the model from ignoring the global structure of the target node.

3. Key Contributions

1. Real-World Applicability: The work bridges the gap between neural solvers and real-world asymmetric routing by moving away from coordinate-centric inputs to direct distance matrix encoding.
2. SVD Initialization: Introduces a novel initialization scheme that extracts compact, asymmetry-aware node embeddings from the distance matrix itself, significantly improving generalization across instance sizes compared to random or one-hot initialization.
3. Sinkhorn Attention: Demonstrates that replacing Softmax with Sinkhorn normalization is crucial for capturing global directional dependencies in asymmetric settings, leading to better convergence and solution quality.
4. Comprehensive Evaluation: The framework is validated on 17 synthetic VRP variants (including ATSP, ACVRP) and 3 real-world datasets, consistently outperforming state-of-the-art baselines.

4. Experimental Results

The authors evaluated RADAR on various benchmarks, comparing it against traditional solvers (LKH3, HGS) and neural baselines (MatNet, ICAM, ReLD, UniCO, RRNCO).

• Synthetic Benchmarks (ATSP & ACVRP):
  • RADAR achieved the lowest optimality gaps among all learning-based methods.
  • On ATSP1000, RADAR maintained a gap of 4.13%, whereas other neural methods (e.g., MatNet, ICAM) suffered gaps exceeding 18–84% or failed to generalize.
  • RADAR even surpassed the traditional solver LKH on ACVRP200.
• Multi-Task Learning:
  • Across 16 asymmetric VRP variants, RADAR achieved the lowest average gap (1.33%) compared to other neural approaches, demonstrating robustness across diverse constraints (time windows, backhauls, etc.).
• Real-World Datasets:
  • On real-world benchmarks (derived from OpenStreetMap), RADAR consistently outperformed RRNCO and MatNet in both in-distribution and out-of-distribution (different cities/clusters) settings, with gaps often below 1%.
• Ablation Studies:
  • Removing SVD initialization or Sinkhorn normalization significantly degraded performance, confirming the necessity of both components.
  • RADAR showed superior robustness under varying levels of asymmetry (simulated by noise) compared to other initialization strategies.
  • The method generalized well to different demand distributions (skewed small/large), whereas other models degraded.

5. Significance and Impact

• Paradigm Shift: RADAR challenges the reliance on Euclidean coordinates in NCO, proving that neural solvers can effectively learn directly from asymmetric distance matrices, which is the standard format for real-world logistics data.
• Generalization: The SVD-based initialization provides a "cold-start" mechanism that encodes structural priors, enabling the model to generalize to problem sizes significantly larger than those seen during training (zero-shot generalization).
• Practical Deployment: By achieving near-optimal performance with inference times in seconds (compared to hours for traditional solvers like LKH on large instances), RADAR offers a viable path for deploying NCO in time-sensitive, real-world asymmetric routing scenarios.
• Broader Applicability: The authors note that the SVD-based relational encoding is not limited to VRPs but can be applied to other combinatorial problems involving directed relational matrices, such as the Flexible Flow Shop Scheduling Problem (FFSP).