Vehicle routing problems (VRPs) are well-known NP-hard problems. Although mathematical formulations for VRPs are intuitive and straightforward, it requires a lot of computational resources to be solved. There have been twofold approaches to address contexts of VRPs: 1) Exact solution approaches and 2) Heuristic approaches. Recently, there has been much interest in applying machine learning-based solver as heuristic-based approaches.
In this dissertation, we consider the system of capacitated vehicles. That is, the system consists of multiple vehicles and infrastructures for any vehicle operations, such as multiple depots and replenishing stations. Because vehicles in the real world have limited capacities, which have critical effects on the system's performance, therefore, the system's purpose can be achieved by wise strategies for vehicle moves and deployment of the infrastructures. However, both vehicle moves and deployment of the infrastructures have a strong correlation, so that we solve both problems jointly.
Generally, in this dissertation, we develop a framework consisting of a simulation (environment) called Simulator, and a learning agent called Learner. We model the target problems mathematically in a manner of an MDP formulation to develop the Simulator for state-based decision making. We also develop the Learner based on DRL (Deep reinforcement learning) and implemented several DRL approaches and sub-algorithms for the robustness and the scalability of the learning process. At last, we avoid an instance learning where the learning process should be repeated in all different problem instances by acquiring transferability by transfer learning.
We propose several RL-based frameworks such as 1) DQN, 2) A2C with temporal abstraction, and 3) MARL with multiple GNNs to solve the mCVRP and system design problem. Target problems are CVRPs (Capacitated vehicle routing problems) and system design problems where CVRPs dictate the routing plans for the multiple capacitated vehicles, and system design problems determine the optimal deployment of the infrastructures in given target problems.
First, the DQN-based framework is studied to show both the robotic agents' movement and system design can be jointly solved in the context of reinforcement learning. However, the MDP model and the DQN-based \textit{Learner} can solve small size problems only due to the nature of the value-based RL and the single-agent RL. Second, we use the framework of A2C with temporal abstraction to achieve scalability. The temporal abstraction can split the whole network into a vehicle routing part and a system design part. As a result, both problems can be split mathematically, resulting in a hierarchical RL framework.
Based on the split framework, we concentrate on the vehicle routing problems only. We use an MARL (Multi-agent reinforcement learning) to efficiently address the vehicle routing problems. We also exploit multi-GNNs (multi-graph neural networks), representing a current state as embedding vectors, to achieve transferability and scalability. The framework of MARL with multi-GNN alleviates the curse of dimension by controlling each vehicle using an individual actor. Further, a trained GNN can extract latent factors for a current state, which is an achievement of generality for any state spaces.
차량 경로 문제 (VRP)는 잘 알려진 NP-난해 문제이다. 수학적 모델링은 간단하고 직관적이지만 조합 최적화 문제의 특성상 해를 구함에 있어 매우 큰 자원을 필요로 한다. 차량 경로 문제에 대한 두 가지 큰 접근법은 최적해를 구하거나, 휴리스틱 기반 solution을 구하는 것이다. 최근, 휴리스틱 기반 접근법으로서 기계 학습 기반의 solver 구현에 대한 연구가 활발히 진행되고 있다.
본 연구에서는 제한된 용량을 가지는 차량의 시스템을 고려한다. 하나의 시스템으로서, 다수의 차량과 차량 운용에 대한 기반 시설 (차량 창고 (depot) 또는 충전 스테이션) 을 다룬다. 실제로 모든 차량은 제한된 용량으로 인한 제약 조건이 시스템 성능에 결정적인 영향을 미치기 때문이다. 따라서, 차량 시스템의 목적 달성은 차량 이동과 기반 시설 배치에 의해 결정된다. 그러나 차량 이동과 기반 시설 배치는 강한 상관 관계를 가진다. 따라서 본 논문에서는 차량 이동 및 기반 시설 배치 문제를 동시에 고려한다.
이를 위해, 문제의 환경을 구현하는 \textit{Simulator}와 학습 에이전트인 \textit{Learner}로 이루어진 프레임워크를 구성하였다. \textit{Simulator}는 state 기반 의사 결정을 위한 MDP 모델링을 하였다. \textit{Learner}는 심층 강화 학습을 기반으로 구현하였고, 강건성과 확장성 확보를 위해 다양한 심층 강화 학습 방법론과 서브 알고리즘을 구현하였다. 최종적으로, 문제가 달라질 때마다 학습 프로세스를 새로이 진행하여야 하는 instance 기반 학습에서 탈피해, 전이가능성을 가지는 전이 학습 기반의 강화 학습을 활용하였다.
본 연구에서 우리는 1) DQN, 2) A2C with temporal abstraction, 3) 다중 GNN 기반 MARL과 같은 강화 학습 기반의 프레임워크를 제안하였다. 목표 문제는 크게 CVRP (제한 용량 차량 경로 문제) 와 시스템 디자인 문제로서, CVRP는 제한된 용량을 가지는 차량의 이동 경로를 결정하고, 시스템 디자인 문제는 주어진 상황에서 최적의 기반 시설 위치를 결정한다.
첫째, DQN 기반 프레임워크는 차량의 이동과 시스템 디자인 문제를 동시에 푸는 데 있어 강화 학습을 활용할 수 있음을 보여준다. 하지만 가치 기반 강화 학습 및 하나의 학습 네트워크로 구성되어 상대적으로 작은 사이즈의 문제만 풀 수 있다. 둘째, A2C with temporal abstraction을 활용해서 확장성을 확보한다. Temporal abstraction은 하나의 전체 네트워크를 차량 이동 부분과 시스템 디자인 부분으로 나눌 수 있다. 이를 통해, 시스템 디자인 문제와 차량 경로 문제는 수직적으로 분리되어 계층적 구조로서 학습이 가능함을 보여준다.
분리된 학습 구조를 기반으로, 제한 용량 차량 경로 문제에만 집중한다. 제한 용량 차량 경로 문제를 효율적으로 풀기 위해 다중 에이전트 강화 학습 (MARL)을 활용한다. 또한 전이가능성 및 확장성 확보를 위해 다중 GNN을 활용하여 상태 (state) 를 표현할 수 있다. MARL은 각 차량마다 actor를 컨트롤러로서 배치하여 curse of dimension을 완화한다. 그리고 GNN은 현재 상태에 대한 잠재 요소 추출을 통해 다양한 상태에 대한 일반성을 확보한다.
