Polyhedral Properties of the Uncapacitated Multiple Allocation Hub Location Problem

  • We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet defining. We show its superior computational performance by benchmarking it on a well known data set.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Horst W. Hamacher, Martine Labbé, Stefan Nickel, Tim Sonneborn
URN:urn:nbn:de:hbz:386-kluedo-10718
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (67)
Document Type:Preprint
Language of publication:English
Year of Completion:2000
Year of first Publication:2000
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2000/08/29
Tag:branch and cut; facets; facility location; hub location; integer programming; valid inequalities
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011