Parallel Local search for the CVRP on the GPU

For many applications of optimized transportation management, there is still a large gap between the requirements and the performance of today’s decision support systems. Vehicle routing is no exception. Although there has been a tremendous increase in the ability to solve ever more complex VRPs (partly due to methodological improvements, partly due to the general increase in computing power), the ability to consistently provide better routing plans in shorter time across a variety of instances will give substantial additional savings. With VRP methods that are more powerful and robust, applications that are too large or too complex for routing tools today, will become effectively solvable. For solving a variety of industrial VRPs, some form of approximate solution method is required in a generic vehicle routing tool. Metaheuristics constitute a popular basis for solving rich and large-size VRPs. Variants and hybrids of Large Neighborhood Search, Variable Neighborhood Search, and Iterated Local Search methods have proven remarkable performance lately. Heuristics based on exact methods such as column generation, and hybrid methods, for instance combining exact methods and local search, have recently proven to be highly effective in solving complex VRPs.Parallel computing is one way of improving both performance and robustness of VRP methods. Parallelism nowadays comes in many guises, ranging from low level parallelism to coarse-grained cooperative parallel solvers. We distinguish between task parallelism and data parallelism. Parallel methods in discrete optimization are not new. According to the recent survey of Crainic however, the literature on parallel methods for the VRP is scarce before the year 2000. The survey has 80 references that almost exclusively focus on task parallelization for the VRP. The optimization methods that are utilized by vehicle routing tools of today are tailored to yesterday’s computer architectures and sequential processing. Standard (comm