Attention, Learn to Solve Routing Problems!

12분 분량

Attention, Learn to Solve Routing Problems!

Digest (CISELQ)

  • Context: TSP·VRP 등 라우팅(Routing) 문제는 NP-hard로, 문제 유형별 전용 heuristic(Concorde, LKH, OR-Tools)을 정교하게 설계해야 하는 부담이 있었다. Pointer Network(Vinyals 2015) 및 Bello et al.(2016)이 신경망 기반 학습으로 TSP를 풀려 했으나 RNN 기반 구조의 표현력과 학습 안정성 한계가 존재했다.
  • Issue: RNN 기반 Pointer Network는 순서 의존적(sequence-dependent)이어서 순서가 의미 없는 node 집합을 인코딩하기에 부적합하고, REINFORCE의 critic(value function) baseline은 학습이 불안정하며, 기존 학습 기반 해법의 성능이 전통적 heuristic에 크게 못 미쳤다.
  • Solution: Transformer 스타일의 Multi-Head Attention encoder로 node 집합을 permutation-invariant하게 임베딩하고, context-based attention decoder로 한 node씩 순차적으로 선택하는 autoregressive policy를 학습한다. 학습은 REINFORCE에 greedy rollout baseline(동일 policy의 greedy decode로 baseline 구성)을 도입해 안정적으로 수행한다.
  • Evaluation: TSP20/50/100, CVRP(Capacitated VRP), SDVRP(Split-Delivery), OP(Orienteering), PCTSP(Prize-Collecting), SPCTSP(Stochastic) 등 6개 라우팅 변형에서 동일 하이퍼파라미터로 학습/평가. Concorde·LKH·Gurobi·OR-Tools와의 optimality gap 및 Bello et al., Nazari et al. 등 선행 학습 기반 방법과 비교.
  • Limits: Node 100까지만 검증, 더 큰 instance로 확장 시 O(N^2) attention 메모리·연산 비용이 병목. Construction heuristic 스타일이라 local search와 달리 해를 반복 개선하지 못함. Stochastic·constraint 강한 문제에서는 여전히 전용 solver에 미치지 못함.
  • Questions: 수천 node 규모로의 scalable extension? Attention 기반 policy가 2-opt류 local search와 결합하면? Multi-depot·time-window 등 더 복잡한 routing에 일반화 가능한가?

섹션별 요약

Introduction

논문은 학습 기반 heuristic이 정교한 수작업 휴리스틱을 대체할 수 있다는 가설에서 출발한다. Bello et al.(2016)의 Pointer Network + RL 접근이 있었으나 TSP100 성능이 최적에 크게 못 미쳤고, RNN 기반 encoder는 node 순서에 인위적으로 의존한다는 구조적 결함을 지적한다. 저자는 Transformer(Vaswani 2017) 구조에서 영감받아 순서 불변(permutation-invariant) encoder를 도입하고 policy gradient baseline을 단순화하여 다양한 routing 문제에 단일 모델·단일 하이퍼파라미터로 대응하겠다고 선언한다.

Methods

  • Encoder: 각 node의 2D 좌표(혹은 문제별 feature)를 선형 임베딩 후 Multi-Head Self-Attention(MHA) 블록 N=3회 적용. 각 블록은 MHA + skip + BatchNorm + FFN + skip + BatchNorm으로 구성. 결과로 node embedding {h_i}와 graph embedding h̄ = mean(h_i)를 얻는다.
  • Decoder: Autoregressive. 시점 t의 context는 [h̄, h_{π_{t-1}}, h_{π_1}] (또는 문제별 state concat). Context vector를 glimpse MHA로 refine한 뒤, node 후보에 대해 single-head attention logit을 계산하고 tanh·C=10으로 clipping → masked softmax로 확률 분포 형성 → 다음 node 선택.
  • Training(REINFORCE + Greedy Rollout Baseline): Policy π_θ에서 solution을 sampling하여 cost L(π)를 계산, baseline b(s) = L(greedy π_{θ_BL}(s))로 advantage 계산. θ_BL은 주기적으로(매 epoch) paired t-test로 현재 policy가 유의하게 우수하면 업데이트. Critic 네트워크 대비 구현이 간단하고 variance가 낮다.

Results

  • TSP20/50/100에서 Optimal(Concorde) 대비 gap: 0.34% / 1.76% / 4.53% (greedy) → sampling/beam search 시 더 개선. Bello et al. Pointer Net 대비 전 구간 우위.
  • CVRP20/50/100에서 LKH3 대비 근접, OR-Tools 및 Nazari et al. RL 대비 우위.
  • OP·PCTSP·SPCTSP에서도 Gurobi/전용 heuristic과 근접한 gap 달성.
문제NOurs (greedy) gapOurs (sampling) gapBaseline(최적/전통)
TSP1004.53%2.26%Concorde 0%
CVRP1007.34%~LKH3 0%
OP(dist)100~1.9%~Gurobi 0%
PCTSP100~2%~OR-Tools

Discussion

Attention encoder의 permutation invariance가 routing에 본질적으로 유리함을 실증했고, greedy rollout baseline이 value network 없이도 낮은 variance로 수렴함을 보였다. 동일 아키텍처로 6개 문제를 모두 푸는 transfer-ready 성질이 학습 기반 combinatorial optimization의 실용성을 높였다.

Insights

  • Set 구조 문제에는 RNN보다 self-attention이 구조적 bias 측면에서 자연스럽다.
  • RL baseline을 자기 자신의 greedy decode로 두는 것은 단순·강력하며 이후 RL4CO 연구의 표준이 되었다.
  • 단일 모델·단일 하이퍼파라미터로 여러 variant를 푼다는 점은 foundation-style combinatorial solver 가능성을 시사.

Discussion Points

  • Instance 크기를 N≥1000까지 어떻게 확장할 것인가(sparse/linear attention, divide & conquer)?
  • Construction policy를 improvement policy(2-opt, LNS)와 결합해 closed gap을 더 줄일 수 있는가?
  • Real-world constraint(time window, multi-depot, dynamic)에 대한 일반화?

메타데이터

항목내용
제목Attention, Learn to Solve Routing Problems!
저자Wouter Kool, Herke van Hoof, Max Welling
소속University of Amsterdam, ORTEC
학회ICLR 2019
arXiv1803.08475
코드https://github.com/wouterkool/attention-learn-to-route
키워드Attention, Transformer, REINFORCE, TSP, VRP, Combinatorial Optimization

왜 이 연구를 하는가?

라우팅 문제는 물류·배송·반도체 설계·유전체 서열화 등 산업 전반에 편재하며, 문제 유형이 조금만 바뀌어도(용량 제약, 시간 창, 확률적 보상) 전용 heuristic을 새로 설계해야 한다. 이 재설계 비용을 줄이고, 데이터로부터 문제 구조를 “학습”하여 일반화 가능한 solver를 만드는 것이 핵심 동기다. 기존 Pointer Network RL 접근은 성능·안정성 모두 부족했기에, Transformer 구조와 개선된 baseline을 결합해 학습 기반 접근을 실제 전통 solver와 경쟁 가능한 수준으로 끌어올리는 것이 본 연구의 목적이다.

방법 (Method)

flowchart TD
    A[Node coords x_i] --> B[Linear embed h_i^0]
    B --> C[N=3 x MHA Block<br/>MHA+BN+FFN+BN]
    C --> D[Node embeddings h_i]
    D --> E[Graph embed h_bar = mean h_i]
    D --> F[Decoder Context<br/>h_bar, h_prev, h_first]
    E --> F
    F --> G[Glimpse MHA]
    G --> H[Single-head Attention<br/>tanh clip C=10]
    H --> I[Masked Softmax]
    I --> J[Select next node pi_t]
    J -->|autoregressive| F
    J --> K[Tour pi, cost L]
    K --> L[REINFORCE gradient<br/>L - b times grad log p]
    K --> M[Greedy Rollout baseline<br/>b = L greedy pi_BL]
    M --> L
    L --> N[Update theta]
    N -.paired t-test.-> M

발견

#발견증거
1Attention encoder가 Pointer Net 대비 TSP 전 구간에서 gap을 큰 폭으로 감소TSP100 gap 4.53% vs Bello et al. ~6.9%
2Greedy rollout baseline이 critic baseline보다 빠르게 수렴·낮은 variance§4 학습 곡선
3단일 모델·동일 hparam으로 6개 routing variant 경쟁력 있는 해Table 1–3
4Sampling(1280 solutions)으로 gap을 2~3배 추가 감소TSP100 2.26%
5OR-Tools·Nazari RL 대비 CVRP 전 구간 우위Table 2

이론적 의의

  • 구조적 inductive bias: Set을 다루는 combinatorial 문제에서 self-attention의 permutation invariance가 원리적으로 적합함을 정량적으로 입증.
  • RL baseline 설계: “자기 자신의 greedy 정책”을 baseline으로 사용하는 아이디어는 actor–critic과 달리 별도 네트워크 없이 variance를 줄일 수 있음을 보여 RL4CO 표준 기법이 되었다.
  • Unified solver 패러다임: 문제별 손작업 heuristic의 대안으로, 단일 아키텍처로 다양한 variant를 학습할 수 있는 foundation-style 접근 가능성을 제시.

재현성 및 신뢰도 평가

기준등급근거
코드 공개A저자 공식 repo(wouterkool/attention-learn-to-route) 전체 공개
데이터A랜덤 인스턴스 생성기 코드 제공, seed 명시
하이퍼파라미터A논문 Appendix·config 파일에 전량 기재
결과 재현A학계에서 수차례 재현됨(RL4CO 벤치마크)
근거 품질AConcorde/LKH3/Gurobi 등 최적/준최적 기준선과 직접 비교
일반화BN≤100·2D Euclidean 위주, 대규모·실세계 constraint는 후속 과제

관련 연구

  • Vinyals et al. 2015, Pointer Networks — 시퀀스 인덱스 출력의 원조.
  • Bello et al. 2016, Neural Combinatorial Optimization with RL — Pointer Net + actor-critic TSP.
  • Nazari et al. 2018, Reinforcement Learning for Solving the VRP — RNN 기반 VRP RL.
  • Vaswani et al. 2017, Attention Is All You Need — Transformer 구조의 기반.
  • Deudon et al. 2018, Learning Heuristics for the TSP by Policy Gradient — 유사 시기의 attention + RL TSP.
  • Kool et al. 후속 연구 및 POMO(2020), AM-D 등 이 논문을 직접 확장한 계열.

원자적 인사이트

  1. Set 구조에는 self-attention이 자연스럽다: Node들의 순서가 의미 없을 때 RNN 인코딩은 인위적 순서 편향을 만든다. MHA는 permutation-equivariant하여 라우팅처럼 “집합을 읽고 순서를 출력”하는 문제의 inductive bias와 정합한다.
  2. Greedy rollout baseline은 가장 저렴한 저분산 baseline 중 하나다: Critic 네트워크를 따로 학습할 필요 없이, 같은 정책의 결정적 decode 결과를 baseline으로 쓰면 on-policy advantage가 평균 0 근처로 유지되어 REINFORCE variance를 급감시킨다.
  3. Tanh clipping(C=10)은 exploration-exploitation 균형 장치: Attention logit을 [-C,C]로 제한하여 softmax가 지나치게 확정적(peaky)이 되는 것을 막아 초기 학습 붕괴를 방지한다.
  4. Single model, many problems: 문제별 state concat만 바꾸면 동일 아키텍처로 TSP/CVRP/OP/PCTSP까지 다룬다는 것은 combinatorial foundation model의 가능성을 시사한다.

핵심 용어 정리

  • Pointer Network: 입력 시퀀스의 원소 인덱스를 출력하는 seq2seq 변종. 가변 출력 어휘 문제를 attention으로 해결.
  • REINFORCE: Monte Carlo policy gradient. grad J = E[(R - b) grad log pi].
  • Greedy Rollout Baseline: 학습 중인 policy의 argmax decode로 얻은 cost를 baseline으로 사용. Paired t-test로 baseline policy를 주기 갱신.
  • Optimality Gap: (solver 해 − 최적)/최적 × 100%. 학습 기반 방법의 평가 지표.
  • CVRP / OP / PCTSP: 각각 용량 제약 VRP, Orienteering(상금 최대화), Prize-Collecting TSP(미방문 패널티 + 방문 보상).
  • Multi-Head Attention(MHA): h개 head로 병렬 self-attention을 수행해 다양한 관계 패턴 포착.

태그

Attention Transformer ReinforcementLearning CombinatorialOptimization TSP VRP Routing REINFORCE ICLR2019 RL4CO