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


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


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.

  • 0 Citations



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