Airline network design and hub location problems

Due to the popularity of hub-and-spoke networks in the airline and telecommunication industries, there has been a growing interest in hub location problems and related routing policies. This paper introduces flow-based models for designing capacitated networks and routing policies. No a priori hub-and-spoke structure is assumed. The resulting networks may suggest the presence of ‘‘hubs’’, if cost efficient. The network design problem is concerned with the operation of a single airline with a fixed share of the market. The authors present three basic integer linear programming models, each corresponding to a different service policy. Due to the difficulty of solving (even small) instances of these problems to optimality, they propose heuristic schemes based on mathematical programming. The procedure is applied and analyzed on several test problems consisting of up to 39 U.S. cities. The authors provide comments and partial recommendations on the use of hubs in the resulting network structures.