Competitive hub location problem: Model and solution approaches

In this paper, we study the hub location problem of an airline that wants to set up its hub and spoke network, in order to maximize its market share in a competitive market. The market share is maximized under the assumption that customers choose amongst competing airlines on the basis of utility provided by the respective airlines. We provide model formulations for the airline’s problem for two alternate network settings: one in the multiple allocation setting and another in the single allocation setting. Both these formulations are non-linear integer programs, which are intractable for most of the off-the-shelf commercial solvers. We propose two alternate approaches for each of the formulations to solve them optimally. The first among them is based on a mixed integer second order conic program reformulation, and the second uses Kelley’s cutting plane method within Lagrangian relaxation. On the basis of extensive numerical tests on well-known data-sets (CAB and AP), we conclude that the Kelley’s cutting plane within Lagrangian relaxation is computationally the best for both the single and multiple allocation settings, especially for large instances. We are able to solve instances upto 50 nodes from AP data-set within 120 and 10 minutes of CPU time for single and multiple allocation settings, respectively, which were unsolved by mixed integer second order cone based reformulation or Kelley’s cutting plane algorithm in the maximum allowed CPU time (3 hours for single allocation and 1 hour for multiple allocation).