Til hovedinnhold

Adaptive Large Neighborhood Search on the Graphics Processing Unit

Adaptive Large Neighborhood Search on the Graphics Processing Unit

Kategori
Konferansebidrag og faglig presentasjon
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 / 227071
  • Norges forskningsråd / 246825
Språk
Engelsk
Forfatter(e)
Institusjon(er)
  • SINTEF Digital / Mathematics and Cybernetics
Presentert på
Seminar
Sted
Salerno
Dato
23.10.2016 - 23.10.2016
Arrangør
Università degli Studi di Salerno
År
2016