A further study of single allocation hub location problem

Resumen

We will talk about a new formulation for uncapacitated single allocation hub location problems. In the uncapacitated single allocation p-hub median problem (USApHMP), the aim is to choose p hubs and assign every site to them minimizing the overall transportation costs betweenorigins and destinations through the hubs. Alternatively, the uncapacitated single allocation hub location problem (USAHLP) considers a cost for setting a hub being the number of hubs a decision variable. In this case, the aim is to locate the hubs and to assign the remaining sites to the hubs minimizing the overall installation and transportation costs. O’Kelly (1987) [1] presented the first mathematical formulation for these problems. Since then, different linearization strategies have been used in the literature to handle the quadratic term in the objective function of this model.We introduce a new formulation to solve the USApHMP and the USAHLP with fewer variables than the previous Integer Linear Programming formulations known in the literature. Our formulation includes a general cost structure that does not require costs based on distances neithersatisfaction of the triangle inequality. This allows us to model more realistic cases in transportation systems where, for instance, fares are notproportional to travel distances or longer trips may have lower ticket prices than shorter trips. Moreover, some of the existing formulations forthe USApHMP need to have the overall transportation cost from origin to destination disaggregated in the three components: origin-hub, hub-hub,hub-destination. We develop formulations for both cases, with aggregated/disaggregated transportation costs. The formulation is strengthened by means of valid inequalities and different families of cuts are developed and added through effective separation procedures. A comparison of the performance of the most efficient solution methods existing in the literature ([2], [3] and [4]), shows the efficiency of our methodology, solving large-scale instances in competitive times.