Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem
Institute of Computer Science, University of Wroclaw, Joliot-Curie 15, 50-383 Wroc law, Poland
arXiv:1401.5216 [cs.DC], (21 Jan 2014)
@article{2014arXiv1401.5216K,
author={Karpi{‘n}ski}, M. and {Pacut}, M.},
title={"{Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem}"},
journal={ArXiv e-prints},
archivePrefix={"arXiv"},
eprint={1401.5216},
primaryClass={"cs.DC"},
keywords={Computer Science – Distributed, Parallel, and Cluster Computing, Computer Science – Neural and Evolutionary Computing},
year={2014},
month={jan},
adsurl={http://adsabs.harvard.edu/abs/2014arXiv1401.5216K},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
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).
January 23, 2014 by hgpu
