Research seminar
Abstract
Hub-and-spoke has been the predominant architecture for airline networks since the deregulation of US airline industry in 1978.
Rather than routing traffic/flow directly from their origins to their destinations, a hub-and-spoke network connects the origins and destinations through intermediate hubs. The consolidation of traffic volume at hubs allows airlines to benefit from the economies of scale in hub-to-hub transportation. Owing to its impact on the transportation/logistics industry, hub-and-spoke model has been cited as the seventh in the American Marketing Association series of “Great Ideas in the Decade of Marketing” (Marketing News, June 20, 1986). The optimal location of hubs in a hub-and-spoke network has attracted a lot of attention in Operations Research, starting with the seminal paper by O’Kelly (1987).
Hub Location Problem (HLP) is an NP-hard problem, combining features of both facility location and network flow/quadratic assignment. In this talk, we revisit the classic Single Allocation HLP to propose a very efficient method of solving it. We present its Benders reformulation, for which we provide a very efficient Branch-and-cut (B&C) based solution algorithm. We exploit the structure of the Benders reformulation to highlight that the Benders cuts in our B&C algorithm can be generated very efficiently by solving a number of balanced transportation problems, one for each origin-destination pair.
Further, we strengthen the Benders cuts to make them Pareto-optimal by very efficiently solving parametric transportation problems. Using several further refinements to our algorithm, like variable fixing, heuristic upper bound, etc., we are able to beat the current state-of the-art by orders of magnitude for several classes of Single Allocation HLP.
Registration by email to Jackie.brown@uni.lu