HUBBI: Iterative network design for incomplete hub location problems

In this paper, we design and implement HUBBI, a heuristic-based method to minimize the transportation/setup costs for p-hub location problems with incomplete hub networks. First, HUBBI pre-computes an estimation of node pair quality for establishing hub links. The quality ranking over all node pairs is then used to guide an iterative network design process: Given a solution for p hubs, two generic design patterns extend the hub network to p+1 hubs. These networks are further refined by a variable neighborhood search method. In our evaluation on standard datasets (CAB, AP, TR, USA423 and URAND), HUBBI solves incomplete hub location problems with up to 200 nodes. For those instances that are solved with an exact method, HUBBI solves 90% to optimality and only one instance has a gap larger than 1%. HUBBI is also two to three orders of magnitudes faster than the exact method, while using two orders of magnitude less memory.