| Despite the popularity of the hub-spoke networks, no systematic mathematical analysis has been conducted in order to (i) justify and evaluate the current hub-spoke systems; (ii) provide an optimal network structure; and (iii) suggest alternative routing policies. The purpose of this dissertation is to shed some light on these questions.; The network design problems are investigated considering one airline only. Based on the fixed demand assumption and some other simplifications, three basic integer linear programming models are formulated. Each model specifically deals with one of the following situations, depending on how the airline operates: (1) the all-stop service policy, where demand flow is routed through as many intermediate stops as necessary to reduce the transportation cost; (2) the one-stop service policy, where demand flow is restricted only to paths with at most one intermediate stop, and (3) the two-stop service policy, where paths up to two intermediate stops are permitted. Under each of the three policies, we further extend the design problems with the considerations of one-fleet and two-fleet options.; Solution procedures with several known techniques are examined. Benders decomposition is discussed in great length as a main approach. Through the investigation of the Benders cuts, we are able to develop some valid inequalities to enhance the procedure. Further, based on the structure analysis of the subproblems, we are able to design an efficient algorithm as a Benders variant to solve the problems of small size. Finally, due to the NP-hardness of the problems, heuristic approaches are applied to tackle problems of large size. As a result, a polynomial algorithm is designed for problem under each combination of different policies and options.; Computational evidences are collected from six testing problems consisting of 39 real U.S. cities. According to the characteristics of the resulting network structure, we conclude that the hub-spoke is cost-effective. In regards to the three stop policies, we conclude that the all-stop policy would be the most efficient design if any competition can be ignored. Otherwise the one-stop policy is highly recommended. Overall, by taking into account the fleet option and other operational costs, we show that the combination of a one-stop policy with a one-fleet option would be the most desirable design in real-life practice. |
