Competitive multiple allocation p-hub location problems: models and exact algorithms

Abstract

This thesis addresses the competitive multi-path multi-allocation p-hub location problem (MPMAPHLP), motivated by applications in the airline industry, in which a new airline seeks to compete with an established company in a consolidated market. In this context, we consider passenger route choice, making strategic hub-and-spoke network planning a crucial factor for market capture. Two new mathematical formulations are proposed: the first reformulates the original maximization problem from the literature into an equivalent minimization model. The second reinforces the problem’s coupling constraints, achieving greater scalability. This work is the first to address this type of problem through market loss and to use stronger coupling constraints, favoring scalability. To solve mixed-integer non-linear problems, we first use equivalent conic formulations, followed by new exact algorithms based on the outer approximation technique. Furthermore, this work pioneers the combination of conic reformulation with outer approximation in this context. Through extensive computational experiments using Civil Aeronautics Board (CAB) data with up to 70 nodes, we demonstrate that our models substantially outperform all previous work. Using a commercial conic solver, our proposed formulations achieved remarkable computational gains compared to the literature model: the initial minimization model achieves average speedups of 113 times, and the second formulation reaches average speedups of 1081 times, both faster than the maximization model, establishing a new standard in efficiency for competitive MPMAPHLP solutions. Performance gains were obtained by employing algorithms based on external approximation, demonstrating the efficiency of the newly developed algorithms.