Cristin-resultat-ID: 1043044
Sist endret: 20. mars 2014 15:48
Resultat
Vitenskapelig foredrag
2013

Solving Routing Problems with the GPU

Bidragsytere:
  • Geir Hasle
  • Torkel Andreas Haufmann og
  • Christian Ferdinand Schulz

Presentasjon

Navn på arrangementet: Second Annual Conference of the EURO Working Group on Vehicle Routing and Logistics Optimization (VeRoLog2013)
Sted: Southampton
Dato fra: 7. juli 2013
Dato til: 10. juli 2013

Arrangør:

Arrangørnavn: University of Southampton

Om resultatet

Vitenskapelig foredrag
Publiseringsår: 2013

Beskrivelse Beskrivelse

Tittel

Solving Routing Problems with the GPU

Sammendrag

Due to physical limits, hardware development no longer results in higher speed for sequential algorithms, but rather in increased parallelism. Modern commodity PCs include a multi-core CPU and at least one GPU, providing a low cost, easily accessible heterogeneous environment for high performance computing. New solution methods that combine task parallelization and stream processing and self-adapt to the hardware at hand are needed to fully exploit modern computer architectures and profit from future hardware developments. In this talk, we give an introduction to modern PC architectures and the GPU, and survey the literature on GPU-based solution methods in discrete optimization that currently consists of some 100 papers. Many of them describe GPU implementations of well-known metaheuristics and report impressive speedups relative to a sequential version. As for applications and problems studied, 26 papers describe research on routing problems of which 9 focus on the Shortest Path Problem, 15 discuss the Travelling Salesman Problem, and only 2 study the Vehicle Routing Problem. Finally, we describe a GPU-based Travelling Salesman Problem solver and present numerical results for large-scale instances.

Bidragsytere

Geir Hasle

  • Tilknyttet:
    Forfatter
    ved Mathematics and Cybernetics ved SINTEF AS

Torkel Andreas Haufmann

  • Tilknyttet:
    Forfatter
    ved Det matematisk-naturvitenskapelige fakultet ved Universitetet i Oslo

Christian Ferdinand Schulz

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