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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Silke Baumgartner
URN (permanent link):urn:nbn:de:hbz:386-kluedo-14868
Document Type:Master's Thesis
Language of publication:English
Year of Completion:2003
Year of Publication:2003
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
GND-Keyword:Hub-and-Spoke-System ; Polyhedron
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik
MSC-Classification (mathematics):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING

$Rev: 12793 $