To main content

Adaptive Large Neighborhood Search on the Graphics Processing Unit

Abstract

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.
Read publication

Category

Academic article

Client

  • Research Council of Norway (RCN) / 227071
  • Research Council of Norway (RCN) / 192905
  • Research Council of Norway (RCN) / 263031
  • Research Council of Norway (RCN) / 246825

Language

English

Author(s)

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics

Year

2018

Published in

European Journal of Operational Research

ISSN

0377-2217

Publisher

Elsevier

Volume

275

Issue

1

Page(s)

53 - 66

View this publication at Cristin