Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem

Michal Karpinski, Maciej Pacut
Institute of Computer Science, University of Wroclaw, Joliot-Curie 15, 50-383 Wroc law, Poland
arXiv:1401.5216 [cs.DC], (21 Jan 2014)


   author={Karpi{‘n}ski}, M. and {Pacut}, M.},

   title={"{Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem}"},

   journal={ArXiv e-prints},




   keywords={Computer Science – Distributed, Parallel, and Cluster Computing, Computer Science – Neural and Evolutionary Computing},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



The goal of this paper is to propose and test a new memetic algorithm for the capacitated vehicle routing problem in parallel computing environment. In this paper we consider simple variation of vehicle routing problem in which the only parameter is the capacity of the vehicle and each client only needs one package. We present simple reduction to prove the existence of polynomial-time algorithm for capacity 2. We analyze the efficiency of the algorithm using hierarchical Parallel Random Access Machine (PRAM) model and run experiments with code written in CUDA (for capacities larger than 2).
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: