GPU computing for the capacitated single allocation hub location problem

Several real-life problems show the necessity for solving large scale hub location problem in reasonable time. Since these problems are classified as NP-hard, the aim of this paper is to design a GPU based approach for the capacitated variant of the HLP that can approach these goals. The proposed GA starts from several initial populations (island model) carefully generated in order to speed up the convergence of the GA. The numerical tests on a variety of known benchmarks and on a random large instances (up to 6000 nodes) reveal the importance of the choice of initial populations and the way they interact with each other. They show that the proposed methodology is efficient at least for these benchmarks and may be adapted to other variants of hub location problems. The method has reached all the known optimal solutions for these benchmarks and found new, significantly better, solutions on three AP instances with 100 and 200 nodes.