Lade Inhalt...

Standortlogistik: Zentrenprobleme

Seminararbeit 2005 28 Seiten

BWL - Unternehmensforschung, Operations Research

Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Was sind Zentrenprobleme?
2.1 Einordnung von Zentrenproblemen in die Standortlogistik
2.2 Ausprägungsformen von Zentrenproblemen

3 Diskretes Modell
3.1 Das 1-Center-Problem
3.1.1 Vorüberlegung
3.1.2 Lösungsverfahren
3.1.3 Beispiel
3.2 Das p-Center-Problem
3.2.1 Vorüberlegung
3.2.2 Lösungsverfahren
3.2.3 Beispiel

4 Semidiskretes Modell
4.1 Das 1-Center-Problem
4.1.1 Vorüberlegung
4.1.2 Zentrum im nicht-knotenbewerteten Baum
4.1.3 Zentrum im nicht-knotenbewerteten Graph
4.1.4 Zentrum im knotenbewerteten Graph
4.2 Das p-Center-Problem
4.2.1 Vorüberlegung
4.2.2 Lösungsverfahren
4.2.3 Beispiel

5 Weitere Algorithmen und Ansätze

6 Zusammenfassung

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

Literaturverzeichnis

Anhang

Abbildungsverzeichnis:

Abbildung 1: Ausschnitt aus der Autobahnkarte Deutschlands

Abbildung 2: Anfangslösung nach Anwendung der Gitternetzheuristik

Abbildung 3: Verbesserte Lösung

Abbildung 4: Nicht-knotenbewerteter Baum

Abbildung 5: Nicht-knotenbewerteter Baum mit absolutem Zentrum q*

Abbildung 6: Nicht-knotenbewerteter Graph

Abbildung 7: Graphische Ermittlung eines lokalen Zentrums

Abbildung 8: Minimal spannender Baum mit absolutem Zentrum q**

Abbildung 9: Knotenbewerteter Graph mit allen potentiellen Zentren

Tabellenverzeichnis:

Tabelle 1: Kürzeste-Wege-Matrix

Tabelle 2: Distanzen ausgehend vom „Startknoten“ 3

Tabelle 3: Distanzen ausgehend vom Knoten 6

Tabelle 4: Distanzen aller Knoten von N zu den Knoten 4 und 3 monoton abnehmend sortiert nach der Distanz zu Knoten 4

Tabelle 5: Distanzen aller Knoten von N zu den Knoten 4 und 3

Abkürzungsverzeichnis:

LP-Relaxation Linear Programming Relaxation

1 Einleitung

Die betriebliche Standortplanung hat einen großen Einfluss auf die Konkurrenz­fähigkeit und damit auf die Überlebensfähigkeit eines Unternehmens. So können „günstige“ Standorte den wirtschaftlichen Erfolg erleichtern, während „ungünstige“ Standorte zusätzliche Anstrengungen erfordern, um standortbedingte Wettbewerbsnachteile gegenüber der Konkurrenz zu kompensieren. Darüber hinaus betont auch die geringe Flexibilität hinsichtlich der Veränderung der Standorte eines Unternehmens die Bedeutung einer solchen Entscheidung. (vgl. Domschke/Drexl, 1984, S.5)

Die Frage nach Standorten in Netzwerken hat ihren Ursprung im Kontext der Konsumgüterdistribution in den 60er Jahren des 20. Jahrhunderts mit dem Aufkommen von Outlet-Ketten im Einzelhandel. Industriestandorte wie beispielsweise Produktions­stätten, Beschaffungs- und Auslieferungslager waren so zu wählen, dass die Kosten (Summe aus Lager- und Transportkosten zu den Outlets) minimiert werden. (vgl. Vahrenkamp, 2003, S.119) Neben der Planung neuer Industriestandorte, gehört die Bestimmung von Standorten für zentrale Einrichtungen wie beispielsweise Servicepunkte, kommunale Einrichtungen und Notfall­einrichtungen zu den am häufigsten untersuchten Standortproblemen. (vgl. Domschke/Drexl, 1984, S.83) Sie werden als Zentrenprobleme bezeichnet und erweitern/ersetzen das Ziel der Kostenminimierung durch eine Minimax-Zielsetzung: „Ein Standort ist (oder mehrere Standorte sind) so zu bestimmen, dass der längste Weg, den ein „Benutzer“ zurückzulegen hat oder den man zum Erreichen eines „Benutzers“ zurücklegen muss, möglichst kurz ist." (Domschke/Drexl, 1984, S.83)

Ziel dieser Seminararbeit ist es, Zentrenprobleme und geeignete Lösungsverfahren im Rahmen der Standortlogistik vorzustellen und anhand von Beispielen zu erläutern. Darüber hinaus soll neben der reinen mathematischen Ermittlung von Zentren auch der betriebswirtschaftliche Hintergrund verdeutlicht werden.

Die vorliegende Arbeit gliedert sich dazu in 6 Kapitel. Im Anschluss an die Einleitung (Kapitel 1) folgt die Klassifikation und Einordnung von Zentrenproblemen in die Standortlogistik (Kapitel 2). Anschließend werden die unterschiedlichen Zentrenprobleme und deren Lösungsverfahren beschrieben und jeweils an einem Beispiel verdeutlicht, wobei erst diskrete Modelle (Kapitel 3) und anschließend semidiskrete Modelle behandelt werden (Kapitel 4). Weitere Algorithmen und Ansätze nennt Kapitel 5. Eine Zusammenfassung schließt die Arbeit ab (Kapitel 6).

2 Was sind Zentrenprobleme?

Um einen Einstieg in das Thema zu geben, werden Zentrenprobleme zunächst in die Standortlogistik eingeordnet. Anschließend werden die verschiedenen Ausprägungsformen vorgestellt.

2.1 Einordnung von Zentrenproblemen in die Standortlogistik

Die in der betrieblichen Standortplanung vorgeschlagenen Lösungsansätze zur Bestimmung eines Standortes lassen sich in deskriptive und normative Ansätze kategorisieren. (vgl. Domschke/Drexl, 1984, S.6) Ein allgemeingültiges Lösungsmodell für alle Standortprobleme existiert nicht. (vgl. Current et. al. 2002, S.87)

Ziel deskriptiver Ansätze ist es, aus einer Menge potentieller Standorte einen bzw. mehrere Standorte so auszuwählen, dass unternehmensbezogene Standortanforderungen und vorgefundene Standort­bedingungen weitgehend übereinstimmen. Als Ausgangspunkt dienen Standortfaktorenkataloge. (vgl. Domschke/Drexl, 1984, S.7ff) Die dort aufgeführten Faktoren werden unternehmensspezifisch gewichtet und beispielsweise mit Hilfe von Checklistenverfahren oder Punktbewertungsverfahren (ins­besondere die Nutzwertanalyse) ausgewertet.

Zentrenproblemen gehören neben Coveringproblemen, Medianproblemen, Warehouse-Location-Problemen, Hub-Location-Problemen und der Standortplanung im Transportmodell zu den normativen Ansätzen, (vgl. Vahrenkamp, 2003, S.121; vgl. Domschke/Drexl, 1984, S.10ff) welche mit Hilfe von Modellen und Lösungsverfahren Standorte bezüglich einer konkreten Planungssituation ermitteln. (vgl. Domschke/Drexl, 1984, S.6)

Die konkrete Planungssituation bei Zentrenproblemen kann wie folgt beschrieben werden. Bestimme in einem Netzwerk mit n Knoten p Zentren, so dass die längste der kürzesten Distanzen d(k,i) zwischen einem Knoten i zum nächst gelegenen Zentrum k so klein wie möglich ist. (vgl. Al-Loughani, 1997, S.20; vgl. Vahrenkamp, 2003, S.121; vgl. Domschke/Drexl, 1984, S.83)

Standortfragen dieser Art finden sich beispielsweise bei der Ermittlung von Servicepunkten wie Postämtern und Bankfilialen, kommunalen Einrichtungen wie Schulen und Kindergärten, sowie Notfalleinrichtungen wie Feuerwachen, Polizeistationen, Krankenhäusern und Depots für Rettungsfahrzeuge. (vgl. Vahrenkamp, 2003, S.120; Domschke/Drexl, 1984, S.83)

2.2 Ausprägungsformen von Zentrenproblemen

Bei der Ermittlung von Zentren in Netzwerken lassen sich verschiedene Ausprägungsformen feststellen. Diese wirken sich auf die Komplexität des Problems und damit auch auf die geeigneten Lösungsverfahren aus.

Zunächst kann bezüglich der Menge einzurichtender Zentren unterschieden werden. Die Ermittlung von p Zentren in einem Netzwerk wird in der Literatur als das p-Center-Problem bezeichnet. (vgl. Domschke/Drexl, 1984, S.95; vgl. Vahrenkamp, 2003, S.122) Der Sonderfall, die Ermittlung eines Zentrums, wird als 1-Center-Problem bezeichnet.

Weiterhin lassen sich Zentrenprobleme hinsichtlich der Anzahl potentieller Standorte für die Zentren klassifizieren. Man unterscheidet diskrete und semidiskrete Modelle. Im diskreten Modell ist die Anzahl potentieller Standorte endlich. Hier können lediglich die vorhandenen Knoten im Netzwerk zu Zentren erklärt werden. Probleme dieser Art werden auch als vertex-Center-Probleme bezeichnet. Im semidiskreten Modell gibt es eine unendliche Anzahl potentieller Standorte. Im Gegensatz zu kontinuierlichen Modellen (beispielsweise die Standortbestimmung in der Ebene nach dem Steiner-Weber-Modell) kann ein Zentrum jedoch nur auf einem Knoten des Netzwerkes oder einer existierenden Kante zwischen 2 Knoten errichtet werden. (vgl. Vahrenkamp, 2003, S.120)

Eine dritte Klassifizierungsmöglichkeit bezieht sich auf die Art des zu betrachtenden Netzwerkes. Die Zentrenermittlung kann sich auf Zentren in nicht-knotenbewerteten Bäumen, nicht-knotenbewerteten Graphen oder knotenbewerteten Graphen beziehen. (vgl. Domschke/Drexl, 1984, S.83ff) Darüber hinaus lassen sich noch gerichtete und ungerichtete Graphen unterscheiden. Die in dieser Arbeit vorgestellten Lösungsverfahren beziehen sich ausschließlich auf ungerichtete Graphen.

3 Diskretes Modell

Nach der Einordnung von Zentrenproblemen in die Standortlogistik und der Vorstellung unterschiedlicher Ausprägungsformen in Kapitel 2 werden diese nun der Reihe nach vorgestellt. Kapitel 3 erläutert zunächst die Zentrenermittlung im diskreten Modell. Im Anschluss folgt in Kapitel 4 die Zentrenermittlung im semidiskreten Modell.

3.1 Das 1-Center-Problem

Bei der Beschreibung der Verfahren ist es sinnvoll, sich vorerst den speziellen und einfach zu lösenden Problemen zu widmen und anschließend die Komplexität zu steigern. Aus diesem Grund soll an dieser Stelle mit der Ermittlung eines Zentrums im Netzwerk begonnen werden.

3.1.1 Vorüberlegung

Gegeben sei ein Netzwerk N = (V,E,D) welches aus einer Menge V von n Knoten und einer Menge E von m Verbindungen (Kanten) zwischen den Knoten besteht. Jeder Kante [i,j]ÎE wird eine Distanz (D) d(i,j) zugeordnet. Ein Weg von einem Knoten v1ÎV nach vpÎV kann als eine endliche Knotenfolge W=(v1,v2,…,vp) beschrieben werden, mit dem Startknoten v1 und dem Endknoten vp, wobei kein Knoten mehrfach vorkommen darf. Die Länge des Weges L(W) kann folgendermaßen berechnet werden: [Abbildung in dieser Leseprobe nicht enthalten]

In einem Netzwerk können durchaus mehrere Wege von einem Knoten zu einem anderen Knoten führen. Es ist erforderlich jeweils den kürzesten Weg zwischen den 2 Knoten zu finden, denn das Ziel besteht anschließend darin, den Knoten zu finden, für den der Längste unter den kürzesten Wegen zu allen anderen Knoten minimal ist.

3.1.2 Lösungsverfahren

Zur Ermittlung des Zentrums müssen zunächst die kürzesten Wege zwischen den Knoten berechnet werden. Dazu kann der Dijkstra-Algorithmus (Ermittlung von kürzesten Wegen in gerichteten und ungerichteten Graphen) verwendet werden (vgl. Anhang A). Entsprechende Erläuterungen zum Algorithmus findet man bei Vahrenkamp 2003. Die Distanzen werden in einer „Kürzeste-Wege-Matrix“ dargestellt. Für jeden Knoten wird anschließend der längste der kürzesten Wege ermittelt. Sei also d(i,j) die Länge des kürzesten Weges zwischen zwei Knoten i,jÎV in einem ungerichteten Graphen, dann bestimme für alle iÎV das Maximum der Distanzen zu allen anderen Knoten: [Abbildung in dieser Leseprobe nicht enthalten]

Das Zentrum i* ist der Knoten, bei dem Dmax(i) am Geringsten ist: [Abbildung in dieser Leseprobe nicht enthalten]

In gerichteten Graphen ist die Distanz zwischen 2 Knoten von der Wegrichtung abhängig. Deshalb lassen sich hier 3 Arten von Distanzen unterscheiden.

[[Abbildung in dieser Leseprobe nicht enthalten]] - die maximale Distanz zu allen anderen Knoten ausgehend von i

[Abbildung in dieser Leseprobe nicht enthalten] - die maximale Distanz ausgehend von allen anderen Knoten hin zu i

[Abbildung in dieser Leseprobe nicht enthalten]- maximale Distanz der Summe von Hin- und Rückweg von einem i

zu allen anderen Knoten

Je nach Anwendungsgebiet gibt es somit 3 unterschiedliche Zielfunktionen im gerichteten Graphen.

[Abbildung in dieser Leseprobe nicht enthalten] - schnelles Erreichen anderer Knoten (Bsp. Feuerwehr)

[Abbildung in dieser Leseprobe nicht enthalten] - schnelles Erreichen des Zentrums (Bsp. Bankfiliale)

[Abbildung in dieser Leseprobe nicht enthalten] - schnelle Hin- und Rückfahrt (Bsp. Krankenwagen)

3.1.3 Beispiel

Gegeben sei das folgende Autobahnnetzwerk (Abb. 1). Es werden die kürzesten Wege ermittelt und in eine „Kürzeste-Wege-Matrix“ eingetragen. (Tabelle 1) Für jeden Standort kann der längste der kürzesten Wege anschließend ermittelt werden. So ist beispielsweise der längste Weg von Berlin derjenige nach Frankfurt mit einer Distanz von 660.

Abbildung in dieser Leseprobe nicht enthalten

Der Standort mit dem kleinsten längsten Weg wird Zentrum. In diesem Fall ist i*=Hannover mit Dmax(i*)=390. Der Aufwand des Algorithmus liegt bei O(n3).

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Kürzeste-Wege-Matrix

3.2 Das p-Center-Problem

Nachdem die Ermittlung eines Zentrums im diskreten Modell beschrieben wurde, soll nun eine Verallgemeinerung des Problems vorgenommen werden.

3.2.1 Vorüberlegung

Anstelle eines Zentrums im Netzwerk sind nun[Abbildung in dieser Leseprobe nicht enthalten] Zentren zu errichten, so dass die Längste der kürzesten Wege von einem beliebigen Knoten zum nächst gelegenen Zentrum minimiert wird. Die optimale Anordnung von p-Zentren im Netzwerk N=(V,E,D) kann durch Lösung eines ganzzahligen Optimierungsproblems ermittelt werden. Dazu sind zunächst 2 Binärvariablen yk und xik einzuführen.

Abbildung in dieser Leseprobe nicht enthalten

Daraus ergibt sich folgendes Optimierungsmodell:

Zielfunktion: [Abbildung in dieser Leseprobe nicht enthalten]

Nebenbedingungen: (1) Es werden genau p Zentren eingerichtet:

Abbildung in dieser Leseprobe nicht enthalten

(2) Jeder Knoten i muss an genau ein Zentrum k angeschlossen werden: [Abbildung in dieser Leseprobe nicht enthalten]

(3) Ein Knoten kann nur an einen anderen Knoten angeschlossen werden, wenn dieser ein Zentrum ist:

Abbildung in dieser Leseprobe nicht enthalten

(4) Binaritätsbedingungen:

Abbildung in dieser Leseprobe nicht enthalten

3.2.2 Lösungsverfahren

Anhand der Zielfunktion lässt sich erkennen, dass das Problem nicht linear ist. Bei dem p-Center-Problem handelt es sich um ein NP-hartes Problem. Standardtechniken wie die LP-Relaxation oder die Lagrange-Relaxation können nur bedingt zur Lösung des Problems herangezogen werden, denn vor allem bei großen Modellen ist die Laufzeiteffizienz nicht mehr tragbar. Aus diesem Grund werden Heuristiken oder das Branch&Bound-Verfahren verwendet, welche in möglichst kurzer Zeit eine gute (aber nicht zwingend optimale) Lösung finden sollen. Als Beispiel für eine Heuristik sei hier die Gitternetzheuristik genannt. Sie ermittelt eine Lösung mit p oder weniger Zentren. (vgl. Vahrenkamp, 2003, S.124f)

Vorgehen: 1.) Über die Knoten des Netzwerkes wird ein Gitter mit p gleich großen Rechtecken gezogen.

2.) In jedem Rechteck wird der Knoten zum Zentrum erklärt, der dem Mittelpunkt des Rechtecks am nächsten liegt, sofern das Rechteck einen Knoten enthält.

3.) Zwischen 2 benachbarten Gitterfeldern wird geprüft, ob es möglich ist, ohne Verschlechterung eines der beiden gegenwärtigen Zentren zu schließen.

4.) Zentren werden systematisch mit Nicht-Zentren vertauscht. Bei einer Verbesserung der Lösung wird der neue Zustand übernommen.

5.) Nicht-Zentren werden systematisch anderen Zentren zugeordnet. Bei einer Verbesserung der Lösung wird der neue Zustand übernommen.

3.2.3 Beispiel

Gegeben sei erneut das Autobahnnetz (Abb. 1, S.5). Es sollen 6 Zentren eingerichtet werden. Zunächst muss das Netzwerk mit 6 gleich großen Rechtecken überzogen werden. (Abb. 2). Anschließend werden die Mittelpunkte der Rechtecke ermittelt. Die Knoten, die den Mittelpunkten am nächsten sind, werden zu Zentren erklärt (Dortmund, Hannover, Leipzig, Frankfurt, Kassel und Erfurt). Die maximale Distanz Dmax=199. (Strecke Dresden-Erfurt) Eine Anfangslösung ist somit gefunden. Diese wird nun schrittweise verbessert.

Beim Vergleich benach­barter Gitterfelder können Erfurt und Hannover als Zentren ge­schlossen wer­den. Erfurt und Dresden werden dem Zentrum Leipzig zugeordnet. Han­nover dem Zentrum Kas­sel. Dadurch verbessert sich die maximale Distanz auf Dmax=188. In einem weiteren Verbes­serungsschritt wird Köln an das Zentrum Dortmund ange­schlossen. Die neue maximale Distanz beträgt anschließend Dmax=187.

Abbildung in dieser Leseprobe nicht enthalten

Sind im Verlauf der Verbesserung Zentren ge­schlossen worden, können diese nun erneut gesetzt werden. Sinnvoll erscheint, den Knoten mit der größten Distanz zum Zentrum zu erklären. Berlin und Hannover werden somit jeweils Zentrum. (Abb. 3) Die maximale Distanz beträgt letztlich Dmax=140 mit den Zentren Dortmund, Han­nover, Frankfurt, Kas­sel, Berlin und Leipzig.

4 Semidiskretes Modell

Nachdem in Kapitel 3 die Zentrenermittlung im diskreten Modell beschrieben wurde, widmet sich Kapitel 4 der Zentrenermittlung im semidiskreten Modell. Da die Anzahl der potentiellen Standorte unendlich ist, können die im Kapitel 3 verwendeten Verfahren, die im Wesentlichen einen Vergleich zwischen den potentiellen Standorten durchführen, nicht auf das semidiskrete Modell übertragen werden.

4.1 Das 1-Center-Problem

Analog zu Kapitel 3 soll zunächst vom einfachen Fall, der Ermittlung eines Zentrums, ausgegangen werden.

4.1.1 Vorüberlegung

Gegeben sei wie auch in Abschnitt 3.1.1 ein Netzwerk N = (V,E,D) welches aus einer Menge V von n Knoten und einer Menge E von m Verbindungen (Kanten) zwischen den Knoten besteht. Jeder Kante [i,j]ÎE wird eine Distanz d(i,j) zugeordnet. Auf jeder Kante [i,j] von N lassen sich unendlich viele Punkte q unterscheiden, wobei die Knoten i und j zwei dieser Punkte sind. Die Vereinigung der Punkte aller Kanten von N wird als Punktmenge Q des Netzwerkes bezeichnet. Sei d(q,j) die Distanz (kürzester Weg) zwischen einem Punkt qÎQ und jÎV dann ist Dmax(q) der Längste der kürzesten Wege zu allen Knoten jÎV. [Abbildung in dieser Leseprobe nicht enthalten]Diesen Längsten unter den kürzesten Wegen gilt es zu minimieren. Das absolute Zentrum eines Netzwerkes N ist folglich q*=[Abbildung in dieser Leseprobe nicht enthalten]. D(q*) bezeichnet man als absoluten Radius des Netzwerkes N.

Durch die unendliche Anzahl potentieller Standorte ist bereits die Ermittlung eines Zentrums wesentlich komplexer als im diskreten Modell. Deshalb soll zunächst mit speziellen und einfach zu lösenden Problemen begonnen werden, der Zentrenbestimmung im nicht-knotenbewerteten Baum. Anschließend werden Verfahren für nicht-knotenbewertete Graphen und letztlich für knotenbewertete Graphen vorgestellt.

4.1.2 Zentrum im nicht-knotenbewerteten Baum

Bäume sind spezielle Graphen, die mindestens 2 der 3 folgenden Eigenschaften aufweisen müssen.

1.) Zwischen allen Knoten der Menge V des Netzwerkes existiert ein Weg
2.) Das Netzwerk, bestehend aus n Knoten, hat genau n-1 Kanten
3.) Das Netzwerk enthält keine Zyklen

Lösungsverfahren: Das folgende Verfahren zur Ermittlung eines absoluten Zentrums in einem nicht knotenbewerteten Baum stammt von Handler und besteht im Wesentlichen aus 2 Schritten. (vgl. Handler, 1973)

1.) Wähle einen Knoten i im Baum und bestimme den von i am weitesten entfernten Knoten j
2.) Bestimme den von j am weitesten entfernten Knoten k

Die so ermittelte Distanz zwischen den Knoten j und k ist die längste Kette im Baum. Der Mittelpunkt, also der Punkt q*, mit der Eigenschaft D(q*,j)=D(q*,k) ist absolutes Zentrum. Dmax(q*)=D(q*,j)=D(q*,k) ist absoluter Radius. Der Knoten, der dem Punkt q* am nächsten ist, ist Knoten-Zentrum des Baumes. Somit lässt sich das Verfahren auch bei diskreten Modellen für nicht-knotenbewertete Bäume anwenden.

[...]

Details

Seiten
28
Jahr
2005
ISBN (eBook)
9783638441285
ISBN (Buch)
9783638659208
Dateigröße
715 KB
Sprache
Deutsch
Katalognummer
v47104
Institution / Hochschule
Martin-Luther-Universität Halle-Wittenberg – Wirtschaftswissenschaftliches Institut
Note
1,3
Schlagworte
Standortlogistik Zentrenprobleme Seminar Operations Research

Autor

Zurück

Titel: Standortlogistik: Zentrenprobleme