Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959987 | European Journal of Operational Research | 2017 | 43 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Marco Antonio Boschetti, Vittorio Maniezzo, Francesco Strappaveccia,