Machine and deep learning models for vehicle routing problems: a literature review

Abstract

Vehicle routing problems (VRPs), a generalization of the traveling salesman problem, are extensively studied combinatorial optimization problems for their practical application. Many solution methods, e.g., exact and heuristic algorithms, have been proposed in the last few decades but require relatively much computation time due to the NP-hard nature of the VRP. Additionally, to build such algorithms, much expert knowledge is required. The recent developments in a subfield of machine learning, deep learning, make it possible to solve routing problems in a purely data-driven manner or assist heuristic methods. This requires less problem-specific knowledge and can outperform the traditional solution methods in terms of objective value and computation time. In this literature review, introductions for the vehicle routing problem and machine learning are given first. Then, an existing categorization for algorithmic machine learning structures is described. The main body of this report reviews recent machine and deep learning methods to solve static and dynamic routing problems. The reviewed literature is summarized in tables that indicate the main characteristics of each work. Moreover, the results of several machine and deep learning based solution methods for the static VRP are compared to each other. Lastly, the challenges and opportunities for future research of deep learning based solution methods for the vehicle routing problem are discussed. The main challenges of these methods are scalability, generalization, and adaptability. Therefore, future research could be focused on addressing these challenges to improve deep learning methods for practical routing applications.