Research Article Open Access

A GPU-Based Genetic Algorithm for the Multiple Allocation P-Hub Median Problem

Achraf Berrajaa1, Ayyoub El Outmani2 and Abdelhamid Benaini3
  • 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.

Journal of Computer Science
Volume 19 No. 5, 2023, 629-640

DOI: https://doi.org/10.3844/jcssp.2023.629.640

Submitted On: 20 August 2022 Published On: 28 April 2023

How to Cite: Berrajaa, A., Outmani, A. E. & Benaini, A. (2023). A GPU-Based Genetic Algorithm for the Multiple Allocation P-Hub Median Problem. Journal of Computer Science, 19(5), 629-640. https://doi.org/10.3844/jcssp.2023.629.640

  • 1,257 Views
  • 552 Downloads
  • 0 Citations

Download

Keywords

  • Genetic Algorithm
  • P-Hub Median Problem
  • Multiple Allocations
  • GPU