A Lagrangean heuristic and GRASP for the hub-and-spoke network design with economies of scale and congestion

Abstract

In the current fiercely competition environment, cost and time efficient distribution strategies provide companies with a competitive advantage. In a distribution network, direct shipments are neither cheap nor practical between each origin and destination pair. The cost efficiency of these networks can be improved by inserting hub points (switching/sorting centers) onto the link connecting origins and destinations and reducing direct links concentrates overall flow between fully interconnected hub points, thus creating economies of scale. The hub-and-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 of nodes (airports, computers, depots, etc.), goods must be transported between possibly each pair of nodes. Direct connections between every origin-destination of nodes would result in n ∗ (n − 1) connections which is impractically high and economically non-profitable. Consider, for instance, an airline company that serves several airports worldwide. Offering nonstop flights between every pair of airports would require a huge amount of planes and crews and would result in empty seats on board for many flights. This thesis offers deeper investigation into the hub-and-spoke design network for the airline industry; and it considers a hub-and-spoke network design problem with a concave cost function representing the economies of scale on the interhub links and a convex function representing congestion at hubs in the objective function of the model. The problem is modeled as a nonlinear mixed integer program that is difficult to solve directly. A Lagrangean approach is proposed to obtain tight upper and lower bounds. Computational experiments are reported for the Civil Aeronautics Board(CAB) dataset with a number of nodes –up to 25– that are solved efficiently by the Lagrangean heuristic. The solution methodology provides a high quality solution for the reported instances with reasonable time for all the tested instances. Moreover, a Greedy Randomized Adaptive Search Procedure(GRASP) is developed to solve large instances of the developed mathematical model which proved to provide high quality solutions when compared to the Lagrangean heuristic.

Date of Award	2014
Original language	American English
Supervisor	Ali Diabat (Supervisor)