| Hub-and-spoke topology is widely applied in a variety of industries, as it effectively exploits economies of scale. One major side effect that it causes is congestion. Congested hubs jeopardize the performance of the entire hub-and-spoke network and may lead to the paralysis of the whole system. Hence, it is important to incorporate congestion effects into the network design stage.;To solve the NMIP, we propose a Lagrangean heuristic where the model is decomposed into an easy subproblem and a more difficult nonlinear subproblem. The nonlinear subproblem is first lineared using piecewise functions and then solved using a cutting plane method. The Lagrangean lower bound is found using subgradient optimization. The solution from the subproblems are used to find a heuristic solution. The upper bound from the heuristic solution is compared to the Lagrangean lower bound.;Computational results indicate the efficiency of the methodology in providing a sharp bound and in generating feasible solutions that are 1% from the optimal in most cases. The feasible solutions reveal that incorporating congestion effects into the design stage is a valid and effective approach to prevent the congestion problem in hub-and-spoke systems.;This thesis presents an analytic model for a capacitated single assignment hub-and-spoke system design with congestion. A non-linear mixed integer program (NMIP) is developed. Congestion at hubs is modelled as a ratio of total flow to surplus capacity. This is a direct result of viewing the hub-and-spoke system as a network of M/M/1 queues. The objective is to minimize transportation costs, hub capacity fixed costs and hub congestion costs. |
