New formulations for the uncapacitated multiple allocation hub location problem

In this paper we review the integer linear formulations of the uncapacitated multiple allocation hub location problem, we study the scope of validity of these formulations and give new ones that generalize the older formulations. Our formulations allow one or two visits to hubs and include a more general cost structure that needs not satisfy the triangle inequality. We prove that the constraints defined by cliques of a related (intersection) graph are tighter constraints than the classical ones. We also discuss a pre-processing of the problem, which is very useful for reducing its size. Finally, we check the strength of the new formulations and compare them with others in the literature by solving instances of two commonly used data sets: the CAB (Civil Aeronautics Board) and AP (Australian Post), and also randomly generated instances. Our computational results clearly show that our formulations outperform all others previously used for small and medium problems. (C) 2004 Elsevier B.V. All rights reserved.