[논문 리뷰] Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention

View Paper" target="_blank" rel="noopener" data-mce-href="http://View Paper">http://View Paper

Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention

 

※ 다차종 상황 경로 최적화에 관한 위 논문에 대한 리뷰

Abstract

이 논문에서는 복잡한 제약 조건(차량 용량, 고객의 시간 창 등)을 고려한 차량 경로 문제(VRP)를 해결하기 위한 새로운 정책 모델을 제안한다. 기존의 기계 학습 모델들은 기본적인 VRP를 빠르게 해결할 수 있지만, 복잡한 제약 조건을 잘 다루지 못하는 한계가 있다. 본 논문에서 제안된 모델 JAMPR은 여러 경로를 동시에 시작하고 확장할 수 있으며, 이를 통해 다양한 경로와 고객을 선택하고 어려운 트레이드오프를 학습한다. 여러 투어의 공동 행동 공간에서 주의 메커니즘을 사용하여 이를 달성한다. 

 

1. Capacitated Vehicle Routing Problems (CVRP)

다차종 문제는 graph $G = [V, \epsilon, q, c]$의 환경으로 정의될 수 있다. 여기서, $G$를 구성하는 각 항목은 다음과 같다. 

1. $V$ : 총 $N + 1$개의 노드 (0번 노드인 depot과 나머지 N개의 고객 노드)
2. $\epsilon$ : 노드 $i$에서 노드 $j$로 이동하는 데 비용 $c_{ij}$ 들의 집합 $( i, j \in V, i \neq j)$
3. $q$ : 각 노드의 수요, 즉 각 고객노드가 받아야 할 물품의 양 (단, $q_0 = 0$)
4. $c$ : 비용 $c_{ij}$

더 나아가, 총 $K$개의 동일한 차량이 있고, 각 차량의 용량은 $Q$이다. 이 때, 각 노드의 수요를 $\widetilde{q_i} = \frac{q_i}{Q}$로 정규화한다. 임의의 차량 $k \in K$에 대한 경로 $s_k$는 각 경로 내에서 차량이 방문하는 모든 노드의 sequence를 포함한다. 즉, 경로 집합 S는 $S = \left\{s_1, s_2, \cdots , s_K \right\}$ 로 정의 되며, 각 원소 $s_i$는 $s_i = \left\{v(s_1), v(s_2), \cdots, v(s_n) \right\}$로 나타낼 수 있다. 이 때 $v(s_j)$는 특정 경로에 포함된 임의의 노드이다. 

 

따라서 일반적인 CVRP의 경우, 다음과 같은 제약조건 내에서 경로 최적화 문제를 푸는 것으로 볼 수 있다.

• 모든 고객이 방문된다. 즉, $\bigcup_{s \in S}^{}v(s) = V' \quad (V' = V - \left\{0\right\})$
• 고객 중복 방문 없음. 즉, $v(s_k) \cap v(s_l) = \phi$
• 용량 제약 조건 : $\sum_{i \in v(s_k)} \widetilde{q_i} \leq 1$

 

본 논문에서 위의 일반적인 상황에 Time Window를 새로운 제약으로 추가한다. 이는 고객들이 특정 시간 창 내에서만 서비스를 받을 수 있다고 가정하는 것이다. 각 고객 $i \in V$는 서비스 지속 시간 $h_i$만큼이 요구된다.

 

시간 창은 $[a_i, b_i]$ 형태로, $a_i$는 도착 가능한 가장 이른 시각, $b_i$는 도착 가능한 가장 늦은 시각을 의미한다. 이 때, 고객 $i$의 서비스가 완료되어야 하는 최종 기한 $\tau$에 대해, $b_i = \tau - h_i$로 정의될 수 있다. 예를 들어, 고객의 서비스 지속 시간이 30분이고, 서비스가 18:00까지는 완료되어야 한다고 하면, $b_i = 18:00 - 0:30 = 17:30$이 된다. 즉, 고객 $i$에 대한 시간 창은 $[a_i, 17:30]$이 되는 것이다. 

 

Depot의 시간 창 $[a_0, b_0]$는 가장 이른 출발 시간과 가장 늦은 복귀 시간을 의미하며, 전체 계획의 시간 범위를 설정한다. 

 

엣지 가중치 $c_{ij}$는 노드 $i$에서 노드 $j$로 이동하는 데 걸리는 시간 단위의 비용을 나타내며, 출발 노드 $i$의 서비스 지속 시간 $h_i$를 포함한다.

 

따라서 최종적으로, 본 논문은 분포 $p$로부터 주어진 문제를 샘플링하고, 주어진 비용 함수(cost function)에 따라 비용을 최소화하는 솔버 $\hat{s}$를 학습하는 것을 목표로 한다. 수식으로 표현하면 다음과 같다.

$$min  \mathbb{E}_{(c, q, a, b) \sim p} (cost(\hat{s}(c, q, a, b)))$$

 

 

2. Encoder 구조 및 작동 순서

논문에서 제시하는 VAMPR 모델의 인코더의 구성과 작동방식을 살펴보자. 우선 인코더의 작동 순서는 크게 다음과 같이 3단계를 따른다.

 

1. 입력 특성 변환: 각 노드의 입력 특성 $x_i$를 선형 변환하여 초기 임베딩 $z_{i}^{0}$를 생성

2. Self-Attention 블록: 세 개의 SA 블록을 거쳐 임베딩을 점진적으로 업데이트한다. 각 블록은 쿼리, 키, 밸류 생성, 어텐션 가중치 계산, 출력 계산, Residual Connection, Layer Normalization의 과정을 포함한다.

3. 최종 임베딩 생성: 세 번의 SA 블록을 거쳐 최종 임베딩 $\omega_{\text{node}}$ 를 생성

 

그럼 이제 각 인코딩 단계를 더 세부적으로 분석해보도록 하겠다.

 

1. 입력 특성 변환

• 우선, 모델은 입력 특성 $x_i$로 각 노드 $i$의 특성 벡터를 받는데, 노드의 좌표 $r_i$와 수요 $q_i$를 포함한다. 즉, $x_i = (r_i, q_i)$. 이 때, $r_i$는 2차원 벡터이고, $q_i$는 1차원 스칼라이므로 $x_i$는 3차원 벡터가 된다. 
• $x_i$를 선형변환하여 초기 임베딩 $z_{i}^{0}  \in \mathbb{R^{d_{emb}}}$를 생성 $$z_i^0 = W_{in}x_i + b_{in}$$
• 이 때, $\text{dim}(W_{in}) = d_{emb} \times d_{input}$, $\text{dim}(b_{in}) = d_{emb}$

 

2. Self-Attention (SA) 블록

• 각 Self-Attention 블록은 입력 임베딩을 업데이트하여 노드 간의 상호작용을 반영
• 각 블록은 다음과 같은 과정을 거친다.
  1. 쿼리, 키, 밸류 생성 $$\begin{align*} Q &= W_{\text{query}} z_i^{l-1}, \\ K_j &= W_{\text{key}} z_j^{l-1}, \\ V_j &= W_{\text{value}} z_j^{l-1} \end{align*}$$
     • $z_{i}^{l-1​}​​$: 이전 블록의 출력 임베딩
     • $W_{\text{query}}$, $W_{\text{key}}$, $W_{\text{value}}$ : 각 변환에 사용되는 가중치 행렬
  2. Attention 가중치 계산 $$\begin{align*} \text{attn}(Q, K_j) &= \text{softmax}\left(\frac{Q \cdot K_j}{\sqrt{d_{\text{key}}}}\right) \end{align*}$$
     • $d_{\text{key}}$: 키 벡터의 차원
  3. 출력 계산 $$\begin{align*}
     z_i^l &= \sum_{j=1}^{|Z|} \text{attn}(Q, K_j) V_j
     \end{align*}$$
  4. Residual Connection과 Layer Normalization: $$\begin{align*}
     z_i^l &= \text{BN} \left( \text{FF}_{\text{res}} \left( \text{BN} \left( \text{MHA}_{\text{res}} \left( z_i^{l-1}, Z^{l-1} \right) \right) \right) \right)
     \end{align*}$$
     
     • $\text{MHA}_{\text{res}}$: Multi-Head Attention과 Residual Connection
     • $\text{BN}_{\text{BN}}$: Layer Normalization
     • $\text{FF}_{\text{res}}$​: Feed-Forward Network와 Residual Connection

3. 최종 임베딩 생성

• 위의 과정을 총 3번 반복하여 최종 임베딩 노드 생성 $$\begin{align*}
  \omega_{\text{node}_i} &= \text{SA} \left( \text{SA} \left( \text{SA} \left( z_i^0, Z^0 \right), Z^1 \right), Z^2 \right)
  \end{align*}$$
• 여기서 $Z^0, Z^1, Z^2$는 각 블록을 거친 모든 노드의 임베딩 집합이다.

 

[의문점] 시간 창도 $x_i$에 포함되어야 하는 것 아닌가?? 왜 노드의 좌표랑 수요만 input으로 받는지, 우리가 환경 구성할 때는 시간 창도 input으로 넣어주어야 하는지

 

3. Decoder 구조 및 작동 순서

이번엔 디코더의 작동 순서를 알아보도록 하겠다. Decoder는 각 디코딩 단계 $t = \left\{1, 2, \cdots , T \right\}$에서 컨텍스트 $C^{(t)}$를 받아 현재 경로에 추가할 다음 노드를 선택한다. 이 과정은 주어진 노드 임베딩을 바탕으로 진행된다. 

 

1. 컨텍스트 구성 요소

• 그래프 임베딩 : 모든 노드 임베딩의 평균 $$
  \omega_{\text{graph}} = \frac{1}{N+1} \sum_{i=0}^{N} \omega_{\text{node}_i}
  $$으로 그래프 전체의 전반적인 상황을 요약
• 현재 차량의 잔여 용량 $Q_f^{(t)}$: 차량 $f$의 디코딩 $t$단계에서 남은 용량을 의미
• 차량이 마지막으로 방문한 노드의 임베딩 $w_{last} = w_{last(s)}^{\text{node}}$: 차량이 depot에서 시작해서 경로 $s$ 상의 노드를 방문할 때마다 업데이트

$$C^{(t)} = [\omega_{\text{graph}}; Q_f^{(t)}; w_{last}]$$

컨텍스트는 디코딩 단계를 한 번씩 거칠 때마다 업데이트된다. 디코딩 단계는 차량이 현재 노드에서 다음 노드로 넘어감과 동시에 업데이트 되므로 디코딩의 총 단계 $T$는 해당 차량의 경로 상의 노드 수와 동일해야 함을 유추할 수 있다. 

 

컨텍스트의 차원은 $2d_{emb} + 1$ 이다.  

 

★[컨텍스트의 업데이트 과정]

- 초기 단계:

• depot에서 시작할 때, 초기 컨텍스트는 다음과 같다. $$C^{(0)} = [\omega_{\text{graph}}; Q_f; \omega_{node_0}]$$
• $Q_f$ : 차량의 초기용량, $\omega_{{node_0}}$: depot의 임베딩

 

- 각 디코딩 단계 $t$:

1. 새로운 노드 $i$ 방문 후 컨텍스트 업데이트 $$C^{(t+1)} = [\omega_{\text{graph}}; Q_f^{t+1}; \omega_{node_i}]$$
2. 잔여 용량 업데이트 : $$Q_f{(t+1)} = Q_f{(t)} - q_i$$
3. 이전 노드 임베딩 업데이트 : $$\omega_{\text{last(s)}}^{node} = \omega_{node_i}$$

 

 

2. 디코더의 작동 

• 멀티-헤드 어텐션 레이어 (Multi-Head Attention Layer)
  • 컨텍스트 $C^{(t)}$와 노드 임베딩 $M = (\omega_{\text{node}_0}, \omega_{\text{node}_1}, \ldots, \omega_{\text{node}_N})$를 사용하여 어텐션을 계산. $$p_i = \text{attn}(\text{MHA}(C^{(t)}, M), \text{mask}(M))$$

마지막 단계에서는 제약 조건에 의해 제외된 노드들을 -∞로 마스킹하여 어텐션 가중치가 0이 되도록 하고, 각 노드가 다음에 선택될 확률 $p_i$ 을 계산하여, 다음에 방문할 노드를 결정한다.

 

 

4. RL 환경에서의 작용

1. 상태 (State)

1. 현재 경로 정보:
   • 현재 방문한 노드들의 리스트와 그 순서.
   • 현재 차량의 남은 용량 $Q_f^{(t)}$
   • 마지막으로 방문한 노드의 정보 $\omega_{node_i}$
2. 각 노드의 상태:
   • 노드의 좌표 $r_i$
   • 노드의 수요 $q_i$
   • 노드의 시간 창 $[a_i, b_i]$
   • 노드의 서비스 시간 $h_i$
3. 인코딩 상태:
   • 인코더를 사용하여 각 노드의 상태를 고차원 벡터로 변환.
   • 모든 노드 임베딩의 평균을 계산하여 그래프 임베딩을 생성.
   • 컨텍스트 벡터를 생성: 그래프 임베딩, 남은 용량, 마지막 방문 노드의 임베딩을 결합.

2. 행동 (Action)

1. 다음 방문할 노드 선택:
   • 디코더는 현재 컨텍스트와 노드 임베딩을 입력으로 받아, 각 노드를 선택할 확률 분포를 출력.
   • 확률 분포에 따라 다음 방문할 노드를 선택.

3. 보상 (Reward)

1. 보상 정의:
   • 경로의 효율성: 총 이동 거리, 총 소요 시간.
   • 차량 용량 준수: 용량 초과 여부.
   • 시간 창 준수: 각 노드에 시간 내에 도착했는지 여부.
2. 보상 계산:
   • 경로의 효율성에 따른 보상.
   • 용량을 초과할 경우 패널티.
   • 시간 창을 벗어날 경우 패널티.

4. 정책 학습 (Policy Learning)

1. 에피소드 단위 학습:
   • 초기 상태에서 시작하여 에피소드를 진행.
   • 각 단계에서 상태를 업데이트하고, 행동을 선택하여 보상을 받음.
   • 에피소드가 종료되면 누적 보상을 계산.
2. 정책 업데이트:
   • 강화 학습 알고리즘을 사용하여 정책 네트워크(인코더-디코더 구조)를 업데이트.
   • Q-러닝, 정책 경사법 등 다양한 알고리즘 사용 가능.

 

[구상 알고리즘]

 

1. 초기화 단계

• 환경과 정책 네트워크를 초기화.
• 환경은 노드, 차량 용량, 시간 창 등의 초기 상태를 설정.
• 정책 네트워크는 인코더-디코더 구조를 초기화.

2. 에피소드 반복

• 에피소드 수만큼 반복.
• 각 에피소드에서 다음 단계를 반복.

3. 에피소드 단계

• 초기 상태로 리셋.
• 초기 상태를 인코딩하여 첫 번째 컨텍스트 생성.

4. 디코더를 사용하여 행동 선택

• 현재 컨텍스트와 노드 임베딩을 입력으로 디코더를 사용하여 다음 방문할 노드를 선택.
• 선택된 노드를 현재 경로에 추가하고, 남은 용량과 시간을 업데이트.
• 보상을 계산하고 누적 보상을 업데이트.
• 새로운 상태를 인코딩하여 다음 컨텍스트를 생성.

5. 종료 조건 확인

• 모든 노드를 방문하거나, 용량 초과, 시간 초과 등의 종료 조건을 확인.
• 에피소드가 종료되면, 누적 보상을 계산하고 정책을 업데이트.

6. 정책 업데이트

• 강화 학습 알고리즘을 사용하여 정책 네트워크를 업데이트.
• 정책 네트워크는 인코더-디코더 구조를 포함하여 상태에 따른 최적의 행동을 학습