AlphaRouter

Abstract

Deep reinforcement learning (DRL) as routing problem solvers have shown promising results in recent studies. However, a gap between computationally-driven DRL and optimization-based heuristics exists. While a DRL algorithm is able to solve several similar-kind problem instances, traditional optimization algorithms focus on optimizing one specific problem instance. In this paper, we propose an approach, AlphaRouter, which bridges the gap between reinforcement learning and optimization for solving routing problems. Our approach first proposes attention-enabled policy and value networks, fitting to routing problems, that consist of a policy network that outputs a probability distribution over all possible nodes and a value network that outputs the expected distance from any given state. We modify Monte Carlo tree search (MCTS) for routing problems and selectively combine it with the routing problems. Our experiments demonstrate that the combined approach is promising in producing better solutions compared to RL approaches without MCTS.|심층강화학습(DRL) 방법은 차량경로최적화의 최근 연구에서 좋은 성과를 이루었다. 그럼에도 불구하고, 계산을 통해 해결하는 DRL과 최적화에 기반한 휴리스틱 방법 간에 격차가 존재한다. DRL 알고리즘은 몇가지 유사한 문제를 잘 풀 수 있는 반면, 전통적인 알고리즘은 하나의 문제를 푸는데 집중한다. 본 논문에서는 AlphaRouter라는 방법을 제안하여 강화학습과 최적화의 간극을 줄이는 것을 목표로 한다. 해당 방법론은 attention에 기반한 정책(policy)와 가치(value) 네트워크를 구성하고 경로 문제에 적용한다. 정책 네트워크는 모든 이동 가능한 노드에 대한 확률 분포를 출력하고 가치 네트워크는 어떤 state에서 예상되는 거리를 예측한다. 이어 Monte Carlo Tree Search(MCTS)를 경로 문제를 위하여 수정을 한 뒤에 선택적으로 이를 적용한다. 우리의 실험은 두가지를 조합하여 사용하는 방법이 MCTS를 사용하지 않는 방법보다 더 나은 해를 찾는데 도움이 되는 것을 보여준다.