GRASP METAHEURISTIC APPLIED TO THE MAXIMUM COVERAGE p-HUB PROBLEM

This work presents an algorithm based on the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic for the uncapacitated single-allocation maximum-coverage p-hub problem. The objective of the problem is to determine the best location for p-hubs and the assignment of each non-hub node to a single hub, so that the total demand between pairs of nodes within a given coverage distance is maximized. Computational tests performed using instances from the literature show satisfactory results, with good-quality solutions and runtimes lower than those of the CPLEX solver. Furthermore, the results obtained were also compared with reference results from the literature, evidencing an average gap of 0.1\% to the objective function values and lower average CPU times in 100\% of the instances analyzed.