| 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.
|