To main content

Efficient Local Search on the GPU. Investigations on the Vehicle Routing Problem

Abstract

We investigate the performance increase potential of GPU implementations of local search. In particular, we report on how we managed to incrementally improve the implementation of a local search algorithm to a given GPU platform for maximum performance. As our target problem we use the well known Vehicle Routing Problem (VRP). The VRP is a family of computationally very hard problems with high industrial relevance. In particular, we investigate the 2-opt and 3-opt neighborhoods for the Distance constrained Capacitated VRP (DCVRP). Our final GPU implementation utilizes the GPU architecture efficiently. It is nearly one order of magnitude faster than the first implementation.

Oppdragsgiver: The Research Council of Norway

Category

Report

Client

  • SINTEF AS / 90A36301

Language

English

Author(s)

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics

Year

2011

Publisher

SINTEF

Issue

A19678

ISBN

9788214049848

View this publication at Cristin