A tabu search heuristic for the uncapacitated single allocation p-hub maximal covering problem

This paper describes a tabu search (TS) heuristic for the uncapacitated single allocation p-hub maximal covering problem. The objective is to determine the best location for p hubs and the assignment of each of the spokes to a single hub such that the total demand between pairs of nodes within a given coverage distance is maximized. We consider all nodes as possible candidates for establishing hub facilities, what increases the complexity of the problem. Based on the mathematical programming formulation proposed by Peker and Kara (2015) we also report, for the first time, the optimal solutions for instances with up to 50 nodes from the AP (Australian Post) benchmark dataset, as well as the complete set of results for the CAB (Civil Aeronautics Board) dataset, including some heretofore yet unpublished results. The computational experiments have also demonstrated that our TS heuristic is efficient, leading to improved solutions in shorter CPU times when compared to previously published results, as well as for new derived instances with tigher coverage. It was also able to solve, for the first time, all instances of the AP data set, with up to 200 nodes, as well as new instances with tighter coverage parameters, thus evidencing it capacity to solve effectively large, realistic-sized instances of the problem.