A GPU-based genetic algorithm for the p-median problem |
| |
Authors: | Bader F. AlBdaiwi Hosam M. F. AboElFotoh |
| |
Affiliation: | 1.Computer Science Department,Kuwait University,Kuwait City,Kuwait |
| |
Abstract: | The p-median problem is a well-known NP-hard problem. Many heuristics have been proposed in the literature for this problem. In this paper, we exploit a GPGPU parallel computing platform to present a new genetic algorithm implemented in CUDA and based on a pseudo-Boolean formulation of the p-median problem. We have tested the effectiveness of our algorithm using a Tesla K40 (2880 CUDA cores) on 290 different benchmark instances obtained from OR-Library, discrete location problems benchmark library, and benchmarks introduced in recent publications. The algorithm succeeded in finding optimal solutions for all instances except for two OR-library instances, namely pmed 30 and pmed 40, where better than 99.9% approximations were obtained. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|