Selecting between evolutionary and classical algorithms for the CVRP using machine learning: Optimization of vehicle routing problems

Solutions for NP-hard problems are often obtained using heuristics that yield results relatively quickly, at some cost to the objective. Many different heuristics are usually available for the same problem type, and the solution quality of a heuristic may depend on characteristics of the instance being solved. This paper explores the use of machine learning to predict the best heuristic for solving Capacitated Vehicle Routing Problems (CVRPs). A set of 23 features related to the CVRP were identified from the literature. A large set of CVRP instances were generated across the feature space, and solved using four heuristics including a genetic algorithm and a novel self-organizing map. A neural network was trained to predict the best performing heuristic for a given problem instance. The model correctly selected the best heuristic for 79% of the CVRP test instances, while the single best heuristic was dominant for only 50% of the test instances