Erweiterung des 'generalized' p-Median-Problems

Die vorliegende Masterarbeit beschäftigt sich mit den MINISUM-Modellen auf einem Graphen. Die Eigenschaften des „generalized“ p-Median-Problem werden neben den Eigenschaften des ordinären p-Median-Problems untersucht. Dabei kommt folgende Diskrepanz zum Vorschein: Obwohl das „generalized“ p-Median-Problem eine unendliche Anzahl an potenziellen Lösungsmöglichkeiten besitzt und der optimale Standort bei einer derartigen Problemstellung sowohl im Knoten als auch auf der Kante des Graphen liegen kann, wird der Median oft ausschließlich in den Knoten des Graphen gesucht. Dadurch entsteht das Risiko, dass beim Lösen des Problems der optimale Standort von Anfang an nicht mitberücksichtigt wird. Die Forschungsaufgabe dieser Arbeit ist, das „generalized“ p-Median-Problem so zu erweitern, dass aus einem Problem mit unendlicher Anzahl an Lösungsmöglichkeiten ein endliches Problem wird, welches optimal mit einer diskreten Methode gelöst werden kann. Im ersten Schritt werden die potenziellen Standorte auf den Kanten (die sogenannten fiktiven Knoten) ermittelt. Sie werden mit den Knoten des Graphen gleichgestellt und bei der Auffindung des kostenminimalen Standortes einkalkuliert. Damit sind alle potenziellen Standorte abgedeckt und das Problem erhält eine endliche Anzahl an Lösungsmöglichkeiten. Eine weitere Herausforderung liegt in der unkonventionellen Formulierung des Kostenparameters, der beim „generalized“ p-Median-Problem zusätzlich berücksichtigt wird. Die Kosten stellen eine logarithmische Kostenfunktion dar, die von der Verteilung der Nachfrage auf die Mediane abhängig ist. Diese Variable wird als Zuteilung bezeichnet und muss zusätzlich vor der Formulierung des Optimierungsproblems bestimmt werden. Die Zuteilung ist für die Ermittlung der Kosten zuständig und fließt in das Modell nur indirekt mit ein. Abschließend wird die Funktionsfähigkeit des neuen Modells überprüft und dem ursprünglichen Modell (dem umformulierten Warehouse Location Problem) gegenübergestellt. Tatsächlich werden bei dem erweiterten Modell durch die Platzierung der Mediane auf die Kante zusätzliche Kosten eingespart. Die vorliegende Arbeit zeigt das Prinzip, wie das „generalized“ p-Median-Problem erweitert werden kann, und liefert den Beweis über die Funktionstüchtigkeit dieser Methode.The following master’s thesis deals with the MINISUM models on a graph. In this regard the properties of the generalized p-median problem have been investigated alongside the properties of the ordinary p-median problem. In the course of the investigation, the following discrepancy comes to the fore: although the generalized p-median problem has an infinite number of potential solutions, and the optimal location for such a problem may lie in both the vertex and on the edge of the graph, the median is often searched for exclusively in the vertex of the graph. This creates the risk that, upon attempting to find a solution, the optimal location to place the median may not be taken into consideration right from the start. The goal of the following thesis is to extend the generalized p-median problem so that a problem with an infinite number of possible solutions becomes a finite problem which can best be solved with a discrete method. In the first step, all potential locations along the edges (the so-called fictitious vertices) are determined using an empirical-analytical approach. They are equated with the vertices of the graph and taken into account when locating the minimum cost location. This covers all potential locations and through this method the problem receives a finite number of possible solutions. Another challenge lies in the unconventional formulation of the cost parameter, which is additionally taken into account in the generalized p-median problem. The cost represents a logarithmic cost function that depends on the distribution of demand on the median. In the following work, this variable shall be called the allocation and must first be determined in order to formulate the optimization problem framework. The allocation is responsible for determining the costs and is included only indirectly in the model. Finally, the functionality of the new model is checked and compared with the original model, the rewritten warehouse location problem. In fact, the placement of medians on an edge saves additional costs in the extended model. The following elaboration shows the principle of how the generalized p-median problem can be extended, and provides proof of the functionality of this extension