This study address various vehicle routing problems and various methodologies to solve them. The vehicle routing problem is used in various fields such as OR, transportation, and artificial intelligence, and it is a research with high industrial value. VRP is composed of the depot, customer, and vehicle elements and are divided into various problems depending on the combination of each element. Since VRP is an NP-hard problem, the exact optimal solution can only be obtained for small-sized problems. So most of the problems are solved through the heuristic methodology. Heuristics are divided into improvement and construction heuristics, and neural networks can combine inside heuristics. This study considered UAV routing problems in a stochastic environment, min-max vehicle problems, and TSP with drone problems. The problem was formalized as MDP model and MILP model, and sub-MDP based heuristic, NCE, and iterative heuristic using GNN were developed to solve the problem. In addition, various experiments demonstrate the effectiveness of the algorithm.
본 연구에서는 다양한 차량 라우팅문제와 이를 해결하기 위한 여러가지 방법론을 다룬다. 차량 라우팅 문제는 OR, 교통, 인공지능등 여러 분야에서 쓰이고 있으며 산업적으로도 가치가 높은 연구이다. 차량 라우팅 문제는 디폿, 고객, 차량의 요소로 구성되며 각 요소 들의 조합에 따라 다양한 문제로 나누어 진다. 차량 라우팅 문제는 NP-hard문제이기 때문에 최적해는 사이즈가 작은 문제에서만 구할 수 있다. 그래서 대부분 휴리스틱 방법론을 통해 문제를 푼다. 휴리스틱은 개선 휴리스틱과 건설 휴리스틱으로 나누어지며 휴리스틱 내부에 인공 신경망이 결합이 되기도 한다. 본 연구에서는 확률적인 환경에서 UAV의 경로설정, min-max 차량문제,TSP with drone 문제를 풀었다. 문제를 MDP model, MILP model로 형식화 하였으며 문제를 풀기 위해 sub-MDP based heuristic, NCE, Iterative heuristic using GNN등을 개발하였다. 또한 다양한 실험을 통해 개발한 알고리즘의 효율성 입증하였다.
