기술 요약: 신경 클러스터링 우선, 라우팅 차후

문제 정의

본 논문은 마지막 마일 물류에서 차량 대수 $Q$의 균일한 용량을 가진 차량 대가 중앙 창고에서 특정 수요를 가진 고객 집단을 서비스하며 총 이동 거리를 최소화해야 하는 근본적인 과제인 **용량 제한 차량 라우팅 문제 (CVRP)**를 다룬다.

저자들은 현재 신경 조합 최적화 (NCO) 접근법의 중요한 한계를 식별한다:

1. 자기회귀 (AR) 병목 현상: 지배적인 NCO 방법은 토큰 단위로 솔루션을 구성하여 순차적 디코딩 비용, 공간적 대칭성에 대한 민감성, 그리고 분포 외 (OOD) 일반화의 취약성을 초래한다.
2. 방법론적 단절: 여행 세일즈맨 문제 (TSP) 가 순수한 라우팅 작업인 반면, CVRP 는 본질적으로 용량 가능 클러스터로 고객을 분류하는 **분할 문제 (bin-packing)**와 라우팅이 결합된 것이다. 기존 NCO 방법들은 종종 CVRP 를 투어 생성 작업으로 취급하여 용량制약을 값비싼 사후 검색으로 강제한다.
3. 벤치마크 불일치: 표준 벤치마크는 노드 좌표를 독립 동일 분포 (i.i.d.) 로 재샘플링하여, 매일 다른 수요로 동일한 지역을 라우팅하는 실제 물류에서 전형적인 고정 지리적 지지 (예: 도시의 도로망) 를 무시한다.

방법론: 신경 CFRS

저자들은 고전적인 클러스터링 우선 - 라우팅 차후 (CFRS) 패러다임에 기반한 최초의 순수 비자기회귀 (NAR), 원샷 신경 프레임워크인 Neural CFRS를 제안한다. 모델을 순차적으로 라우트를 생성하는 대신, 고객들을 차량 클러스터에 전역적이고 미분 가능한 방식으로 할당한 후 독립적인 TSP 를 병렬로 해결한다.

아키텍처는 세 단계로 운영된다:

1. 사전 학습 및 공간 지지 사전 ($\Psi$)

실제 물류의 고정된 지리를 해결하기 위해, 저자들은 고정된 잠재 고객 위치 집합 ($X$) 에 대해 **공간 마스킹 오토인코더 (SMAE)**를 사전 학습한다.

• SMAE 는 절대 좌표를 소비하지 않고 쌍별 유클리드 거리와 로컬 $k$-NN 연결성을 재구성함으로써 $E(2)$-불변 (병진, 회전, 반사 불변) 임베딩을 학습한다.
• 이러한 동결된 임베딩 ($\Psi$) 은 "공간 어휘" 역할을 하여, 하위 모델이 동일한 지도에서 새로운 수요 인스턴스에 대해 기하학을 재학습하지 않고도 일반화할 수 있게 한다.

2. 1 단계: 시드 생성

**시드 트랜스포머 (ST)**는 초기 클러스터 중심 ("시드") 으로 작용할 노드 하위 집합을 식별한다.

• 시드로서 작용하는 노드에 대한 주변 확률을 예측하고 유사 노드를 그룹화하기 위해 대비적 표현을 학습한다.
• 용량 인식 탐욕적 디코딩 전략은 추정된 차량 대수 $K$만큼의 시드를 선택하고, 대비적 유사성에 기반하여 근처 노드를 이러한 시드에 탐욕적으로 포장하여 공간적 분산과 용량 가능성을 보장한다.

3. 2 단계: 미분 가능한 최적 수송을 통한 전역 할당

**클러스터링 트랜스포머 (CT)**는 고객과 선택된 시드 사이의 잠재 거리 ($\Delta_{ij}$) 를 계산한다.

• 미분 가능한 완화: 전역 용량制약을 엔드투엔드로 강제하기 위해, 이산적인 용량 할당 문제 (CAP) 를 연속적인 최적 수송 (OT) 문제로 완화한다.
• Sinkhorn-Knopp (SK) 알고리즘: 모델은 엔트로피 정규화된 OT 목적 함수를 최소화하여 용량制약을 만족하는 연속 수송 계획 ($\hat{Y}$) 을 생성한다. 이 계획은 이산 할당 행렬을 위한 미분 가능한 대리 역할을 한다.

4. 3 단계: OR 디코딩

연속 수송 계획 $\hat{Y}$는 최종 이산 클러스터를 복구하기 위해 정확한 혼합 정수 계획법 (MIP) 솔버를 안내한다.

• 희소화: 모델은 높은 확신 임계값을 사용하여 높은 확신 할당을 고정 (Hard Assignment) 하거나 낮은 확률 간선을 가지치기 (Sinkhorn-Guided Sparsification) 한다.
• 이는 정확한 솔버의 검색 공간을 극적으로 줄여주며, 나머지 하위 문제들을 상용 솔버 (예: LKH-3) 를 사용하여 독립적인 TSP 로 해결한다.

주요 기여

1. 비자기회귀 프레임워크: 문제를 전역 분할 작업으로 재구성하여 순차적 디코딩 병목 현상을 우회하는 CVRP 를 위한 최초의 순수 NAR 신경 솔버를 도입한다.
2. 미분 가능한 용량 제약: 엔트로피 최적 수송을 사용하여 엔드투엔드 미분 가능한 레이어를 개발하여 신경 할당과 정확한 정수 계획법 간의 간극을 메운다.
3. 대칭성 추상화: 아키텍처가 구성에 의해 $E(2)$ 공간 대칭성, 인터-라우트 치환, 인트라-라우트 이동 대칭성을 본질적으로 추상화한다는 공식적인 이론적 보장을 제공한다. 값비싼 데이터 증강의 필요성을 제거한다.
4. 공간 지지 사전: 고정된 지리에서 사전 학습된 공간 어휘를 활용하는 것이 극도의 매개변수 효율성과 대규모 문제 크기에 대한 제로샷 확장을 가능하게 함을 입증한다.

실험 결과

본 프레임워크는 고정 지리에서의 일정 용량 운영 설정과 표준 벤치마크 (i.i.d. 좌표) 모두에서 평가되었다.

• 제로샷 일반화: Neural CFRS 는 $N=1000$명의 고객까지 분포 외 인스턴스에 대해 견고하게 확장된다.
  • 일정 용량 설정 ($Q=50$) 하에서 $N=1000$ 인스턴스에서 30 초 이내에 4% 미만의 최적성 갭을 달성한다.
  • 놀랍게도, 초경량 단일 레이어 아키텍처(682K 매개변수) 는 이 규모에서 약 5% 의 갭을 유지하여 대규모 라우팅에 깊은 아키텍처가 필요하다는 통념에 도전한다.
• 표준 벤치마크: 표준 CVRP100 벤치마크에서 정확한 디코딩 변형은 **2.73%**의 최적성 갭을 달성하여 탐욕적 자기회귀 베이스라인 (예: POMO, BQ, LEHD) 보다 우수하고 고전적 휴리스틱과 경쟁한다.
• 효율성: 이 방법은 초기 클러스터링을 위한 사후 지역 검색에 대한 의존성을 완전히 제거하고, 대신 정확한 솔버를 안내하는 신경 모델의 능력에 의존한다.

중요성과 주장

본 논문은 Neural CFRS가 라우팅 문제를 위한 NCO 에서 구조적 전환을 나타낸다고 주장한다:

• 딥러닝 강점과의 정렬: 긴 순차적 투어를 구성하도록 강요하는 대신, 전역 컨텍스트에서 유사성과 할당을 학습하는 딥러닝의 능력을 활용한다.
• 실제 세계 타당성: 고정된 공간 지지와 일정 용량을 존중함으로써, 이 프레임워크는 실제 물류의 감가상각적이고 지연에 민감한 영역과 일치하며, 정적 서비스 영역에서의 일상적 라우팅을 위한 실현 가능한 경로를 제공한다.
• 패러다임 전환: 결과는 작업별 맞춤화 (예: 공간 지지에서의 사전 학습) 가 광범위한 미세 조정 없이 최첨단 결과를 가져올 수 있으며, 올바른 귀납적 편향 (CFRS 분해 및 공간 사전) 과 결합될 때 단순하고 얕은 아키텍처가 매우 효과적일 수 있음을 시사한다.

저자들은 프레임워크가 경쟁력 있게 수행하지만, 향후 연구는 더 큰 인스턴스로의 제로샷 확장성을 개선하고 엣지 케이스에서 용량 활용과 공간 효율성 간의 균형을 맞추는 모델의 능력을 정교화하는 데 초점을 맞춰야 한다고 결론지었다.