The hub & spoke network design problem is a strategic logistics planning problem with applications for airlines, telecommunication companies, computer networks, postal services, and trucking companies, for example. Basically, the problem in all these applications is that for a given set
= 1,... ,
of nodes (airports, computers, post offices, depots, ...) goods must be transported between possibly every pair of nodes. Direct connections between every pair of nodes would result in
− 1) linkages which is impractically high and economically non-profitable. Consider, for instance, an airline that serves several airports worldwide. Offering nonstop flights between every pair of airports would require a huge amount of planes and crews and many empty seats on board could be observed for many connections. In such settings, it turns out to be reasonable to install one or more so-called hub locations where direct links are then available to hub nodes as indicated in figure 1 where nodes 3, 6, and 9 are assumed to be hubs. Transporting goods from, say, node 1 to node 11, can then be done via hubs 3 and 6.