Cristin-resultat-ID: 1248280
Sist endret: 1. september 2015, 11:03
Resultat
Vitenskapelig foredrag
2015

Adaptive Large Neighborhood Search using the Graphics Processing Unit

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

Presentasjon

Navn på arrangementet: Network Optimization Workshop (NOW) 2015
Sted: La Rochelle
Dato fra: 17. mai 2015
Dato til: 20. mai 2015

Arrangør:

Arrangørnavn: CIRRELT

Om resultatet

Vitenskapelig foredrag
Publiseringsår: 2015

Beskrivelse Beskrivelse

Tittel

Adaptive Large Neighborhood Search using the Graphics Processing Unit

Sammendrag

We investigate the efficiency of Adaptive Large Neighborhood Search (ALNS) on the Graphics Processing Unit (GPU). We do this by implementing an ALNS algorithm for the Distance-constrained Capacitated Vehicle Routing Problem (DCVRP) on a GPU. We benchmark towards a state of the art sequential implementation of an ALNS algorithm by Pisinger and Ropke [1]. In recent years the computational capacity of the GPU in ordinary desktop computers has increased significantly compared to the Central Processing Unit (CPU) normally used for computations. Hence, we find it interesting to investigate how this additional processing power is best utilized. A survey of GPU computing for routing problems can be found in Schulz, Hasle, Brodtkorb, and Hagen [2]. They find that most routing related GPU implementations use swarm intelligence, evolutionary, or local search based algorithms. To the best of our knowledge, there are no papers on ALNS implementations on a GPU. ALNS consists of a neighborhood search where destroy operators remove parts of an existing solution and repair operators that reinsert them. There are multiple destroy and repair operators and these are selected probabilistically based on their merit. A new solution is accepted according to an overall metaheuristic. Our ALNS algorithm for the GPU is implemented using NVIDIAs CUDA C/C++ programming language. Compared to the CPU based implementation from Pisinger and Ropke [1], it is necessary to adapt some of the operators to achieve a good utilization of the GPU. In these cases we implement a GPU version of the operator mimicking the behavior of the CPU version. Experiments are performed on an Intel Core i7-4770K with 3.5 GHz and an NVIDIA GeForce GTX TITAN. We perform tests on three sets of instances of the DCVRP: the Christofides, Mingozzi, and Toth instances, the Kelly instances, and the Li, Golden, and Wasil instances. In total this yields a set of 46 instances with the number of customers ranging from 50 to 1200. Our experiments show that, on average, our GPU implementation is close to the performance of the Pisinger and Ropke algorithm in terms of quality, but with less runtime. References [1] David Pisinger, and Stefan Ropke, A general heuristic for vehicle routing problems, Computers& Operations Research 34, 2403-2435 (2007) [2] Christian Schulz, Geir Hasle, Andre R. Brodtkorb, and Trond R. Hagen, GPU computing in discrete optimization. Part II: Survey focused on routing problems, EURO Journal on Transportation and Logistics 2, 159-186 (2013)

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