Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem
This work addresses a specific optimization problem in logistics, but it is incremental as it builds on existing memetic and parallel computing methods.
The paper tackles the capacitated vehicle routing problem by proposing a new memetic algorithm for parallel computing, achieving a polynomial-time solution for capacity 2 and testing efficiency with CUDA for larger capacities.
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).