Til hovedinnhold

Adaptive Large Neighborhood Search on the Graphics Processing Unit

Adaptive Large Neighborhood Search on the Graphics Processing Unit

Kategori
Tidsskriftspublikasjon
Sammendrag
For computationally hard discrete optimization problems, we rely on increasing computing power to reduce the solution time. In recent years the computational capacity of the Graphics Processing Unit (GPU) in ordinary desktop computers has increased significantly compared to the Central Processing Unit (CPU). It is interesting to explore how this alternative source of computing power can be utilized. Most investigations of GPU-based methods in discrete optimization use swarm intelligence or evolutionary methods. One of the best single-solution metaheuristics for discrete optimization is Adaptive Large Neighborhood Search (ALNS). GPU parallelization of ALNS has not been reported in the literature. We gain knowledge on the difficulties of developing a data parallel version of the ALNS, and investigate the efficiency of ALNS on the GPU. To this end, we develop an ALNS for the much studied Distance Constrained Capacitated Vehicle Routing Problem (DCVRP). We compare the performance of our GPU-based ALNS with a state-of-the-art CPU implementation using standard DCVRP benchmarks. While it proved hard to implement certain commonly used mechanisms efficiently on the GPU, experimental results show that our GPU-based ALNS yields highly competitive performance.
Oppdragsgiver
  • Norges forskningsråd / 263031
  • Norges forskningsråd / 246825
  • Norges forskningsråd / 227071
  • Norges forskningsråd / 192905
Språk
Engelsk
Institusjon(er)
  • SINTEF Digital / Mathematics and Cybernetics
År
2018
Publisert i
European Journal of Operational Research
ISSN
0377-2217
Årgang
275
Hefte nr.
1
Side(r)
53 - 66