Solving various vehicle routing problem using deep learning

Abstract

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.