Uncapacitated Euclidean hub location: strengthened formulation, new facets and a relax-and-cut algorithm

The multiple allocation uncapacitated hub location problem is considered. This problem arises in transportation systems when several locations send and receive passengers and/or express packages and the performance of these systems can be improved by using transshipment points (hubs), where the passengers/packages are collected and distributed. An Integer Programming formulation, the one giving the best computational results until now, serves as a basis for the solution method. Using the fact that the transportation costs between hubs satisfy the triangle inequality, an analysis of the set of solutions that are not candidates to be optimal is carried out and, as a consequence, the formulation of the problem can be strengthened by means of powerful valid inequalities obtained through the study of the intersection graph of an associated set packing problem. The algorithm developed uses the most promising of these inequalities in a Lagrangian relaxation context to reduce the size of the branching tree and improve the computational times. This improvement is shown by means of a computational study, where a set of instances are optimally solved with low computational effort.