Adaptive Large Neighborhood Search on the Graphics Processing Unit

Lukas Bach, Geir Hasle and Christian Schulz

European Journal of Operational Research, 2019, vol. 275, issue 1, 53-66

Abstract: 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.

Keywords: Metaheuristics; ALNS; Discrete optimization; VRP; GPU-programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718309767
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:275:y:2019:i:1:p:53-66

DOI: 10.1016/j.ejor.2018.11.035

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().