GRASP for the uncapacitated r-allocation p-hub median problem

In this paper we propose a heuristic for the Uncapacitated rr-Allocation pp-Hub Median Problem. In the classical pp-hub location problem, given a set of nodes with pairwise traffic demands, we must select pp of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the rr-  allocation pp-hub median problem, recently proposed by Yaman [19], in which every node is assigned to rr of the pp selected hubs (r≤pr≤p) and we are restricted to route the traffic of the nodes through their associated rr hubs.As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on the GRASP methodology in which we consider three local search procedures. The combinatorial nature of this problem makes them time-consuming. We therefore propose a filtering mechanism to discard low-quality constructions and skip its improvement, saving its associated running time. We perform several experiments to first determine the values of the key-search parameters of our method and then to compare with previous algorithms. Computational results on 465 instances show that while only small instances can be optimally solved with exact methods, the heuristic is able to find high-quality solutions on larger instances in short computing times. Moreover, when targeting the classical pp-hub versions (with r=1r=1 or r=pr=p), our heuristic is competitive with the state of the art methods.