The Classical p-median Problem as a Surrogate Model in Hub Location

This paper examines the use of the classical p-median problem as a surrogate (or approximate) model in hub location. The models presented here are derived from two extreme situations: (i) the hub network is super-efficient so that cost coefficient $$\alpha$$ α for hub to hub transfer tends to be close to 0; and (ii) the reverse where the hub sub-network is highly inefficient, so that $$\alpha$$ α tends to be unusually high. The performance of these approximate models is assessed on a group of test instances using different allocation strategies (single and multiple), uniform and non-uniform flows between nodes, and different values of $$\alpha$$ α . The group contains relatively small instances in order to allow optimal hub locations to be found most of the time by a general purpose MILP solver. A second group of larger instances is also tested, but in this case we use a state-of-the-art heuristic based on variable neighborhood search to find high quality solutions to one of the hub median problems under investigation. The obtained results confirm that the presented models are viable alternatives for finding good (sometimes even optimal) solutions to p-hub median problems. In some cases, where the MILP solver does not find an optimal solution for the given hub problem within the specified time-limit, better solutions are obtained with the basic p-median model in a small fraction of the time. We also introduce new cuts that can be added to the MILP formulations of p-hub median problems. These cuts take advantage of the observed ’proximity’ of the p-median nodes to the optimal hub nodes, and should be highly effective in finding optimal solutions or tight upper bounds. The effectiveness of the p-median solution as a starting solution in heuristics is also demonstrated.