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.