Cristin-resultat-ID: 1646027
Sist endret: 30. april 2019 14:31
NVI-rapporteringsår: 2018
Resultat
Vitenskapelig artikkel
2018

Adaptive Large Neighborhood Search on the Graphics Processing Unit

Bidragsytere:
  • Lukas Bach
  • Geir Hasle og
  • Christian Ferdinand Schulz

Tidsskrift

European Journal of Operational Research
ISSN 0377-2217
e-ISSN 1872-6860
NVI-nivå 2

Om resultatet

Vitenskapelig artikkel
Publiseringsår: 2018
Publisert online: 2018
Trykket: 2019
Volum: 275
Hefte: 1
Sider: 53 - 66
Open Access

Importkilder

Scopus-ID: 2-s2.0-85057518346

Beskrivelse Beskrivelse

Tittel

Adaptive Large Neighborhood Search on the Graphics Processing Unit

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.

Bidragsytere

Lukas Bach

  • Tilknyttet:
    Forfatter
    ved Mathematics and Cybernetics ved SINTEF AS

Geir Hasle

  • Tilknyttet:
    Forfatter
    ved Mathematics and Cybernetics ved SINTEF AS

Christian Ferdinand Schulz

  • Tilknyttet:
    Forfatter
    ved Mathematics and Cybernetics ved SINTEF AS
1 - 3 av 3