Competitive hub location problems: model and solution approaches

Abstract

In this paper, we study the hub location problem of an entrant airline that tries to maximize its market share, in a market with already existing competing players. The routes open for use can be either of multiple allocation or single allocation type. The entrant’s problem is modelled as a non-linear integer program in both the situations, which is intractable for off-the-shelf commercial solvers, like CPLEX and Gurobi, etc. Hence, we propose four alternate approaches to solve the problem. The first is based on a mixed integer second order conic program reformulation, while the second uses lifted polymatroid cuts based approximation of second order cone constraints. The third is the second order conic program within Lagrangian relaxation, while the fourth uses approximated lifted polymatroid cuts within lagrangian relaxation. The four methods performs differently for the single allocation and multiple allocation models, and second approach is the best for single allocation model and for smaller instances in multiple allocation model. As the problem size in multiple allocation model increases, the third method starts to be the better performer in terms of computation time.