FASTER MIXED-INTEGER QUADRATIC CONIC PROGRAMS FOR TWO COMPETITIVE MULTIPLE ALLOCATION P-HUB LOCATION PROBLEMS

ABSTRACT We present new mixed-integer quadratic conic formulations for two variants of the multiple-allocation p-hub location problems in a competitive environment. The problems consist in locating p hubs so that an entrant company can establish its hub-and-spoke network to provide transportation services for pairs of origin-destination that exchange flows in a competitive market. The objective is to maximize the entrant’s market share when compared to its competitors. Both problems assume that the paths used to route the flows have one or at most two hubs. However, whereas the first problem allows an origin-destination to be serviced by multiple routes, the second problem requires that a single path be used. Here, we show that instead of maximizing the entrant’s market share, it is computationally more interesting to minimize the market lost so that equivalent, but more suitable programs to conic solvers can be obtained. When solved by a commercial conic programming solver, our proposed formulations achieve average speedups of 89 times for the multi-path variant and 37 times for the single-path variant, as shown in our extensive computational experiments on solving well-known datasets. Therefore, this work not only reformulates the problem but also substantially outperforms all prior works, demonstrating the practical applicability and effectiveness of our approaches.