The p-hub problem is a facility location problem that can be viewed as a type of network design problem. Each node, within a given set of nodes, sends and receives some type of traffic to and from the other nodes. The hub locations must be chosen from among these nodes to act as switching points for the traffic. Network links are placed between pairs of hubs so that the hubs are fully interconnected; each of the remaining nodes, in turn, is connected to one of the hubs. The traffic may represent telecommunications traffic, data transmissions, airline passengers, express packages, etc. This paper examines various heuristics for the p-hub location problem. It describes exchange heuristics that work with an incumbent set of hubs and systematically substitute other nodes for the incumbents based on local improvement measures. The paper compares these with clustering heuristics and enumeration heuristics based on previous work in the literature. Computational comparisons are reported.
