개선된 네트워크 임베딩과 심층 강화 학습을 이용한 유한 시간 내 차량 경로 탐색

Vehicle Routing with Finite Time Horizon using Deep Reinforcement Learning with Improved Network Embedding

본 논문에서는 유한 시간 호라이즌(finite time horizon)을 고려한 차량 경로 문제를 연구한다. 이 경로 문제의 목표는 유한한 시간 내에 서비스되는 고객 요청의 수를 최대화하는 것이다. 우리는 지역 노드 임베딩 벡터와 문맥을 인식하는 전역 그래프 표현을 생성하는 새로운 경로 네트워크 임베딩 모듈을 제안한다. 제안된 차량 경로 문제를 위한 마르코프 결정 과정은 노드 특징, 네트워크 인접 행렬, 그리고 엣지 특징을 상태 공간의 구성 요소로 포함한다. 우리는 임베딩 모듈에 적절한 경로 탐색 문맥을 제공하기 위해 남은 시간을 네트워크 임베딩 모듈에 통합한다. 유한 시간 호라이즌 차량 경로 문제를 해결하기 위해, 우리는 이 임베딩 모듈을 정책 경사(policy gradient) 기반의 심층 강화 학습 프레임워크와 통합한다. 우리는 실제 도로 네트워크와 인공적으로 생성된 유클리드 네트워크에서 제안된 경로 탐색 방법을 훈련하고 검증했다. 실험 결과에 따르면, 제안된 방법은 기존 경로 탐색 방법보다 더 높은 고객 서비스 비율을 달성하는 것으로 나타났다. 또한, 제안된 방법의 해 탐색 시간은 기존 방법들보다 현저히 짧다.

In this paper, we study the vehicle routing problem with a finite time horizon. In this routing problem, the objective is to maximize the number of customer requests served within a finite time horizon. We present a novel routing network embedding module which creates local node embedding vectors and a context-aware global graph representation. The proposed Markov decision process for the vehicle routing problem incorporates the node features, the network adjacency matrix and the edge features as components of the state space. We incorporate the remaining finite time horizon into the network embedding module to provide a proper routing context to the embedding module. We integrate our embedding module with a policy gradient-based deep Reinforcement Learning framework to solve the vehicle routing problem with finite time horizon. We trained and validated our proposed routing method on real-world routing networks, as well as synthetically generated Euclidean networks. Our experimental results show that our method achieves a higher customer service rate than the existing routing methods. Additionally, the solution time of our method is significantly lower than that of the existing methods.