A GVNS algorithm applied to the uncapacitated single allocation hub maximal covering problem with fixed costs

This paper proposes the uncapacitated single allocation hub maximal covering problem with fixed costs (USAHMCP), focused on selecting the hubs to be opened and determining the allocation of each non-hub node to a single hub, assuming that the set of selected hubs is restricted by a budget for opening the hubs. Thus, the uncapacitated single allocation p-hub maximal covering problem (USApHMCP), aimed to open a predetermined number of hubs, is a particular case of this problem. This paper proposes a heuristic algorithm based on the General Variable Neighborhood Search (GVNS) metaheuristic, with two variants differing on the greedy allocations criterion. One variant, originally proposed in this paper, uses coverage potential-based allocation; the other variant uses a distance-based allocation strategy, the most used criterion in the literature. Computational experiments carried out using instances from the literature with up to 1000 nodes showed that, when the hub opening cost is higher for nodes with higher demands, USAHMCP tends to open more hubs than USApHMCP; for instances that do not make this distinction, the number of hubs tends to be the same, with possible differences in the set of opened hubs. The coverage potential-based allocation strategy found better solutions than the distance-based allocation strategy. Concerning USApHMCP, for instances with up to 200 nodes, the proposed heuristic obtained good solutions in better runtimes than the benchmarks and updated the best-known solutions for 1000-node URAND instances.