Avoiding Local Optima in the p-Hub Location Problem Using Tabu Search and GRASP

Situations exist in which various locations (nodes) interact with each other by sending and receiving traffic. This could represent telecommunications traffic, data transmissions, airline passengers, express packages, etc. One possible strategy to link these locations or nodes, via a communications or transportation network, requires a certain number p of the locations to be hubs. These hubs are fully interconnected with network links. The remaining locations are each in turn connected ('assigned') to one of the hubs. The hub is said to 'serve' those nonhub locations assigned to it. Traffic can then be sent between any pair of locations by using the hubs as intermediate switching points.