New formulations for the uncapacitated multiple allocation hub location problem

New formulations for the uncapacitated multiple allocation hub location problem

0.00 Avg rating0 Votes
Article ID: iaor20083615
Country: Netherlands
Volume: 172
Issue: 1
Start Page Number: 274
End Page Number: 292
Publication Date: Jul 2006
Journal: European Journal of Operational Research
Authors: , ,
Keywords: graphs, programming: integer
Abstract:

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 need 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 preprocessing 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.

Reviews

Required fields are marked *. Your email address will not be published.