Outer-approximation algorithms for a competitive multiple allocation p-hub location

We propose outer-approximation methods for multiple-allocation p-hub location problems in a competitive setting. An entrant must locate p hubs to design a hub-and-spoke network for origin-destination pairs, seeking to maximize market share against incumbents. Flows use paths with one or two hubs, and each origin-destination pair may use multiple routes. We reformulate the problem by minimizing market loss instead of maximizing market share, obtaining equivalent models better suited to conic solvers and outer-approximation. Our outer-approximation algorithms significantly outperform CPLEX’s conic solver in numerical experiments, demonstrating strong practical effectiveness.