Hub Location and the p-Hub Median Problem

Hub facilities serve as switching and transshipment points in transportation and communication networks. Hub networks concentrate flows on the hub-to-hub links and benefit from economies of scale in interhub transportation. Most hub location research has focused on problems where each origin/destination is allocated to a single hub. However, multiple allocation to more than one hub is necessary to minimize total transportation costs. This paper defines a p-hub median, analogous to a p-median, and presents integer programming formulations for the multiple and single allocation p-hub median problems. Two new heuristics for the single allocation p-hub median problem are evaluated. These heuristics derive a solution to the single allocation p-hub median problem from the solution to the multiple allocation p-hub median problem. Computational results are presented for problems with 10–40 origins/destinations and up to eight hubs. The new heuristics generally perform well in comparison with other heuristics.