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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Silke Baumgartner
URN:urn:nbn:de:hbz:386-kluedo-14868
Document Type:Diploma Thesis
Language of publication:English
Year of Completion:2003
Year of first Publication:2003
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2007/04/11
GND Keyword:Hub-and-Spoke-System; Polyhedron
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011