Paper) Reinforcement Learning for Solving the Vehicle Routing Problem

 

https://arxiv.org/abs/1802.04240

해당 논문을 인용한 논문들

https://scholar.google.com/scholar?as_ylo=2021&hl=en&as_sdt=2005&sciodt=0,5&cites=7637833782499120275&scipsc= 

Google Scholar

 

목차

Abstract

why

차량 라우팅 문제(VRP)는 수십 년 동안 응용 수학과 컴퓨터 과학에서 연구되어 온 조합 최적화 문제입니다. VRP는 정확하고 휴리스틱한 알고리즘이 많이 제안돼 계산적으로 어려운 문제로 알려져 있지만 빠르고 안정적인 솔루션 제공은 여전히 어려운 과제입니다.

가장 간단한 형태의 VRP에서는 하나의 정전식 차량이 여러 고객 노드에 항목을 배달합니다.

차량이 소진되면 창고로 돌아가 추가 항목을 픽업해야 합니다. 목표는 다음과 같은 작업을 최적화하는 것입니다. 최대값에 도달하기 위해 창고라고 하는 지정된 노드에서 모든 시작 및 끝 경로 총 차량 거리 또는 평균 서비스 시간의 음수인 경우가 많습니다.

이 문제는 계산적으로 최적의 상태로 해결하기 어려우며[12] NP-하드 문제로 분류됩니다. VRP에 대한 개요는 예를 참조하십시오.

goal

본 논문에서는 보강학습(RL)을 이용하여 다양한 조합 최적화 문제를 해결할 수 있는 프레임워크를 개발하고 이를 적용하여 VRP를 해결할 수 있는 방법을 보여줍니다.

이러한 목적을 위해, 우리는 최적의 솔루션을 일련의 의사결정으로 볼 수 있는 문제의 마르코프 의사결정 프로세스(MDP) 공식을 고려한다. 이를 통해 RL을 사용하여 "바람직한" 시퀀스를 디코딩할 확률을 높여 거의 최적에 가까운 솔루션을 생성할 수 있습니다.

순진한 접근 방식은 모든 인스턴스를 별도로 고려하여 인스턴스별 정책을 교육하는 것입니다. 이 접근법에서, RL 알고리즘은 많은 표본, 아마도 수백만 개를 채취해야 한다. 문제의 기초가 되는 MDP는 양질의 솔루션을 생산할 수 있어야 합니다.

명백하게, 이것은RL 방법은 솔루션 품질뿐만 아니라 런타임 측면에서도 기존 알고리즘과 비교할 수 있어야 하기 때문에 실용적이지 않습니다.

예를 들어, 본 논문에서 연구한 모든 문제에 대해 1초 이내에 거의 최적에 가까운 솔루션을 생산할 수 있는 방법을 사용하고자 합니다.

또한 이러한 순진한 접근 방식을 통해 학습된 정책은 학습에 사용된 정책 이외의 인스턴스에는 적용되지 않습니다. 예를 들어 고객의 위치나 요구를 변경하는 등 문제 설정이 약간 교란된 후에는 정책을 처음부터 다시 구축해야 합니다.

Conclusion

제안된 알고리즘이 VRP에만 국한되지 않는다는 점에 주목해 bin-packing, job-shop, and flow-shop 등 다른 조합 최적화 문제에 적용하는 것이 향후 연구의 중요한 주제가 될 것으로 보인다.

이 방법은 실현 가능한 솔루션을 찾는 검증자뿐이기 때문에 매우 매력적입니다. 또한 정책이 얼마나 잘 작동하고 있는지 보여주는 보상 신호이기도 합니다.

많은 고전적 휴리스틱과 달리, 우리의 제안은 방법은 증가하는 문제 규모에 따라 잘 확장되며, 경쟁력 있는 솔루션 시간으로 우수한 성능을 제공합니다. 특히 동적으로 변화하는 VRP에서 거리 행렬 계산이 복잡할 수 있습니다.

우리는 또한 훨씬 더 복잡한 확률적 버전의 VRP에서 알고리즘의 성능을 보여줍니다.

result & discussion

---

Introduction

• 배경 지식

Neural Combinatorial Optimization

• 지난 몇 년 동안, 인공지능의 최근 발전을 이용하여 조합 최적화 문제를 해결하기 위한 여러 방법이 개발되었습니다.
• 초창기 논문(Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692–2700, 2015.)
• Pointer Network는 인코더 시퀀스의 길이에 불변하므로 Pointer Network를 사용하면 모델이 소스 시퀀스에 의해 출력 시퀀스 길이가 결정되는 조합 최적화 문제에 적용할 수 있습니다.
  • Pointer Network 아키텍처를 지도 학습 방식으로 사용하여 ground truth 최적(또는 휴리스틱) 솔루션에서 거의 최적화된 TSP(Traveling Salesman Problem) 투어를 찾습니다.
  • 이러한 감독 의존성으로 인해 Pointer Network는 학습 중에 제공되는 솔루션보다 더 나은 솔루션을 찾을 수 없습니다.
• 이번 논문과 비슷한 아이디어로 RL을 사용하여 Pointer Network로 모델링된 정책을 최적화하는 최적화 프레임워크입니다.
  • Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016.
  • TSP 및 배낭 문제와 같은 몇 가지 고전적인 조합 최적화 문제를 사용하여 아키텍처의 효율성과 일반성을 보여줍니다.
  • 관련 주제에 대해, 다이 외. [11] 그래프 내장 구조[10]와 심층 Q-러닝(DQN) 알고리즘을 사용하여 그래프를 통해 최적화 문제를 해결합니다[25]. 가중 노드 및 에지가 있는 그래프로 VRP를 나타낼 수 있지만 VRP에서는 특정 노드(예: 디포)를 여러 번 방문할 수 있기 때문에 제안된 모델이 직접 적용되지 않습니다.
    • • Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015.

detail

모델

종료 조건

• 문제에 따라 달라질 수 잇다.
  • 예를 들어, 본 작업에서 고려하는 VRP에서 종료 조건은 더 이상 만족해야 할 수요가 없다는 것입니다.
• 이 프로세스는 길이의 시퀀스를 생성합니다. T, Y = {$y_t$, t = 0, ..., T}, 입력 길이 M과 다른 시퀀스 길이를 가질 수 있습니다.
• 예를 들어, 차량이 주유소로 여러 번 돌아가야 하기 때문입니다.
• 저자는 또한 Yt 표기법을 사용하여 t 시간까지 디코딩된 시퀀스를 나타냅니다. 즉, Yt = {y0, · · · , yt}.
• 해당 모델에서는 문제의 제한조건을 만족하면서, 손실 함수를 최소화하는 시퀀스 y를 생성하는 확률적인 정책을 찾아낼 수 있기를 기대합니다.
•  

  

$h_t$는 이전 히스트로의 정보를 요약하는 RNN decoder이고, g는 인풋 사이즈만큼의 길이를 가진 것을 출력하는 함수라고 합니다.

저자는 이 모델은 보다 고전적인 조합 최적화 문제를 모두 처리할 수 있다고 합니다. 즉, 정적 설정뿐만 아니라 동적으로 변경되는 설정에서도 마찬가지입니다.

• 정적 조합 최적화에서
  • X0 완전 우리가 해결하고자 하는 문제를 규정합니다.
  • 예를 들어 VRP에서 X0은 모든 고객을 포함합니다. 위치, 요구 사항 및 디포 위치. 그런 다음 나머지 요구 사항은 차량 목적지 및 그 부하에 따라 업데이트됩니다.

Limitations of Pointer Networks

• knapsack 문제는 잘 풀었지만, 더 복잡한 문제는 풀지 못했다고 합니다.
• 기존 모델에서는 한 번씩 움직임에 따라서 동적으로 변하는 상태가 되기 때문에 어렵다고 합니다.

제안하는 모델

저자들은 RNN 인코더가 인코더에 추가적인 복잡성을 추가하지만 실제로는 필요하지 않다고 주장하며, 이 접근 방식을 생략함으로써 훨씬 더 일반적인 접근 방식을 만들 수 있습니다.

입력은 순차적인 정보를 전달합니다. 예를 들어, 텍스트 번역에서는 정확한 번역을 위해 단어 조합과 상대적 위치를 캡처해야 한다.

하지만 여기서 중요한 것은 입력 세트에 의미 있는 순서가 없는데 왜 조합 최적화 문제를 위해 인코더에 데이터를 저장해야 하는가입니다.

예를 들어, VRP에서 입력은 각각의 요구를 가진 주문되지 않은 고객 위치의 집합이며, 그 순서는 의미가 없습니다. 임의의 순열은 원래 입력과 동일한 정보를 포함합니다.

그러므로, 우리의 모델에서는, 우리는 단순히 인코더 RNN을 생략하고 RNN 숨겨진 상태 대신 내장된 입력을 직접 사용합니다.

이 수정에 의해, 많은 계산상의 복잡성이 사라지며, 그 결과도 줄어들지 않는다고 합니다.

모델의 효율성. 부록 A에서 우리는 이 주장을 검증하기 위한 실험을 제공합니다.

2개의 메인 요소로 구성되어 있습니다.

1. 인풋을 d 차원의 벡터 공간으로 맵핑한 임베딩 셋입니다.
   • 입력의 서로 다른 요소에 해당하는 임베딩이 여러 개 있을 수 있지만 입력 간에 공유됩니다.
2. 각 decoding step마다 입력을 가리키는 디코더입니다.
   • RNN을 사용하여 디코더 네트워크를 모델링합니다.

정적 요소를 디코더의 네트워크의 입력으로 정보를 줍니다.

동적 요소도 디코더에 대한 입력이 될 수 있지만, VRP에 대한 우리의 실험은 그렇게 함으로써 어떤 개선도 제시하지 못하므로, 동적 요소는 다음에 설명된 주의 계층에서만 사용됩니다.

Attention Mechanism

Attention Mechanism은 입력의 다른 부분을 다루기 위한 구별 가능한 구조입니다.

2번 그림에서 각 decoder step i에서는 Vinals 등과 유사한 맥락 기반 주의 메커니즘(context-based attention mechanism)을 활용합니다.

• 컨텍스트 정보는 가변 길이 선형 벡터를 사용하여 인풋으로부터 관련된 정보를 뽑아줍니다.
• at는 모든 입력 데이터 포인트가 다음 디코딩 단계 t에 얼마나 관련될 수 있는지 지정합니다.

s는 static d는 dynamic 정보를 의미하고, 아래 코드는 attention score를 얻는 것을 의미한다.

여기서 $W_a$ 와 $W_b$ 가 학습 가능한 변수이다.

Model Symmetry : 빈얄 외. [33] 정렬(sorting)과 같이 명확한 입력 순서가 없는 작업에서 입력이 네트워크 문제로 공급되는 순서를 경험적으로 입증하는 시퀀스 대 시퀀스 모델의 확장에 대해 논의한다.

Pointer Networks를 조합 최적화 문제로 사용할 때도 이와 유사한 문제가 발생합니다. 그러나, 본 논문에서 제안된 모델은 임베딩과 주의 메커니즘이 입력 순서에 불변하기 때문에 그러한 복잡한 문제를 겪지 않습니다.

학습 방법

• policy gradient 방식을 사용함
• actor critic 방식을 사용한 것으로 보인다.
• actor network
  • 주어진 decision step에서 다음 액션에 대한 확률 분포 예측
  • dynamic element
    • 갔다 오고 나서 남아있는 물량 정보를 사용함.
    • attention layer
  • LSTM RNN (128) 사용했다고 함
• critic network
  • 주어진 상태로부터 발생한 모든 문제 사례에 대한 보상 추정
  • two hidden layer
• xavier initialization
• REINFOCRMENT ALGORITHM 사용함
• ADAM
  • 0.0001
• BATCH SIZE 128
• clip gradient than 2
• dropout 0.1(decoder)
• entropy regularizer
  • local optimal 방지 하지만 실제로 효과는 없었다고 함
• 임베딩의 경우, in-width는 입력 길이이고, filter 수는 D이며, in-channel 수는 x 요소의 개수인 임베딩에 1차원 컨볼루션 레이어를 사용하므로 임베딩 레이어가 없는 학습은 항상 열등한 솔루션을 제공합니다.
  • 한 가지 가능한 설명은 정책이 고차원 입력 표현에서 유용한 기능을 훨씬 효율적으로 추출할 수 있다는 것입니다.
  • 우리의 내장은 AFFINE TRANSFORMATION이므로, 내장된 입력 거리가 원래의 2차원 유클리드 거리에 비례하지 않아도 됩니다.

VRP를 위한 강화학습 알고리즘

리워드

$R_t$ is the number of demands satisfied at time t

리워드는 discrete time mdp($\tau_t$ $\frac{R_t}{\tau_t} - \tau_{t-1}}$을 리워드로 했다.

실험

다음과 같은 상황을 가정함

제한된 용량을 가진 한 대의 차량이 제한된 수요로 지리적으로 분산된 많은 고객에게 품목을 공급하는 역할을 담당합니다.

차량의 적재량이 부족하면 다시 주유소로 돌아갑니다. 시운전 t 차량의 잔여 하중을 나타냅니다.

목표는 전체 경로 길이를 최소화하는 동시에 고객의 요구를 모두 충족하는 것입니다.

이 문제를 흔히 CVRP(Capacited VRP)라고 부르는데, 우리는 이것을 간단히 VRP라고 부르겠습니다.

노드 위치와 디맨드는 고정된 분포에서 랜덤하게 생성되는 것으로 가정합니다. 특히, 고객 및 창고 위치는 단위 제곱[0,1]×[0,1]에서 무작위로 생성됩니다. 노출의 단순화를 위해, 우리는 각 노드의 요구가 무작위로 균일하게 선택된 {1, ..., 9}의 이산형 숫자라고 가정한다.

그러나 수요 값은 연속 분포를 포함한 모든 분포에서 생성될 수 있습니다.

우리는 차량이 0시에 창고에 있다고 가정합니다.

따라서 디코더에 대한 첫 번째 입력은 창고의 위치를 내장하는 것입니다.

각 디코딩 단계에서 차량은 다음 단계에서 방문할 고객 노드 또는 depot 중에서 선택합니다.

고객 노드 i 방문 후 요구 사항 및 차량 하중은 다음과 같이 업데이트됩니다.

2개의 다른 디코더

• 각 decoding step에서 다음 목적지를 선택할 때 가장 높은 확률이 있는 노드를 가는 greedy
• 빔 검색(BS) - 가장 가능성이 높은 경로를 추적한 다음 최소 둘러보기 길이를 가진 경로를 선택합니다.

저자의 결과는 빔 검색(BS) 알고리즘을 적용함으로써 계산 시간을 조금만 늘려도 솔루션의 품질을 향상시킬 수 있다는 것을 보여준다고 합니다.

빠른 학습

• 빠른 학습을 위해서 masking scheme을 적용함
• 실행 불가능한 솔루션의 로그 확률을 -무한대로 설정하거나 특정 조건이 충족되면 솔루션을 강제 적용합니다.
• VRP에서는 다음과 같이 적용했다고 합니다.
  1. 수요가 없는 곳은 방문하지 않는다.
  2. 모든 고객 노드들은 정확히 남아있는 것이 0이 된다면, 마스크 된다.
  3. 현재 차량 부하보다 수요가 큰 고객을 마스킹합니다

이 마스킹 방식에서는 차량이 방문할 때 고객의 모든 요구를 충족해야 합니다.

그러나 모델링 중인 상황에서 분할 배송이 가능한 경우 1개 (3번의 제한은 풀 수도 있다)

• 실제로, 마스킹이 완화되어 분할 배송이 가능하므로, 솔루션은 주어진 고객의 요구를 여러 경로로 할당할 수 있습니다.
• 이러한 속성은 매력적인 행위라 할 수 있다. 실제로는 이런 경우가 흔하지만, 전통적인 VRP문제에서는 이 부분이 무시가 된다.

다른 VRP 문제로 확대 가능

제안된 프레임워크는 여러 창고의 문제로 쉽게 확장될 수 있습니다. 해당 상태 전환 기능(state transition function)과 마스킹 절차만 구성하면 됩니다.

다양한 측면 제약 조건도 포함할 수 있습니다. 즉, 보상을 처벌하여 부드러운 제약 조건을 적용하거나 마스킹 제도를 통해 타임 윈도우와 같은 엄격한 제약 조건을 적용할 수 있습니다.

그러나 이러한 체계를 설계하는 것은 어려운 작업일 수 있으며, 최적화 문제 자체보다 더 어려울 수 있습니다. 여러 대의 차량을 탑재한 VRP도 흥미로운 확장이다. 차량이 독립적으로 이동하는 가장 간단한 경우에는 동일한 고객 노드를 가리키는 차량을 피하기 위해 공유 마스킹 방식(shared masking scheme)만 설계해야 합니다.

차량 간의 경쟁이나 협업을 통합하는 것 또한 다중 에이전트 RL(Multi-agent RL)과 관련된 흥미로운 연구 라인입니다.

(참고 Lucian Bu¸soniu, Robert Babuška, and Bart De Schutter. Multi-agent reinforcement learning: An overview. In Innovations in multi-agent systems and applications-1, pages 183–221. Springer, 2010.)

도움이 되는 것 같으므로, appendix도 읽어보려고 한다.

저자가 주장하는 모델 VS Pointer Network

• 성능면에서는 차이가 없지만, 속도면에서는 훨씬 빠르다고 주장한다.
•  

  

Capacitated VRP Baselines

• or-tools에 vrp를 써서 베이스라인을 만듦
• Clarke-Wright Savings Heuristic
  • vrp에서 잘 쓰는 휴리스틱한 방법
• Sweep Heuristic
  • cluster 방법을 사용함.
• or-tools
• Optimal Solution

실험 결과

예전 논문이긴 하지만, 인용도 300번이나 되고, 내용도 vrp 관련된 내용에 어떻게 적용하는지 나오기 때문에 유용한 논문이 될 것 같다. 아이디어만 받아들이는 정도로 읽으면 될 것 같다!