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.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:H.W. Hamacher, M. Labbé, S. Nickel, T. Sonneborn
URN (Permalink):urn:nbn:de:hbz:386-kluedo-12834
Schriftenreihe (Bandnummer):Berichte des Fraunhofer-Instituts für Techno- und Wirtschaftsmathematik (ITWM Report) (20)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2000
Jahr der Veröffentlichung:2000
Veröffentlichende Institution:Fraunhofer-Institut für Techno- und Wirtschaftsmathematik
Datum der Publikation (Server):02.02.2004
Freies Schlagwort / Tag:branch and cut; facets; facility location; hub location; integer programming; valid inequalities
Fachbereiche / Organisatorische Einheiten:Fraunhofer (ITWM)
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $