Route relaxations on GPU for vehicle routing problems

State-Space Relaxation (SSR) is an approach often used to compute by dynamic programming (DP) effective bounds for many combinatorial optimization problems. Currently, the most effective exact approaches for solving many Vehicle Routing Problems (VRPs) are DP algorithms making use of SSR for computing their bounding components. In particular, most of these make use of the q-route and ng-route relaxations. The bounding procedures based on these relaxations provide good quality bounds but they are often time consuming to compute, even for moderate size instances. In this paper we investigate the use of GPU computing for solving q-route and ng-route relaxations. The results prove that the proposed GPU implementations are able to achieve remarkable computing time reductions, up to 40 times with respect to the sequential versions.