Each language version is independently generated for its own context, not a direct translation.

🚗 RADAR: 비대칭 도로를 위한 똑똑한 내비게이션

이 논문은 **"RADAR"**이라는 새로운 인공지능 시스템을 소개합니다. 이 시스템은 차량 경로 최적화 문제 (VRP) 를 해결하는 데 특화되어 있는데, 특히 실제 도로 환경처럼 '가는 길'과 '오는 길'이 다른 (비대칭적인) 상황에서 탁월한 성능을 발휘합니다.

기존의 AI 들은 대부분 "가는 길과 오는 길 거리가 똑같다"는 이상적인 가정을 하고 훈련되었기 때문에, 실제 복잡한 도시 도로 (일방통행, 교통 체증 등) 에 적용하면 성능이 떨어졌습니다. RADAR 는 이 문제를 해결하기 위해 두 가지 핵심 기술을 도입했습니다.

🧩 1. 문제 상황: "가는 길"과 "오는 길"이 다른 세상

🗺️ 기존 AI 의 한계 (대칭적인 세계)

기존의 경로 탐색 AI 들은 마치 원형 경기장에서 달리는 선수들처럼 생각했습니다. 경기장 안에서는 A 에서 B 로 가는 거리와 B 에서 A 로 가는 거리가 정확히 같습니다. 그래서 AI 는 "거리"라는 정보를 단순히 좌표 (x, y) 만 보고 계산하면 됐습니다.

하지만 실제 도시는 다릅니다.

일방통행: A 에서 B 로는 갈 수 있지만, B 에서 A 로는 갈 수 없습니다.
교통 체증: A 에서 B 로는 10 분 걸리지만, B 에서 A 로는 20 분 걸립니다.
교량과 터널: 특정 방향으로만 통행이 가능합니다.

이처럼 "가는 길"과 "오는 길"이 다른 (비대칭적인) 상황에서 기존 AI 는 길을 잃거나 비효율적인 경로를 찾습니다. 마치 지도에 "가는 길"만 그려져 있고 "오는 길"은 없는 것처럼 작동하기 때문입니다.

🛠️ 2. RADAR 의 해결책: 두 가지 핵심 기술

RADAR 는 이 문제를 해결하기 위해 **정적 (Static)**인 정보와 **동적 (Dynamic)**인 상호작용을 모두 고려합니다.

🔍 기술 1: SVD(특이값 분해) 를 이용한 '초능력' 지도 읽기 (정적 비대칭)

비유: 거울과 그림자
기존 AI 는 각 도시 (노드) 를 단순히 "이곳은 A 시입니다"라고만 기억했습니다. 하지만 RADAR 는 **SVD(특이값 분해)**라는 수학적 도구를 사용합니다.

상황: A 에서 B 로 가는 비용은 100 원, B 에서 A 로 가는 비용은 50 원입니다.
기존 방식: "A 와 B 사이 거리는 75 원"이라고 평균내버립니다. (정보 손실!)
RADAR 의 방식: SVD 를 통해 이 정보를 두 개의 다른 차원으로 쪼갭니다.
- 왼쪽 차원 (나가는 신호): "A 는 다른 곳으로 나가는 데 100 원이 든다"는 정보를 담습니다.
- 오른쪽 차원 (들어오는 신호): "A 는 다른 곳에서 들어올 때 50 원이 든다"는 정보를 담습니다.

이렇게 하면 AI 는 각 도시가 '출발지'로서 어떤 역할을 하고 '도착지'로서 어떤 역할을 하는지 동시에 이해하게 됩니다. 마치 **거울 (나가는 길) 과 그림자 (오는 길)**를 동시에 보고 도시의 성격을 파악하는 것과 같습니다.

🌪️ 기술 2: 싱크혼 (Sinkhorn) 정규화 - '균형 잡힌' 시선 (동적 비대칭)

비유: 인기 있는 식당과 혼잡한 도로
AI 가 경로를 찾을 때, Attention(주의) 메커니즘을 사용합니다. 기존 방식 (Softmax) 은 **"내가 지금 보고 있는 곳 (A) 에서 가장 가까운 곳들"**만 집중해서 봅니다.

문제: A 에서 B 로 가는 길은 멀지만, B 에서 A 로 오는 길은 매우 가깝습니다. 기존 AI 는 A 가 B 를 볼 때 B 가 다른 곳들과 어떻게 연결되는지 무시합니다. 마치 **인기 있는 식당 (B)**만 보고, 그 식당이 얼마나 붐비는지 (다른 곳과의 연결) 는 고려하지 않는 것과 같습니다.

RADAR 의 해결책 (Sinkhorn Normalization):
RADAR 는 Sinkhorn이라는 기술을 사용합니다.

기존: "내가 A 에서 B 를 볼 때"만 계산합니다.
RADAR: "내가 A 에서 B 를 볼 때"와 **"B 가 다른 곳들 (C, D, E...) 과 어떻게 연결되는지"**를 동시에 고려합니다.

이는 도로의 양방향 교통량을 모두 고려하는 것과 같습니다. 단순히 "가까운 길"만 보는 게 아니라, **"그 길이 전체 교통 흐름에 어떻게 영향을 미치는지"**를 균형 있게 파악하여, AI 가 더 넓은 시야를 가지고 경로를 계획하게 합니다.

🏆 3. 결과: 왜 RADAR 가 더 좋은가?

RADAR 는 합성 데이터와 실제 도시 데이터 (서울, 뉴욕 등) 에서 기존 최고의 AI 들보다 훨씬 좋은 결과를 냈습니다.

더 넓은 일반화: 작은 도시 (100 개 지점) 에서 배운 지식을 큰 도시 (1000 개 지점) 에 적용해도 성능이 떨어지지 않습니다. (기존 AI 는 도시가 커지면 길을 잃었습니다.)
실제 도로 적응력: 일방통행이나 복잡한 도로망이 있는 실제 데이터에서도 최적의 경로를 찾아냅니다.
빠른 속도: 복잡한 계산을 하더라도 실시간으로 경로를 찾을 수 있을 정도로 빠릅니다.

💡 요약: 한 줄로 정리하면?

RADAR는 **"가는 길과 오는 길이 다른 복잡한 도시"**에서, **수학적 분해 (SVD)**로 도로의 방향성을 정확히 파악하고, **균형 잡힌 시선 (Sinkhorn)**으로 전체 교통 흐름을 고려하여 가장 빠르고 효율적인 길을 찾아내는 차세대 AI 내비게이션입니다.

이 기술은 물류 배송, 택시 배차, 긴급 구조 활동 등 실제 도로 환경이 중요한 모든 분야에서 혁신을 가져올 것으로 기대됩니다.

Each language version is independently generated for its own context, not a direct translation.

RADAR: 비대칭 거리 표현을 인식한 라우팅 학습 (RADAR: LEARNING TO ROUTE WITH ASYMMETRY-AWARE DISTANCE REPRESENTATIONS) 기술 요약

본 논문은 ICLR 2026 에 발표된 것으로, 차량 라우팅 문제 (VRP) 를 해결하는 신경망 솔버 (Neural Solvers) 의 한계를 극복하고 현실 세계의 비대칭 거리 (Asymmetric Distances) 환경을 효과적으로 처리할 수 있는 새로운 프레임워크 RADAR를 제안합니다.

1. 문제 정의 및 배경

배경: 기존 신경망 기반 VRP 솔버 (Constructive Neural Solvers) 는 대부분 유클리드 거리 (대칭적) 를 가정하고 좌표 입력에 의존합니다.
현실적 제약: 실제 도로 네트워크에서는 일방통행, 교통 체증, 지형적 장벽 등으로 인해 $i \to j$ 와 $j \to i$ 의 이동 비용이 다른 비대칭 거리 행렬이 발생합니다.
핵심 과제:
1. 정적 비대칭 (Static Asymmetry): 입력된 거리 행렬 자체에 내재된 방향성 차이 (출발 노드와 도착 노드의 역할 차이) 를 임베딩에 어떻게 효과적으로 인코딩할 것인가?
2. 동적 비대칭 (Dynamic Asymmetry): 인코더의 어텐션 (Attention) 메커니즘 내에서 노드 간 상호작용이 방향에 따라 어떻게 다르게 학습되어야 하는가? 기존 Softmax 기반 어텐션은 행 (Row) 단위로만 정규화되어 노드 $j$ 가 그래프 전체와 어떻게 상호작용하는지 (열 정보) 를 무시하는 문제가 있습니다.

2. 제안 방법론: RADAR

RADAR 는 기존 신경망 VRP 솔버를 확장하여 비대칭 입력을 처리할 수 있도록 두 가지 핵심 기술을 도입합니다.

2.1 정적 비대칭 처리: SVD 기반 임베딩 초기화

문제: 기존 방법들은 노드 임베딩을 무작위나 고정된 패턴으로 초기화하여, 거리 행렬의 전역적 구조와 방향성을 잃어버리는 경우가 많았습니다.
해결책: 비대칭 거리 행렬 $D$ $D$ 에 대해 **특이값 분해 (SVD, Singular Value Decomposition)**를 적용합니다.
- $D \approx U_k \Sigma_k V_k^T$
- 여기서 $U_k$ 는 행 (출발 노드) 의 특성을, $V_k$ 는 열 (도착 노드) 의 특성을 나타냅니다.
- 임베딩 구성: 각 노드의 초기 임베딩을 $X = [U_k \Sigma_k^{1/2} | V_k \Sigma_k^{1/2}]$ 로 구성합니다. 이는 노드가 출발지로서의 역할과 도착지로서의 역할을 동시에 인코딩하도록 설계되었습니다.
- 이론적 근거: 정의 1 (Asymmetry-Aware Embedding) 에 따라, 이 임베딩은 두 개의 다른 선형 변환을 통해 원래 비대칭 행렬 $D$ 를 재구성할 수 있어, 어텐션 메커니즘이 방향성 정보를 효과적으로 학습할 수 있는 기반을 제공합니다.

2.2 동적 비대칭 처리: Sinkhorn 정규화

문제: 기존 어텐션은 Softmax 를 사용하여 행 (노드 $i$ 의 이웃) 에 대해서만 정규화합니다. 이는 노드 $i$ 가 $j$ 를 바라볼 때, $j$ 가 그래프 전체에서 어떤 위치를 차지하는지 (열 정보) 를 고려하지 못하게 합니다.
해결책: Softmax 를 Sinkhorn 정규화로 대체합니다.
- 어텐션 점수 행렬의 행과 열을 모두 반복적으로 정규화하여 **이중 확률 행렬 (Doubly Stochastic Matrix)**을 생성합니다.
- 이는 노드 $i$ 와 $j$ 간의 상호작용이 양방향으로 균형을 이루도록 강제하며, 각 노드가 그래프 전체의 맥락 (네트워크 구조) 을 고려하여 어텐션 점수를 계산하도록 합니다.
- 결과적으로 비대칭 환경에서의 방향성 의존성을 더 정확하게 포착할 수 있습니다.

3. 주요 기여

현실적 VRP 시나리오 적용: 좌표가 아닌 비대칭 거리 행렬만 입력 가능한 현실적인 VRP 변형 (ATSP, ACVRP 등 17 가지) 에 신경망 솔버를 적용 가능한 범위를 확장했습니다.
SVD 기반 초기화 및 Sinkhorn 어텐션: 거리 행렬의 전역적 방향성을 포착하는 SVD 초기화 방식과 상호작용 노드의 전체 맥락을 고려하는 Sinkhorn 정규화를 도입하여 일반화 성능을 크게 향상시켰습니다.
광범위한 실험 검증: 합성 데이터 (100~1000 노드) 와 3 가지 실제 세계 데이터셋 (RRNCO) 에서 다양한 VRP 변형에 대해 실험을 수행했습니다.
심층 분석: 좌표의 역할, 비대칭성 수준에 따른 초기화 전략의 영향, 다양한 수요 분포에서의 견고성 등을 분석하여 모델의 동작 원리를 규명했습니다.

4. 실험 결과

성능: RADAR 는 합성 데이터 (ATSP, ACVRP) 와 실제 데이터셋 모두에서 기존 최첨단 (SOTA) 솔버 (MatNet, ICAM, ReLD, RRNCO 등) 보다 우수한 성능을 보였습니다.
- ATSP: 1000 노드 크기의 인스턴스에서도 기존 신경망 기반 방법들보다 훨씬 낮은 오차 (Gap) 를 기록했습니다.
- ACVRP: 200 노드 크기에서 전통적인 휴리스틱 솔버 (LKH) 보다도 좋은 결과를 보여주었습니다.
- 실제 데이터: RRNCO 데이터셋에서 모든 작업 (ATSP, ACVRP, ACVRPTW) 에서 최적의 학습 기반 결과를 달성했습니다.
일반화 (Generalization): 훈련 데이터 (100 노드) 에서 학습하여 200, 500, 1000 노드와 같은 Out-of-Distribution (OOD) 인스턴스에 대해 뛰어난 일반화 능력을 입증했습니다.
비대칭성 수준: 비대칭성이 강해질수록 기존 방법들의 성능이 급격히 저하되는 반면, RADAR 는 안정적인 성능을 유지했습니다.
좌표 의존성 제거: 좌표 정보가 없더라도 거리 행렬만으로도 강력한 구조적 정보를 학습할 수 있음을 보였습니다.

5. 의의 및 결론

RADAR 는 신경 조합 최적화 (NCO) 분야가 이론적 유클리드 공간에서 벗어나 실제 도로 네트워크의 비대칭성을 처리할 수 있는 중요한 전환점을 제공합니다.

기술적 의의: SVD 를 통한 구조적 초기화와 Sinkhorn 을 통한 전역적 어텐션 정규화는 비대칭 행렬 데이터를 다루는 신경망 설계에 새로운 패러다임을 제시합니다.
실용적 의의: 일방통행, 시간 의존적 비용 등 복잡한 제약이 있는 실제 물류 및 운송 문제 해결에 직접 적용 가능한 강력한 도구를 제공합니다.
미래 전망: 이 프레임워크는 거리 행렬뿐만 아니라 다른 관계형 행렬 (예: 작업 스케줄링의 처리 시간 행렬) 을 사용하는 조합 최적화 문제에도 확장 가능함을 시사합니다.

요약하자면, RADAR 는 비대칭 VRP 문제에서 발생하는 방향성 정보의 손실을 최소화하고, 전역적 맥락을 고려한 학습을 가능하게 함으로써 기존 신경 솔버의 성능 한계를 극복한 획기적인 연구입니다.

RADAR: Learning to Route with Asymmetry-aware DistAnce Representations