A GPU-Based Genetic Algorithm for the Multiple Allocation P-Hub Median Problem
- 1 Department of Computer Science, Euromed Research Center, Euromed University of Fes, Morocco
- 2 Department of Computer Science, LARI, Faculty of Sciences Oujda, Mohammed Premier University, Oujda, Morocco
- 3 Department of Mathematics, LMAH, Faculty of Sciences and Techniques, Normandie University, le Havre, France
Abstract
As the sizes of realistic hub location problems increase as time goes on (reaching thousands of nodes currently) this makes such problems difficult to solve in a reasonable time using conventional computers. This study aims to show that such problems may be solved in a short computing time and with high-quality solutions using the computational power of the GPU (actually available in most personal computers). So, we present a GPU-based approach for the uncapacitated multiple allocations p-hub median problems. Our method identifies the nodes that are likely to be hubs in the optimal solution and improves them via a parallel genetic algorithm. The obtained GPU implementation reached within seconds the optimal or the best solutions for all the known benchmarks we had access to and solved larger instances up to 6000 nodes so far unsolved. Compared to this study, no other article dealing with hub location problems has presented results for instances as large.
DOI: https://doi.org/10.3844/jcssp.2023.629.640
Copyright: © 2023 Achraf Berrajaa, Ayyoub El Outmani and Abdelhamid Benaini. This is an open access article distributed under the terms of the
Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 1,147 Views
- 507 Downloads
- 0 Citations
Download
Keywords
- Genetic Algorithm
- P-Hub Median Problem
- Multiple Allocations
- GPU