Polyhedral Analysis of Hub Center Problems

  • A hub location problem consists of locating p hubs in a network in order to collect and consolidate flow between node pairs. This thesis deals with the uncapacitated single allocation p-hub center problem (USApHCP) as a special type of hub location problem with min max objective function. Using the so-called radius formulation of the problem, the dimension of the polyhedron of USApHCP is derived. The formulation constraints are investigated to find out which of these define facets. Then, three new classes of facet-defining inequalities are derived. Finally, efficient procedures to separate facets in a branch-and-cut algorithm are proposed. The polyhedral analysis of USApHCP is based on a tight relation to the uncapacitated facility location problem (UFL). Hence, many results stated in this thesis also hold for UFL.
  • In einem Hub Location Problem werden p Knoten eines Logistik-Netzwerks als Hubs ausgewählt, die Flüsse zwischen anderen Knoten sammeln und konsolidieren. In dieser Arbeit wird das "uncapacitated single allocation p-hub center problem" (USApHCP) als Spezialfall des Hub Location Problems mit Min Max Zielfunktion behandelt. Für die so genannte Radius-Formulierung des Problems wird die Dimension des Polyeders von USApHCP ermittelt. Die Ungleichungen der Formulierungen werden danach untersucht, welche davon Facetten des Polyeders beschreiben. Anschließend werden drei neue Klassen von gültigen Ungleichungen vorgestellt, die Facetten definieren. Schließlich werden effiziente Vorgehensweisen zur Separierung der Facetten in einem Branch-und-Cut-Algorithmus vorgeschlagen. Die polyedrische Analyse von USApHCP basiert auf einer engen Verwandtschaft des Problems zum "uncapacitated facility location problem" (UFL). Daher gelten viele der in dieser Arbeit dargestellten Ergebnisse auch für UFL.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Silke Baumgartner
URN (Permalink):urn:nbn:de:hbz:386-kluedo-14868
Dokumentart:Diplomarbeit
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2003
Jahr der Veröffentlichung:2003
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):11.04.2007
GND-Schlagwort:Hub-and-Spoke-System ; Polyhedron
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Klassifikation (Mathematik):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $