Embed Size (px)
Citation preview
Marius Kurth
Bachelorarbeit
Standortplanung - State of the Art
Themasteller: Jun.-Prof. Dr. Ali Sunyaev
Vorgelegt in der Bachelorprüfung
im Studiengang Wirtschaftsinformatik
der Wirtschafts- und Sozialwissenschaftlichen Fakultät
der Universität zu Köln
Köln, April 2013
II
Inhaltsverzeichnis Abkürzungsverzeichnis....................................................................................................III
Abbildungsverzeichnis ................................................................................................... IV
Tabellenverzeichnis .......................................................................................................... V
1. Einleitung ......................................................................................................................1
1.1 Problemstellung ........................................................................................................1
1.2 Zielsetzung ...............................................................................................................2
1.3 Vorgehensweise und Aufbau der Arbeit ..................................................................2
2. Einführung in die grundlegenden Modelle der Standortoptimierung ...........................3
2.1 p-Median Problem ....................................................................................................4
2.2 p- Center Problem ....................................................................................................6
2.3 Covering Problem ....................................................................................................8
2.4 Lösungsverfahren der Center und Median Probleme .............................................10
2.5 Übersicht verschiedener Modelle ...........................................................................12
3. Maximal Covering Location Problem ........................................................................16
3.1 Charakteristika des MCLP .....................................................................................16
3.1.1 Eingliederung in die Standortprobleme ........................................................16
3.1.2 Definition des MCLP ....................................................................................17
3.2 Techniken zur Lösung der Probleme .....................................................................18
3.2.1 Heuristische Methoden .................................................................................19
3.2.2 Lineare Programmierung ..............................................................................20
3.3 Erweiterungen zum MCLP.....................................................................................23
4. Forschungsagenda .......................................................................................................26
4.1 Offene Punkte der Modelle der Standortplanung ...................................................26
4.2 Forschungsansätze zur Vervollständigung der Modelle ........................................27
5. Fazit .............................................................................................................................29 Literaturverzeichnis .........................................................................................................31
Erklärung .........................................................................................................................36
Lebenslauf........................................................................................................................37
III
Abkürzungsverzeichnis
ACLP
GA
GAS
GPAH
LSCP
MEXCLP
MCLP
MCLPDC
MPS
QMCLP
SA
TS
UFLP
Anti-Covering Location Problem
Greedy Adding
Greedy Adding with Substitution
Greedy paired adding heuristic
Location Set Covering Problem
Maximal Expected Covering Location Problem
Maximal Covering Location Problem
Minimum Covering Location Problem with Distance
Constraints
Mathematical Programming System
Quadratic Maximal Covering Location Problem
Simulated Annealing
Tabu Search
Uncapacitated Facility Location Problem
IV
Abbildungsverzeichnis
Abb. 2-1 : Median und absoluter Median in einem Graph ..............................................5
Abb. 2-2 : (a) Center und (b) absolutes Center in einem Graph ......................................7
Abb. 2-3 : Eine Lösung des Covering Location Problem mit S = 15 ............................10
V
Tabellenverzeichnis
Tab. 2-1: Distanzen zwischen den Knoten in einem Graph ...........................................5
Tab. 2-2: Minimierung der durchschnittlichen Fahrtzeit/
durchschnittlichen Kosten oder Maximierung der Einkünfte .......................13
Tab. 2-3: Minimierung der durchschnittlichen Reaktionszeit ......................................13
Tab. 2-4: Minimierung der maximalen Fahrtzeiten bzw. Fahrtkosten .........................14
Tab. 2-5: Minimierung der maximalen Reaktionszeit ..................................................14
Tab. 2-6: Maximierung der minimalen oder durchschnittlichen Fahrtzeit
bzw. Fahrtkosten ...........................................................................................15
Tab. 2-7: Standortprobleme mit anderen Zielen...........................................................16
Tab. 3-1: Vergleich der Lösungsverfahren des MCLP's ..............................................22
1
1. Einleitung
1.1 Problemstellung
Das Thema der Standortplanung umfasst unterschiedliche Probleme, welche mit Hilfe
von verschiedenen Modellansätzen der Forschung identifiziert und gelöst werden
können.1 Die Wahl von Standorten ist fester Bestandteil von unternehmerischen
Entscheidungen, um die Nachfrage effizient abdecken zu können.2 Unter der
Abdeckung der Nachfrage versteht man im optimalen Fall, dass die Nachfrage jedes
potenziellen Kunden vollständig und innerhalb eines bestimmten Radius von der
positionierten Einrichtung abgedeckt wird.3 Das Ziel der Standortoptimierung ist es,
Einrichtungen so in einem Bezirk zu positionieren, dass die Abhängigkeit von der neuen
Einrichtung optimiert wird.4 Typische Kriterien für diese Optimierung sind die
Minimierung der durchschnittlichen Fahrtzeit oder Distanz zwischen den
Nachfragepunkten, von denen die Nachfrage ausgeht, und dem Standort, die
Minimierung der Antwortzeit der Standorte, die Minimierung der Kostenfunktion der
Fahrt- bzw. Antwortzeit, die Minimierung der maximalen Fahrtzeit oder auch die
Maximierung der minimalen Fahrtzeit.
Forscher haben sich in den letzten Jahren intensiv mit dem Thema der Standortplanung
und -optimierung beschäftigt, und dabei verschiedene Lösungsansätze vorgestellt.5
Diese verschiedenen Modellansätze liefern unterschiedliche Ergebnisse und stellen
somit keine einheitliche Lösung dar.
Die Forschungsfrage, die daraus resultiert, kann folgendermaßen definiert werden:
„Wie kann das Forschungspotential der Standortplanung verdeutlicht werden?“
Zur Lösung des beschriebenen Problems werde ich in meiner Arbeit eine strukturierte
Übersicht der Modellansätze der Standortplanung herausarbeiten. Die Erstellung einer
solchen Übersicht ermöglicht späterer Forschung entsprechende Lücken anzugehen und
Lösungen hervorzubringen.
1 Vgl. Brandeau (1989), S. 645-646. 2 Vgl. Hale (2003), S. 21-22. 3 Vgl. Berman (2010), S. 1675. 4 Vgl. zu diesem und folgendem Satz Brandeau (1989), S. 646. 5 Vgl. Brandeau (1989), S. 645.
2
1.2 Zielsetzung
Das Hauptziel meiner Arbeit ist die Erstellung einer Übersicht der Ansätze zur
Standortplanung bzw. Standortoptimierung mit Fokus auf das Maximal Covering
Location Problem (MCLP) und deren Erweiterungen.
Ein Teilziel des übergeordneten Hauptziels besteht zunächst in der Einführung in die
grundlegenden Modelle der Standortoptimierung und der damit verbundenen
Erläuterung der verschiedenen Vorgehensweisen. Hierzu werden p-Center Probleme,
p-Median Probleme und Covering Probleme als Basis für die weiteren Modelle
erläutert.6 Wie lassen sich die Probleme definieren und voneinander abgrenzen?
Anschließend werden die verschiedenen Ansätze zur Standortoptimierung erläutert.
Welche Modelle existieren und bei welchen Standortplanungsproblemen werden sie
eingesetzt? Ein weiteres Teilziel wird die präzise Auseinandersetzung mit dem Maximal
Covering Location Problem sein. Was gibt es für Erweiterungen zu diesem Ansatz?
Zudem werde ich auf offene Punkte der vorgestellten Modelle eingehen. Wie kann die
Forschung die aufgezeigten Lücken der Modelle schließen?
1.3 Vorgehensweise und Aufbau der Arbeit
Da es sich bei dieser Arbeit um ein Literaturreview handelt, ist ein wesentlicher
Bestandteil die Suche und Auswahl relevanter Literatur. Um das Hauptziel , die
Erstellung einer Übersicht der Ansätze zur Standortplanung, zu bearbeiten, können viele
Artikel mit Hilfe der Datenbank EBSCO-Host beschafft werden. Jedoch sind relevante
Zeitschriften in der Datenbank EBSCO-Host nicht verfügbar und müssen über andere
Datenbanken beschafft werden. Mit Hilfe der beiden Datenbanken Science Direkt und
ProQuest lassen sich aber die in EBSCO-Host nicht enthaltenen Zeitschriften zu diesem
Thema ohne Probleme finden. Das weitere Vorgehen besteht also in der Selektion der
Artikel, die für die Erreichung der Teilziele notwendig sind und in der Untersuchung
der relevanten Artikel nach den in den Teilzielen festgelegten Merkmalen. Die Artikel
werden hinsichtlich ihrer Relevanz, vor allem mit Fokus auf das Maximal Covering
Location Problem und deren Erweiterungen, selektiert.
Der Aufbau dieser Arbeit lässt sich folgendermaßen beschreiben. In Kapitel 2 wird in
das Thema der Standortplanung eingeführt und die grundlegenden Modelle vorgestellt.
6 Vgl. Francis (1983), S. 485.
3
Dazu wird zunächst auf die als Basis fungierenden Probleme p-Center, p-Median und
Covering mit den zugehörigen Modellen eingegangen. Anschließend wird eine
Übersicht über verschiedene, repräsentative Modellansätze zur Standortoptimierung in
From von mehreren Tabellen dargestellt.
In Kapitel 3 wird das im Fokus stehende Thema MCLP erläutert. Hierzu wird nach der
Einführung des Problems, der Übersicht der Modellansätze und der Vorstellung der
Lösungstechniken der Modelle, auch auf die verschiedenen Erweiterungen des MCLP's
eingegangen. Im folgenden Kapitel 4 werden offene Punkte und Lücken der
vorgestellten Modelle dargelegt. Außerdem werden Forschungsansätze zur
Vervollständigung der Modelle aufgezeigt. Das Kapitel 5 schließt diese Arbeit mit
einem Fazit zu dem vorgestellten Thema Standortplanung mit Fokus auf das MCLP ab.
2. Einführung in die grundlegenden Modelle der Standortoptimierung
Standortprobleme lassen sich in drei verschiedenen Bereichen lösen. Zum einen gibt es
den konstanten Bereich (continuous space), in der jeder Standort des Bereichs ein
möglicher Standort für Einrichtungen sein kann. Der zweite Bereich bezieht sich auf
Probleme, in denen Standorte aus einer vorher definierten Auswahl ausgewählt werden
(discrete spaces) und letztlich der dritte Bereich, mit dem ich mich im Folgenden
vornehmlich befassen werde, beschäftigt sich mit Problemen, welche durch den Radius
und die Knoten eines grundlegenden Netzwerks begrenzt sind (network spaces).7
Ein Netzwerk im örtlichen Einzelhandel aufzubauen ist eine komplexe Aufgabe. Es gilt
eine Menge von wichtigen Entscheidungen zu treffen, wie die Anzahl der zu öffnenden
Einrichtungen im Markt, der Position der Einrichtungen und die Charakteristiken dieser
Einrichtungen. Um diese Entscheidungen effizient lösen zu können, werden die im
weiteren Verlauf vorgestellten Standortmodelle genutzt. Das gemeinsame Ziel, das die
Modelle verfolgen, lässt sich folgendermaßen als Frage formulieren: Wie können
Einrichtungen im Einzelhandel positioniert werden, so dass sie die Bevölkerung optimal
bedienen?8
Der Anwendungsbereich der Standortmodelle umfasst mehrere verschiedene Probleme.9
Darin enthalten sind beispielsweise die Positionierung eines Geschäfts in einer
7 Vgl. zu diesem Absatz Hale (2003), S. 22. 8 Vgl. zu diesem Absatz Gosh (1987), S. 128. 9 Vgl. zu diesem und folgendem Satz Hale (2003), S. 22.
4
Geschäftskette zur Minimierung der durchschnittlichen Fahrtzeit zu dieser Einrichtung,
die Positionierung von gefährlichen Materialien zur Minimierung des Kontakts mit der
Öffentlichkeit, die Positionierung von Bahnstationen zur Minimierung der Variabilität
eines Lieferplans, die Positionierung von Bankautomaten zur Optimierung des Services
der Bank-Kunden oder die Positionierung einer Küstenwache und einer Rettungsstation
zur Minimierung der maximalen Reaktionszeit auf mögliche Unglücke. An diesen
repräsentativen Problemen lässt sich schnell erkennen, dass die Modelle der
Standortplanung durchaus verschiedene Ziele verfolgen. Zum Einstieg in die
verschiedenen Modelle werden in den folgenden Unterkapiteln die drei grundlegenden
Probleme erläutert.
2.1 p-Median Problem
Das p-Median Problem wird auch als Minisum Problem bezeichnet.10 Das Problem wird
mit m gegebenen Punkten in der Ebene und m zugehörigen, positiven Gewichten
definiert.11 Jeder Knoten (Punkt) des Graphen stellt hierbei einen Punkt der Nachfrage
sowie einen potenziellen Standort der Einrichtung dar.12 Das Niveau der Nachfrage
eines Punktes ist dabei durch das zugehörige Gewicht gegeben. Ziel ist es die Position
in der Ebene zu finden, mit dem die gewichtete Summe der Distanzen der Punkte
minimiert wird.13 Demnach wird eine Reduzierung der Summe der gewichteten
Distanzen zwischen der Nachfrage und der Einrichtung angestrebt, durch eine optimale
Positionierung der Einrichtung. Auf der Suche nach der optimalen Position für p-
Einrichtungen, beschäftigt sich das p-Median Problem also auch mit der Platzierung
von mehreren Einrichtungen. Das Minisum Problem wird im Folgenden auf eine
Positionierung von Einrichtungen in einem Graphen bezogen. Hierbei müssen die
Einrichtungen entweder auf einem Knoten oder einer Kante des Graphen errichtet
werden.14 Wenn die Einrichtung nur auf Knoten des Graphen positioniert werden kann,
um die Summe der Distanzen zu jedem Knoten von der nächstgelegenen Einrichtung
aus zu minimieren, so nennt man die Einrichtung Median. Falls die Einrichtung nach 10 Vgl. zu diesem Satz Hale (2003), S. 22. 11 Vgl. zu diesem Satz Peeters (1985), S. 1251. 12 Vgl. zu diesem und folgendem Satz Church (2003), S. 103. 13 Vgl. zu diesem Satz Ghosh (1987), S. 137 und Peeters (1985), S. 1251. 14 Vgl. zu diesem und folgendem Satz Minieka (1977), S. 641.
5
dem gleichen Verfahren entweder auf Knoten oder Kanten des Graphen positioniert
werden kann, spricht man von einem absolute Median.15 Zur Verdeutlichung lässt sich
die Positionierung einer Einrichtung als Median bzw. als absolute Median anhand der
Abbildung 2-1 und der dazugehörigen Tabelle 2-1 aufzeigen.
Abb. 2-1: Median und absoluter Median in einem Graph16
Tab. 2-1: Distanzen zwischen den Knoten in einem Graph17
Jede Kante der Abbildung 2-2 hat die Länge eins und die Distanzen der Knoten
zueinander sind in der Tabelle 2-2 abgebildet. Wenn man nun die Summen der
gewichteten Distanzen zu den einzelnen Punkten betrachtet, kann man erkennen, dass in
diesem Beispiel sowohl Knoten b als auch Knoten e minimal sind. Das bedeutet, dass in
diesem Fall zwei minimale Distanzen der Länge 9 vorliegen und somit beide Punkte als
Median bezeichnet werden können. Falls man jetzt aber davon ausgeht, dass eine
15 Vgl. zu diesem Satz Minieka (1977), S. 641. 16 Minieka (1977), S. 646. 17 Minieka (1977), S. 646.
6
Einrichtung entweder auf einem Knoten oder einer Kante positionieren werden kann,
also nach dem absolute Median gesucht wird, ändert sich das Ergebnis. Es wird ein
Punkt x auf den Mittelpunkt der Knoten b und e gesetzt, wie man in der Abbildung 2-3
erkennen kann. Dadurch entsteht eine neue minimale Distanz, welche die Summe 8 1/2
besitzt und ebenfalls in der Tabelle 2-3 aufgelistet ist. Dieser neu positionierte Punkt in
dem Graphen wird aufgrund seiner minimalen Summe der gewichteten Distanzen als
absolute Median bezeichnet.18
Wenn man in Folge dessen davon ausgeht, dass sich die potenziellen Kunden nun auch
nicht nur auf den Knoten des Graphen, sondern auf jedem Punkt der Kanten befinden
können, spricht man von einem general Median.19 Zusätzlich lassen sich die p-Median
Probleme in condtional und nicht unconditional unterteilen.20 Während beim
uncondtional p-Median Problem noch keine Einrichtung im Graphen existiert, ist die
Anzahl der existierenden Einrichtungen beim condtional p-Median Problem größer als
null. Vor allem wurde das p-Median Problem in einem Netzwerk von Hakimi (1965),
Kariv und Hakimi (1979b), Goldman (1971), und Minieka (1977) untersucht.21
2.2 p- Center Problem
Parallel zum p-Median Problem wurde das p-Center Problem erforscht, welches
besonders durch Hakimi (1965), Minieka (1970, 1977), Kariv und Hakimi (1979b),
Elzinga und Hearn (1972), und Tansel, Francis und Lowe (1982) untersucht wurde.22 Im
Gegensatz zu dem p-Median Problem findet das p-Center Problem mehr Anwendung
bei der Positionierung von öffentlichen Einrichtungen, wie Krankenhäusern oder auch
Polizeistationen.23 Man spricht hierbei auch von einem Minimax Problem, da versucht
wird eine Einrichtung so zu positionieren, dass die maximal gewichtete Distanz zur
Einrichtung minimiert wird. Auch das p-Center Problem wird mit m gegebenen Punkten
in der Ebene und m zugehörigen, positiven Gewichten definiert.24 Weil sich das
18 Vgl. zu diesem Absatz Minieka (1977), S. 645-646. 19 Vgl. zu diesem Satz Minieka (1980), S. 265. 20 Vgl. zu diesem und folgendem Satz Minieka (1980), S. 266. 21 Vgl. zu diesem Satz Hale (2003), S. 23. 22 Vgl. zu diesem Halbsatz Hale (2003), S. 25. 23 Vgl. zu diesem und folgendem Satz Hakimi (1964), S. 450. 24 Vgl. zu diesem Satz Peeters (1985), S. 1251.
7
p-Center Problem ebenfalls auf die Positionierung einer oder mehrerer Einrichtungen in
einem Graphen bezieht, kann die Einrichtung wie eben beschrieben nur auf Kanten oder
Knoten des Graphen platziert werden.25 Analog zu dem p-Median Problem werden
Einrichtungen, die nur auf Knoten des Graphen platziert werden können, als Center und
Einrichtungen, die entweder auf Knoten oder Kanten des Graphen positioniert werden
können, als absolute Center bezeichnet. Auch die Definition der generellen Position
beim p-Median Problem kann bei dem p-Center Problem angewendet werden. Man
spricht also von einem general Center, falls sich die zu bedienenden Kunden entweder
auf einem Knoten oder einem beliebigen Punkt auf den Kanten des Graphen befinden
dürfen.26
In der Abbildung 2-2 lässt sich schnell erkennen, dass das Center des Graphen (a) v4 ist,
da die maximal gewichtete Distanz zu diesem Knoten mit einem Gewicht von 20
minimal ist.27 Um jedoch in diesem Beispiel eine Einrichtung als absolute Center zu
positionieren, muss wie im Graph (b) vorgegangen werden und die Einrichtung
möglichst genau in die Mitte von v2 und v3 gesetzt werden. Durch dieses Vorgehen
erhält man eine maximal gewichtete Distanz von 18, welche also ein besseres Ergebnis
liefert als die Position des Knotens v4.
Abb. 2-2: (a) Center und (b) absolutes Center in einem Graph28
Es wird deutlich, dass ein p-Center Problem, in dem eine einzige Einrichtung im
Netzwerk als Center positioniert werden soll, sehr schnell gelöst werden kann. 25 Vgl. zu diesem und folgendem Satz Minieka (1977), S. 641. 26 Vgl. zu diesem Satz Minieka (1980), S. 265. 27 Vgl. zu diesem und folgendem Satz Hakimi (1964), S. 451-452. 28 Hakimi (1964), S. 452.
8
Hingegen ist die Platzierung einer Einrichtung als absolute Center durchaus schwieriger
zu lösen. Wie auch das p-Median Problem lässt sich das p-Center Problem sowohl in
conditional, wenn bereits eine gegebene Anzahl von Einrichtungen im Graph
positioniert ist, als auch in unconditional, wenn noch keine Einrichtung im Graph
vorhanden ist, unterteilen.29 In Kapitel 2.4 werden die Lösungsverfahren zu diesen
beiden Problemen und zu den zuvor vorgestellten Positionierungen des Medians und
des absolute Medians vorgestellt.
2.3 Covering Problem
Der Aspekt des Covering Problems wurde erstmals 1971 von Toregas formuliert.30
Eines von mehreren Covering Problemen, das so genannte Set Covering Problem,
wurde unter anderem von Minieka (1970), Moore und ReVelle (1982), Beasley (1990),
Lorena und Lopes (1994), Beasley und Chu (1996), und von Caprara, Fischetti und
Toth (1999) untersucht.
Covering Probleme sind Standortprobleme mit dem speziellen Aspekt, dass die
maximale Zeit oder Distanz, die ein potenzieller Kunde von seiner nächstgelegenen
Einrichtung entfernt ist, ein ausschlaggebender Parameter ist. Aus diesem Grund findet
das Problem besonders Beachtung bei der Positionierung von Notfalldiensten, wie
Feuerwehrwachen, aber auch bei der Positionierung von gewöhnlichen Diensten, wie
z.B. Schulen und Bibliotheken. Wenn ein oberes Limit im Bezug auf die Reaktionszeit
oder die Distanz zu jedem Kunden festgesetzt wird, können die minimalen Kosten der
Einrichtungen, die den Bereich der potenziellen Kunden abdecken, bestimmt werden.
Falls die Kosten für jede mögliche Position der Einrichtung identisch sind, so lässt sich
ein weiteres, äquivalentes Problem formulieren, welches die Anzahl der erforderlichen
Einrichtungen minimiert, um die Reaktionszeit oder die Distanz zu jedem Kunden zu
erfüllen. Die Lösung dieses Problems zeigt sowohl die Anzahl als auch die Position der
Einrichtungen auf, um die gewünschten Leistungen bereitzustellen.31 Die Hauptaussage
des Covering Problems ist also, dass bei einem gegebenen Erreichbarkeitsradius
versucht wird die Anzahl der Einrichtungen zu minimieren bzw. den Versorgungs- oder
Abdeckungsgrad zu maximieren.
29 Vgl. zu diesem Satz Minieka (1980), S. 266. 30 Vgl. zu diesem und folgendem Satz Hale (2003), S. 25. 31 Vgl. zu diesem Absatz Swain (1971), S. 1363.
9
Im Rahmen der Standortplanung sind vor allem die zwei Problemtypen Location Set
Covering Problem (LSCP) und Maximum Covering Location Problem aufzuführen,
wobei die Thematik des MCLP's noch ausführlich in Kapitel 3 erläutert wird. Um einen
Einblick in die verschiedenen Ansätze der Covering Probleme zu bekommen, wird im
Folgenden auf das repräsentative LSCP eingegangen. Der zuvor angesprochene
Erreichbarkeitsradius, auch als maximale Abdeckungs-Distanz einer Einrichtung zu
beschreiben, spielt in dem Location Set Covering Problem eine große Rolle.32 Bei
diesem Problem wird die minimale Anzahl und die Position der Einrichtungen so
identifiziert, dass kein potenzieller Kunde weiter von der zu positionierenden
Einrichtung entfernt ist, als von der maximalen Abdeckungs-Distanz vorgegeben. In der
folgenden Abbildung 2-3 wird eine Lösung des Location Set Covering Problem
dargestellt, in der die Punkte der Kunden in fünf Bereiche unterteilt sind und jeder
Punkt zu der nächstgelegenen Einrichtung zugeordnet ist. Die maximale Abdeckungs-
Distanz S der Einrichtungen ist jeweils durch eine gestrichelte Linie (S=10 Einheiten)
und eine durchgezogene Linie (S=15 Einheiten) gekennzeichnet.
32 Vgl. zu diesem und folgendem Satz Church (1974), S. 101-102.
10
Abb. 2-3: Eine Lösung des Covering Location Problem mit S = 1533
Im LSCP wird also versucht die vollständige Nachfrage des ausgewählten Bereichs
abzudecken, indem die geringste mögliche Anzahl an Einrichtungen positioniert wird.34
2.4 Lösungsverfahren der Center und Median Probleme
Da auf verschiedene Lösungsansätze der Covering Probleme noch ausführlich im
Bereich des MCLP's (Kapitel 3) eingegangen wird, beschäftigt sich dieses Kapitel nur
mit den Ansätzen der Center (Minimax) und Median (Minisum) Probleme.
Um Median und Center Probleme, wie sie im Kapitel zuvor vorgestellt wurden, lösen zu
können, betrachtet man eine Matrix 𝐷 = [𝑑 ] eines Graphen 𝐺 mit 𝑛 Knoten mit der
Bedingung: 𝑑 = 𝑑 𝑣 , 𝑣 , 𝑓ü𝑟 𝑖, 𝑗 = 1,2, … , 𝑛, 𝑢𝑛𝑑 𝑖 ≠ 𝑗,𝑑(𝑣 , 𝑣 ) = 0, 𝑓ü𝑟 𝑖 = 𝑗, 𝑖 = 1,2… , 𝑛.
�
Dabei lässt sich 𝑑 als maximaler Wert einer Spalte in 𝐷 definieren. Falls 𝑑 =min (𝑑 , 𝑑 , … , 𝑑 ), so ist 𝑣 das Center des Graphen 𝐺. Um also ein
1-Center Problem in einem Graphen zu lösen, wird in einer Matrix D nach der Reihe 33 Vgl. zu dieser Abbildung Church (1974), S. 115. 34 Vgl. zu diesem Satz Davari (2013), S. 68.
11
gesucht, in der der maximale Wert am geringsten ist. Dieser gefundene Punkt entspricht
demnach dem 1-Center des vorliegenden Graphen. Ähnlich wie das Center wird auch
der Median eines Graphen über die vorgestellte Matrix definiert. Es wird 𝑑 als Summe
der i-ten Spalte von 𝐷 bzw. 𝐺 definiert. Falls 𝑑 = min(𝑑 , 𝑑 , … , 𝑑 ), so ist 𝑣 der
Median des Graphen. Es wird also beim 1-Median Problem nach der Reihe der Matrix
gesucht, dessen Summe einen minimalen Wert liefert.35
Der folgende Teil befasst sich mit der conditional-Version der beiden Probleme, in der
sich bereits Einrichtungen in einem Netzwerk befinden. Berman und Simchi-Levi
verfolgen in ihrem Algorithmus das Ziel, dass eine neue potenzielle Einrichtung alle
existierenden Einrichtungen repräsentiert. Hierbei ist die Distanz zwischen einem
Nachfragepunkt und der neuen Einrichtung die minimale Distanz zwischen den
existierenden Einrichtungen. Um die Positionierung der neuen Einrichtung zu
erzwingen, wird ein neuer Nachfragepunkt betrachtet, der eine Distanz von null zu dem
neuen Standort aufweist und sehr weit entfernt von allen anderen potenziellen
Standorten ist. Die neue Matrix wird hier als 𝐷′ bezeichnet und dadurch definiert ist,
dass eine neue Einrichtung (neue Spalte) 𝑎 zu 𝐷, mit 𝑄 existierenden Einrichtungen
und einem neuen Nachfragepunkt 𝑣 (mit beliebigen Gewicht), hinzugefügt wird. Für
jeden normalen Nachfragepunkt 𝑖 gilt: 𝑑(𝑖, 𝑎 ) = min ∈ {d } und: 𝑑(𝑣 , 𝑎 ) = 0.
Außerdem gilt für jeden potenziellen Standort j: 𝑑(𝑣 , 𝑗) = 𝑀, wobei 𝑀eine große Zahl
ist.36
Abschließend werden die Ansätze zu den Modellen absolute Center und absolute
Median betrachtet, in denen eine Einrichtung auf Knoten und auch auf Punkten der
Kanten eines Graphen positioniert werden kann. Es wird ein Punkt 𝑥 in einem
gewichteten Graphen 𝐺 als absolute Center von 𝐺 definiert, falls für jeden Punkt 𝑥 aus
𝐺 gilt: 𝑚𝑎𝑥 ℎ 𝑑(𝑣 , 𝑥 ) ≤ 𝑚𝑎𝑥 ℎ 𝑑(𝑣 , 𝑥). Ebenso wird bei der Bestimmung
des absolute Median ein Punkt 𝑦 als absolute Median in einem Graphen definiert, falls
für jeden Punkt 𝑦 aus 𝐺 gilt: ∑ ℎ 𝑑(𝑣 , 𝑦 ) ≤ ∑ ℎ 𝑑(𝑣 , 𝑦).37
Falls es darum geht eine einzelne Einrichtung in einem Graphen zu positionieren, liefert
vor allem Hakimi (1964) Lösungsansätze zu den Median und Center Problemen bzw. zu
35 Vgl. zu diesem Absatz Hakimi (1964), S. 451. 36 Vgl. zu diesem Absatz Berman (1990), S. 77-78 und Kaveh (2012), S. 33. 37 Vgl. zu diesem Absatz Hakimi (1964), S. 451.
12
den absolute Median und absolute Center Problemen. Sollte die Anzahl der zu
positionierenden Einrichtungen größer als eins sein, gibt es eine Vielzahl von
Lösungstechniken, die entwickelt worden sind. Letztlich sind all diese Techniken auf
die Lineare Programmierung angewiesen, welche ebenfalls noch in Kapitel 3
aufgeführt wird.38
2.5 Übersicht verschiedener Modelle
Die Standortplanung umfasst viele verschiedene Modellansätze, die sich vor allem
durch ihre Zielsetzung unterscheiden und im Folgenden nach sechs unterschiedlichen
Zielen gruppiert sind.39 Eine Auswahl verschiedener Probleme zu den einzelnen
Kategorien ist auf den nächsten Seiten in Form von Tabellen dargestellt.
Minimierung der durchschnittlichen Fahrtzeit/ durchschnittlichen Kosten oder Maximierung der Einkünfte (beinhaltet das p-Median Problem):
Problem Definition
Median problem
with uncertainty
Erweiterung des zuvor beschriebenen p-Median Problems, in dem die
Nachfrage und/oder Fahrtzeiten in einem Netzwerk zufällige Variablen
sind.
Mobile server on a
stochastic network
Es werden eine oder mehrere Einrichtungen positioniert, welche zu einem
Preis bewegt werden können, um auf Änderungen der relativen
Fahrtzeiten reagieren zu können.
𝑳𝒑 norm network
location
Es wird eine einzelne Einrichtung im Netzwerk positioniert, um die
durchschnittlichen Fahrtzeiten zu minimieren, wobei die Summe der
Distanzen durch eine 𝑳𝒑 Metrik gemessen wird.
Weber Simples Minisum Problem, in dem eine Einrichtung positioniert wird, um
die Nachfrage eines Bereichs abzudecken, indem die Fahrtzeiten
minimiert werden.
Unreliable
p-median
Dieses Problem verallgemeinert das vorgestellte, lineare Minisum
Problem, indem es die Möglichkeit einschließt, dass Einrichtungen inaktiv
werden. Es werden p- Einrichtungen mit dem Ziel der Minimierung der
Fahrtzeiten unter der Berücksichtigung, dass Einrichtungen zu jeder Zeit
38 Vgl. zu diesem Absatz Minieka (1977), S. 641. 39 Vgl. zu diesem Satz Brandeau (1989), S. 647.
13
scheitern können, positioniert.
Hub location Es wird versucht eine Einrichtung zentral (hub ) zu positionieren, dass die
Summe der gewichteten Distanzen von jedem Nachfragepunkt über die
Einrichtung zu jedem anderen Nachfragepunkt minimiert wird.
Facility layout Es wird versucht eine fixe Nummer von Einrichtungen zu positionieren,
sodass der Kostenfluss zwischen den Einrichtungen minimiert wird und
Standorte aus einem begrenzten Bereich gewählt werden.
Linear assignment Das Ziel hierbei ist Einrichtungen in Bereichen zu bestimmen, sodass die
Transportkosten zwischen Einrichtungen und Nachfragepunkten minimiert
werden.
Location routing Es soll eine undefinierte Anzahl an Einrichtungen positioniert werden,
sodass die Betriebskosten und die Fahrtkosten in einem Netzwerk
minimiert werden.
Transportation
location
Es wird eine fixe Anzahl an Einrichtungen positioniert und die Menge der
zu transportierenden Waren festgesetzt, sodass die Transportkosten
minimiert werden.
Production-
location
Ziel ist es hierbei Einrichtungen zu positionieren und gleichzeitig den
optimalen Produktions-Input für jede Einrichtung festzusetzen, sodass der
Gewinn maximiert wird.
Tab. 2-2: Minimierung der durchschnittlichen Fahrtzeit/ durchschnittlichen Kosten oder
Maximierung der Einkünfte40
Minimierung der durchschnittlichen Reaktionszeit:
Problem Definition
Stochastic loss median Eine einzelne Einrichtung wird in einem
Netzwerk mit dem Ziel positioniert, dass eine
gewichtete Funktion der Transportkosten und
die Ersatzkosten von verlorenen Kunden
minimiert werden.
Stochastic queue median Hierbei wird eine einzelne Einrichtung mit
einer unbegrenzter Warteschlangen Kapazität
positioniert und die durchschnittliche
Reaktionszeit minimiert.
Tab. 2-3: Minimierung der durchschnittlichen Reaktionszeit41 40 Vgl. zu dieser Tabelle Brandeau (1989), S. 650, 653, 654, 661.
14
Minimierung der maximalen Fahrtzeiten bzw. Fahrtkosten (beinhaltet p-Center Problem und Covering Probleme):
Problem Definition
Unreliable p-center Passend zum Unreliable p-median Problem ist
dieser Ansatz ein lineares Minimax Problem,
welches die Möglichkeit beinhaltet, dass bis
zu q Einrichtungen zu jeder Zeit scheitern
können.
k-centrum Ähnlich wie das 1-center Problem ist das Ziel
dieses Problems, dass eine einzelne
Einrichtung positioniert wird und dabei die
Summe der Distanzen zwischen der
Einrichtung und den weit entferntesten
Nachfragepunkten minimiert wird.
Hierachical covering Es wird angenommen, dass N
Einrichtungstypen existieren, die verschiedene
Abdeckungsradien besitzen. Also wird
versucht Einrichtungen verschiedener Typen
zu positionieren und dabei die totale
Bevölkerung, die Zugriff auf alle Service-
Level besitzt, zu maximieren.
Tab. 2-4: Minimierung der maximalen Fahrtzeiten bzw. Fahrtkosten42
Minimierung der maximalen Reaktionszeit:
Problem Definition
Stochastic queue center Dieses Problem hat das Ziel die maximale
Reaktionszeit zu jedem Nachfragepunkt im
Bezug auf die zu positionierende Einrichtung
zu minimieren.
Tab. 2-5: Minimierung der maximalen Reaktionszeit43
41 Vgl. zu dieser Tabell Brandeau (1989), S. 661. 42 Vgl. zu dieser Tabelle Brandeau (1989), S. 661-662. 43 Vgl. zu dieser Tabelle Brandeau (1989), S. 662.
15
Maximierung der minimalen oder durchschnittlichen Fahrtzeit bzw. Fahrtkosten (beinhaltet die Positionierung von negativ konnotierten Einrichtungen):
Problem Definition
Obnoxious facility (oder antimedian) Es wird eine einzelne Einrichtung in einem
Netzwerk positioniert, um die
durchschnittliche Distanz zwischen der
Einrichtung und einem Bereich von diskreten
Nachfragepunkten zu maximieren.
Distant point (oder anticenter) Das Ziel dieses Problems ist die
Maximierung der minimalen Distanz
zwischen Einrichtung und Nachfragepunkten.
Tab. 2-6: Maximierung der minimalen oder durchschnittlichen Fahrtzeit bzw. Fahrtkosten44
Probleme mit anderen Zielen:
Problem Definition
Lorentz measure Das Ziel ist einzelne Einrichtung zu
positionieren und dabei eine Messung der
Gleichheit, basierend auf den Distanzen
zwischen den Kunden und der Einrichtung, zu
minimieren.
Vororoi partitioning problem Hier ist es das Ziel p Einrichtungen so zu
positionieren, dass die Service-Bereiche der
Einrichtungen möglichst gleich sind.
Condorcet point (or voting measure) Es wird eine Position für eine einzelne
Einrichtung gesucht, die am nächsten an der
absoluten Mehrheit der Kunden ist.
Cent-dian (or medi-center) Dieses Problem stellt eine Kombination aus
Center und Median Problemen dar.
Multi-criteria facility location Es wird eine Einrichtungen positioniert, um
mehrere Zielsetzungen zu optimieren
(Erstellungskosten, variable Servicekosten,
abgedeckte Nachfrage, durchschnittliche
44 Vgl. zu dieser Tabelle Brandeau (1989), S. 662-663.
16
Fahrtzeit)
General competitive location Das Ziel ist Einrichtungen zu positionieren,
die mit existierenden Einrichtungen um die
Abdeckung der Nachfrage konkurrieren.
Hotelling's problem Es sind zwei konkurrierende Einrichtungen in
einem Bereich mit kontinuierlich gleicher
Nachfrage zu positionieren.
Price-sensitive demand problem Eine Einrichtung wird in einem Netzwerk mit
diskreter Nachfrage, die abhängig von
Einrichtungen ist, positioniert, um den
Gewinn oder das Gemeinwohl zu maximieren.
Uncapacitated (Competitive) Facility
Location Problem (UFLP) Es wird der erwartete Gewinn des
Unternehmens maximiert, indem eine
Einrichtung in einem bestimmten Bereich (mit
Wettbewerb) positioniert wird.
Tab. 2-7: Standortprobleme mit anderen Zielen45
3. Maximal Covering Location Problem
3.1 Charakteristika des MCLP
3.1.1 Eingliederung in die Standortprobleme
Neben den Grundmodellen p-Median und p-Center gibt es, wie im vorigen Kapitel
beschrieben, die Gruppe der Covering Probleme.46 In diese Gruppe der
Überdeckungsprobleme lässt sich das MCLP eingliedern.
Ein sehr traditionelles Standortproblem, welches seit den Anfängen der Standortplanung
sehr intensiv studiert wurde, ist das Covering Location Problem. In einem Covering
Location Problem wird nach einer Lösung gesucht, um eine Teilmenge der Kunden mit
der Verfolgung von verschiedenen Zielen abzudecken. Dieses Covering Location
Problem beinhaltet vor allem das in Kapitel 2.3 beschriebene Location Set Covering
Problem und das in diesem Kapitel definierte Maximal Covering Location Problem.47
45 Vgl. zu dieser Tabelle Brandeau (1989), S. 663-664 und Benati (2003), S. 43. 46 Vgl. zu diesem und folgenden Satz Hale (2003), S. 21. 47 Vgl. zu diesem Absatz Davari (2013), S. 68.
17
Der Typ des MCLP's ist normalerweise eng mit der Entscheidung über den Standort-
Bereich X verbunden. Dabei lassen sich drei typische Typen des MCLP's unterscheiden.
Zum einen das Discrete MCLP, in dem X ein diskreter Bereich ist, woraus resultiert,
dass die Position der potenziellen Einrichtungen im Vorhinein identifiziert werden
muss. Zusätzlich ist festzuhalten, dass bei der Positionierung eines Standorts der
Standort-Bereich X als Komplement des Nachfrage-Bereichs N aufgefasst werden kann,
falls ein Standort, der keinen Nachfrage-Punkt abdeckt, mit null Gewichtung zu N
hinzugefügt wird. Zur Vereinfachung wird in diskreten Problemen X auch öfter mit N
gleichgesetzt.
Des Weiteren ist das Planar MCLP aufzuführen, in dem X = 𝑟 gesetzt wird, wobei 𝑟
einen Euklidischen-Bereich darstellt. Der dritte und letzte Typ des MCLP's ist das
Network MCLP, auf welches im folgenden Kapitel intensiv eingegangen wird.48
3.1.2 Definition des MCLP
Das Maximal Covering Location Problem ist ein Ansatz zur Standortoptimierung, bei
dem die Standorte einer gegebenen Anzahl von Einrichtungen so geplant werden, dass
die Abdeckung der Nachfrage der verschiedenen Nachfragepunkte maximiert wird. 49
Um die Abdeckung messen zu können wird von einer maximalen Service-Distanz "S"
bzw. von einem Abdeckungsradius ausgegangen, in der die Nachfrage eines
potenziellen Kunden von dem Unternehmen abgedeckt wird.50 Das bedeutet, dass die
Nachfrage eines potenziellen Kunden abgedeckt ist, falls die Distanz zwischen der
Position der Nachfrage und des potenziellen Standorts den Abdeckungsradius nicht
überschreitet.51 Wenn alle Nutzer am Rand des Abdeckungsradius der neu
positionierten Einrichtung liegen, ist demnach das schlechteste Szenario des MCLP's
eingetreten.52
Um das Ziel, die Maximierung der Anzahl der durch die positionierte Einrichtung
abgedeckten Kunden, welche innerhalb der Service-Distanz liegen, zu erreichen, wird
48 Vgl. zu diesem Absatz Berman (2010), S. 1677. 49 Vgl. zu diesem Satz Church (1974), S. 103. 50 Vgl. zu diesem Satz Church (1974), S. 101. 51 Vgl. zu diesem Satz Berman (2009), S. 30. 52 Vgl. zu diesem Satz Church (1974), S. 101.
18
die Funktion z = ∑ 𝑎 𝑦∈ maximiert. Die zugehörigen Nebenbedingungen dieser
Funktion lauten:
1. ∑ 𝑥∈ ≥ 𝑦 für alle 𝑖 ∈ 𝐼 2. ∑ 𝑥∈ = 𝑃
3. 𝑥 =(0,1) für alle 𝑗 ∈ 𝐽 4. 𝑦 =(0,1) für alle 𝑖 ∈ 𝐼 Es wird also mit der Zielfunktion versucht die Summe der Produkte aus der Anzahl der
Menschen, die an einem Punkt i von der Einrichtung abgedeckt werden (𝑎 ) und der
Binärzahl 𝑦 , welche angibt ob dieser Nachfragepunkt von einer Einrichtung abgedeckt
wird (𝑦 = 1) oder nicht (𝑦 = 1), zu maximieren. Die erste Nebenbedingung gibt an,
dass die Summe der Binärzahl 𝑥 , wobei 𝑥 angibt ob eine Einrichtung innerhalb einer
maximalen Service-Distanz zu einem Standort j zugeordnet ist (𝑥 = 1) oder nicht
(𝑥 = 0), größer oder gleich der zuvor erläuterten Binärzahl 𝑦 sein muss. Des Weiteren
stellt die zweite Formel die Bedingung auf, dass die Summe von 𝑥 , egal ob die Distanz
innerhalb der Service-Distanz liegt oder nicht, gleich der Anzahl der zu
positionierenden Einrichtungen (P) sein soll. Die beiden letzten Nebenbedingungen
setzen noch einmal fest, dass die beide Variablen 𝑥 und 𝑦 nur die Werte 0 oder 1
annehmen können (Binärzahl). Das beschriebene Problem lässt sich durch den
Austausch der Variablen auch entgegengesetzt formulieren, indem man die Anzahl der
Menschen, die nicht in der maximalen Service-Distanz abgedeckt werden, minimiert.
Hierbei wird lediglich die Variable 𝑦 negiert (𝑦 ) und die erste Nebenbedingung
abgeändert zu: ∑ 𝑥∈ + 𝑦 ≥ 1. 53
3.2 Techniken zur Lösung der Probleme
Um das zuvor erläuterte Maximal Covering Location Problem optimal lösen zu können,
bedarf es verschiedener heuristischer Methoden und der Linearen Programmierung.54
53 Vgl. zu diesem Absatz Church (1974), S. 103-105. 54 Vgl. zu diesem und folgenden Satz Xia (2009), S. 747.
19
3.2.1 Heuristische Methoden
Effiziente heuristische Methoden sind unter anderem die Modelle Greedy Adding (GA),
Tabu Search (TS) und Simulated Annealing (SA), welche im Folgenden erläutert
werden.55
Das TS Verfahren erforscht einen Teil des Lösungsraums durch wiederholtes Prüfen
aller Bereiche der aktuellen Lösung und bewegt diese zum besten Bezirk, in dem die
Nachfrage optimal abgedeckt wird, auch wenn es zur Verschlechterung der Zielfunktion
führt. Dieser Ansatz versucht zu vermeiden, dass man in einem lokalen Optimum
gefangen ist. Um dieses zu verhindern, werden die Knoten eines Netzwerks in eine
Tabu-Liste eingefügt, welche kontinuierlich aktualisiert wird. Darüber hinaus können
im Tabu Search mehrere flexible Kriterien, wie beispielsweise Ehrgeiz und
Erweiterungen, Verwendung finden.56 Eine weitere zu betrachtende Heuristik nennt sich
Greedy Adding (GA) Algorithmus und beginnt in einem Bereich, in dem noch keine
Einrichtungen positioniert wurden. Unter der Aufgabe, die maximale Abdeckung für p
zu positionierende Einrichtungen unter einer gegebenen Service-Distanz zu erreichen,
wird zu dem ausgewählten Bereich die Einrichtung hinzugefügt, die zu diesem
Zeitpunkt den größten Anteil der Bevölkerung abdeckt. Für die zweite zu
positionierende Einrichtung wird nach dem gleichen Muster vorgegangen und die
Einrichtung gewählt, welche den größten Anteil abdeckt und nicht von dem ersten
Betrieb abgedeckt wird. Dieses Vorgehen wird solange wiederholt bis alle p
Einrichtungen positioniert sind oder die gesamte Bevölkerung in diesem Bereich
abgedeckt ist. Der GA Algorithmus entfernt eine Einrichtung jedoch nie aus dem
bestimmten Bereich. Für den Algorithmus ist festzuhalten, dass eine optimale Lösung
nur für die Positionierung einer einzelnen Einrichtung gewährleistet ist. Sobald p größer
als eins ist, kann die optimale Lösung nicht mehr garantiert werden. Die Erweiterung
des GA Algorithmus, der GAS Algorithmus (Greedy Adding with Sustitutions), verläuft
nach dem gleichen Schema wie der GA Algorithmus, wobei nun auch Einrichtungen
umpositioniert werden können.57
55 Vgl. zu diesem Satz Xia (2009), S. 747 und Colomé (2003), S. 126-127. 56 Vgl. zu diesem Absatz Colomé (2003), S. 127 und Berman (2001), S. 644. 57 Vgl. zu diesem Absatz Church (1974), S. 105-106.
20
Eine weitere Heuristik zur Lösung des MCLP's nennt sich Simulated Annealing und ist
eine populäre stochastische Methode. Sie wird effizient genutzt, um viele große und
komplizierte Probleme aus der realen Welt zu lösen. Die spezielle Charakteristik des SA
verhindert, dass eine zu positionierende Einrichtung in einem lokalen Optimum
feststeckt, da man schlechte Antworten mit dynamischer Wahrscheinlichkeit erlaubt.
Die Tatsache, dass schlechte Lösungen akzeptiert werden resultiert aus der Funktion des
SA, welche sich auf die Temperatur bezieht. In diesem Fall ist die Funktion jedoch auf
die Wahrscheinlichkeit der Verschlechterung bezogen und befasst sich nicht mit der
wahren Temperatur. Diese ist durch die Anzahl der Iterationen eine monotone Funktion
und reduziert somit die Wahrscheinlichkeit der Akzeptanz im ganzen Algorithmus.58
Zusammenfassend lässt sich zu den verschiedenen heuristischen Methoden festhalten,
dass der GA Algorithmus relativ gute Ergebnisse innerhalb von kurzer Zeit liefern kann
und der effiziente SA Algorithmus meistens die beste Lösung von allen aufgelisteten
Modellen liefert.59
3.2.2 Lineare Programmierung
Auch die Lineare Programmierung wird zur Bearbeitung des MCLP's benutzt und bringt
dabei optimale Lösungen, die weit verbreitet sind, hervor. Im Bezug auf das zweite
Problem des MCLP's aus Kapitel 3.1.1, in dem das Ziel verfolgt wird die Anzahl der
Menschen, die nicht in der maximalen Service-Distanz abgedeckt werden, zu
minimieren, dürfen die Variablen 𝑥 und 𝑦 nicht negativ sein anstatt null oder eins. In
einer optimalen Lösung der Linearen Programmierung ist die Variable 𝑥 nie größer als
eins, außer die Nachfrage ist vollständig abgedeckt. Auch wenn ein 𝑥 in der optimalen
Lösung größer als eins ist, kann es ohne Verletzung der ersten Nebenbedingung aus
Kapitel 3.1.1 reduziert werden. Folglich kann diese Reduzierung die Zunahme eines
anderen 𝑥 in der zweiten Nebenbedingung aus Kapitel 3.1.1, dass die Summe der
Einrichtungen gleich p ist, bedeuten. Daraus folgt die Erlaubnis ein 𝑦 zu verringern,
was wiederum ausschlaggebend für die Verringerung des gesamten Ziels ist. Diese
Tatsache widerspricht der Annahme von Optimalität. Um das MCLP demzufolge mit
58 Vgl. zu diesem Absatz Zarandi (2013), S. 713 und Berman (2001), S. 644. 59 Vgl. zu diesem Satz Xia (2009), S. 747.
21
Hilfe der Linearen Programmierung optimal lösen zu können, bedarf es folgender
Bedingungen: 0 ≤ 𝑥 ≤ 1 𝑓ü𝑟 𝑎𝑙𝑙𝑒 𝑗 ∈ 𝐽 𝑢𝑛𝑑 0 ≤ 𝑦 ≤ 1 𝑓ü𝑟 𝑎𝑙𝑙𝑒 𝑖 ∈ 𝐼. Wenn die Lineare Programmierung benutzt wird und jedoch die vollständige
Abdeckung der Nachfrage nicht möglich ist, lässt sich die optimale Lösung in 2 Fällen
formulieren:
Fall 1: Alle: 𝑥 ,𝑦 = (0,1), wird als all-integer answer bezeichnet;
Fall 2: Es gibt 𝑥 's, die minimal sind, welches als fractional answer bezeichnet wird.
Falls die Lineare Programmierung wie im ersten Fall dargestellt die Lösung
hervorbringt, dass alle 𝑥 ,𝑦 = (0,1) sind, ist die optimale Lösung des MCLP's erreicht.
Wenn die Lineare Programmierung andernfalls die Lösung des zweiten Falls darstellt,
ist die optimale Lösung nicht so durchführbar, wie ein Problem mit Nullen und Einsen
(zero-one problem). Um diese optimalen Lösungen der Linearen Programmierung im
Bezug auf das MCLP zu erhalten, lässt sich ein Mathematical Programming System
(MPS) benutzen. 60
Falls bei einem linearen Programm der zuvor beschriebene zweite Fall (fractional
answer) eintritt, gibt es zwei Lösungstechniken. Auf der einen Seite lässt sich das
Problem durch die method of inspection und auf der anderen Seite durch das Branch
and Bound Verfahren lösen. Die method of inspection zeigt, dass es in einem Problem,
in dem p-Einrichtungen positioniert werden sollen, ausgehend von einer fractional
Lösung für p-Einrichtungen und von einer optimalen Lösung des all-integer Problems
für (p-1)-Einrichtungen, eine optimale Lösung des all-integer Problems (Fall 1)
gefunden werden kann. Passend dazu wird die Methode Branch and Bound zur Lösung
der Linearen Programmierung des zweiten Falls (fractional) benutzt, falls dieser noch
nicht durch die vorher vorgestellte method of inspection gelöst wurde. Durch das
Verzweigen (branching) einer fractional Variable, also durch die Festsetzung von 𝑥
gleich null oder eins, enstehen zwei weitere Probleme der Linearen Programmierung.
Wenn die Lösung beider Probleme 𝑥 = (0,1) beinhaltet, so ist die Lösung optimal,
welche den kleineren Wert der Zielfunktion aufweist. Sollte diese gewählte Lösung des
Problems fractional sein, sind zusätzliche Verzweigungen (branching) und Rechnungen
erforderlich.
60 Vgl. zu diesem Absatz Church (1974), S. 107-108.
22
Tab.3-1: Vergleich der Lösungsverfahren des MCLP's61
In der oben aufgeführten Tabelle 3-1 sind die vorgestellten Lösungsverfahren des
MCLP's durch die Lösung von 27 MCLP's in einem Netzwerk mit 55 Knoten
dargestellt. Es lässt sich erkennen, dass beinahe 80% der Linearen Programmierung als
all-integer optimal beendet wird, da nur 6 von 27 Problemen in der Tabelle als
fractional festgesetzt werden. Außerdem werden nahezu 90% der gesamten Probleme
durch eine Kombination aus der Linearen Programmierung und der method of
inspection gelöst. Beim Branch and Bound Verfahren sind nur etwa 10% der Zeit
notwendig, um fractional Probleme zu lösen. Zusätzlich sind in der Tabelle auch die
Lösungen der MCLP's anhand der beiden vorgestellten heuristischen Methoden GA und
GAS aufgelistet. Die Tabelle zeigt, dass der GA Algorithmus mehr als 60% und der
GAS Algorithmus fast 50% der Zeit nicht optimal ist. Für jede Lösung durch eine
heuristische Methode ist die Abdeckung nicht geringer als 90% des zugehörigen,
optimalen Abdeckungswerts. Daraus folgt, dass die benutzten heuristischen Methoden
in diesem Netzwerk mit 55 Knoten eine nahezu optimale Lösung liefern. Diese gute
Leistung lässt sich dadurch begründen, dass das Netzwerk dieser Probleme einen relativ
dichten Bereich umfasst, welcher üblicherweise durch die Positionierung einer einzigen
Einrichtung abgedeckt werden kann.62
61 Church (1974), S. 110. 62 Vgl. zu diesem Absatz Church (1974), S. 110-111.
23
3.3 Erweiterungen zum MCLP
Durch eine umfassende Literaturrecherche wird deutlich, dass weitere Varianten und
Erweiterungen des MCLP's immer mehr von Interesse sind.63 Im Folgenden werde ich
eine Auswahl von verschiedenen Varianten des MCLP's vorstellen und kurz erläutern:
Gradual Covering Problem: In dieser Erweiterung des MCLP's werden zwei Radien
𝑟 und 𝑟 definiert. Falls die Distanz zwischen einem Nachfragepunkt und einer
Einrichtung kleiner als 𝑟 ist, so ist diese Position der Nachfrage vollkommen
abgedeckt. Wenn umgekehrt die Distanz zwischen dem Nachfragepunkt und der
Einrichtung 𝑟 überschreitet, so ist diese Position der Nachfrage nicht abgedeckt.
Zwischen diesen beiden Radien nimmt die Abdeckung entweder linear im Bezug auf die
Distanz oder schrittweise durch eine Funktion ab.64 Das Gradual Covering Problem
lässt sich durch einen Branch and Bound Algorithmus effizient lösen und bearbeitet
dabei mit Hilfe eines Computers Probleme mit bis zu 10000 Nachfragepunkten
innerhalb von fünf Minuten.65
Maximal Covering Model with negative weights: In dieser Variante können die
Gewichte der Einrichtungen in einem Netzwerk auch negativ sein. Beispielsweise ist
dies der Fall, wenn Nachfragepunkte unbeliebt sind und die Einbeziehung in den
Bereich der Abdeckung der Einrichtung nachteilig wäre. Dieses Problem wird am
besten durch das Vorgehen Simulated Annealing gelöst.66
Dynamic Maximal Covering Location Problem: Diese Erweiterung des MCLP's
behandelt im Gegensatz zu dem klassischen MCLP auch die Anzahl der zu
positionierenden Einrichtungen in jeder Periode. Es werden also auch die einzelnen
Parameter der Funktion dieses dynamischen MCLP's an die Behandlung von einzelnen
Perioden angepasst. Um das vorliegende Problem zu lösen, wird auch hier das
Simulated Annealing benutzt.67
63 Vgl. zu diesem Satz Zarandi (2013), S. 712. 64 Vgl. zu diesem Absatz Drezner (2004), S. 841. 65 Vgl. zu diesem Satz Drezner (2004), S. 854. 66 Vgl. zu diesem Absatz Berman (2009), S. 30-31. 67 Vgl. zu diesem Absatz Zarandi (2013), S. 710-712.
24
Maximal Covering Location Problem with Mandatory Closeness Constraints: Bei
diesem Problem wird, wie beim MCLP, eine fixe Anzahl an Einrichtungen so
positioniert, dass die Abdeckung der Nachfrage der potenziellen Kunden innerhalb einer
Service-Distanz S maximiert wird. Jedoch wird hierbei eine verbindliche Abdeckung
innerhalb einer Distanz von T(T>S) eingehalten. Das Maximal Covering Location
Problem with Mandatory Closeness Constraints bemüht sich eine möglichst große
Anzahl an Kunden innerhalb der Service-Distanz zu haben und gleichzeitig, dass
niemand weiter entfernt ist als T(T>S) zu der nächst gelegenen Einrichtung des
Unternehmens. Um diese Erweiterung des MCLP's zu lösen, werden die gleichen
Lösungsverfahren wie beim klassischen MCLP eingesetzt.68
Quadratic Maximal Covering Location Problem (QMCLP): Die quadratische Version
des MCLP's versucht die optimale Positionierung von Einrichtungen durch eine
maximale Abdeckung der Nachfrage der Knoten und auch der Wege innerhalb des
Netzwerks zu gewährleisten. Wie in den vorigen Kapiteln erläutert, ist zur Lösung des
allgemeinen MCLP's die Benutzung einer heuristischen Methode vonnöten. Diese
Erkenntnis wird auch im QMCLP aufgegriffen und zur Lösung dieses Problems ein
neuer Greedy Algorithmus entwickelt, der Greedy paired adding heuristic (GPAH).
Dieser GPAH Algorithmus selektiert die Einrichtungen paarweise, da keine partielle
Abdeckung auf den Wegen in dem Netzwerk vorhanden ist.69
Minimum Covering Location Problem with Distance Constraints (MCLPDC): Mit einer
fixen Anzahl an zu positionierenden Einrichtungen wird bei diesem Ansatz die Anzahl
der Menschen, welche durch die Einrichtung abgedeckt werden und sich somit
innerhalb des vorher bestimmten Abdeckungsradius befinden, minimiert. Falls mehr als
eine Einrichtung positioniert werden soll, wird durch bestimmte Grenzen verhindert,
dass die Einrichtungen alle an der gleichen Position errichtet werden. Als Beispiel für
ein MCLPDC ist die Positionierung eines Atomreaktors zu nennen, da die Bevölkerung,
die in einem bestimmten Radius zu dem Reaktor angesiedelt ist, durchaus in einer
gefährlichen Umgebung lebt. Um das Problem zu lösen, können auch hier verschiedene
68 Vgl. zu diesem Absatz Church (1974), S. 103. 69 Vgl. zu diesem Absatz Erdemir (2008), S. 612-613.
25
heuristische Methoden benutzt werden, wobei in diesem Fall Tabu Search das beste
Verfahren darstellt.70
Anti-Covering Location Problem (ACLP): Das ACLP versucht die Positionierung der
Standorte so zu maximieren, dass keine zwei der zu positionierenden Einrichtungen
innerhalb einer vorher bestimmten Distanz liegen. Im Gegensatz zu dem zuvor
erläuterten MCLPDC ist die Anzahl der Einrichtungen, die positioniert werden sollen,
nicht fix. Die Methode lässt es zu, dass so viele Einrichtungen wie möglich positioniert
werden, solange sie nicht die vorher bestimmten Grenzen verletzen. Das ACLP kann
erfolgreich durch bestimmte Heuristiken gelöst werden.71
Maximal Expected Covering Location Problem (MEXCLP): Im MEXCLP wird eine
Einrichtung optimal positioniert, indem die erwartete Abdeckung der Nachfrage
maximiert wird, unter Berücksichtigung der Möglichkeit, dass eine Einrichtung nicht
verfügbar sein kann bzw. geschlossen ist. Auch diese Erweiterung des MCLP's lässt
sich mithilfe von heuristischen Methoden lösen.72
Maximal covering location problem with price decision for revenue maximization in a
competitive environment: In dieser Erweiterung des MCLP's werden bei der
Positionierung von Einrichtungen auch Entscheidungen über den Preis mit einbezogen,
um den Gewinn in einem Bereich mit intensivem Wettbewerb zu maximieren. Durch
die sorgfältige Prüfung der Beziehung des MCLP's zu unterschiedlichen Preisen,
entsteht ein vollständiger Lösungsansatz.73
Maximal covering location problem with backup-coverage: Falls in diesem Problem die
Nachfrage durch eine Einrichtung nicht abgedeckt wird, gibt es eine so gennante zweite
Abdeckung (backup-coverage), die versucht die nicht abgedeckte Nachfrage zu decken.
Das Konzept des backup-coverage wird vorgestellt als eine Basis, in der die Abdeckung
der Nachfrage davor geschützt wird sich mit der Zeit zu verändern.74
70 Vgl. zu diesem Absatz Berman (2008), S. 357, 372. 71 Vgl. zu diesem Absatz Berman (2008), S. 357, 362. 72 Vgl. zu diesem Absatz Dolan (1989), S. 277. 73 Vgl. zu diesem Absatz Vanhaverbeke (2009), S. 555. 74 Vgl. zu diesem Absatz ReVelle (1986), S. 1434.
26
4. Forschungsagenda
4.1 Offene Punkte der Modelle der Standortplanung
Ein wichtiges Ziel der Standortplanung befasst sich, wie in den vorigen Kapitel
beschrieben, mit der Abdeckung der Nachfrage eines ausgewählten Bereichs
(coverage). Anhand des dritten Kapitels lässt sich erkennen, dass es eine Vielzahl von
Thematiken gibt, welche im Bereich der Covering Probleme anzusiedeln sind. Trotz
dieser zunehmenden Popularität des coverage-Ziels gibt es Zweifel darüber, ob die
grundlegenden Annahmen dieses Bereichs auch wirklich als realistisch eingestuft
werden können. Diese Zweifel werden im Folgenden an drei Hauptaussagen erläutert.
Zum einen wird häufig von der all or nothing coverage gesprochen, in der jeder
Nachfragepunkt, der innerhalb des Abdeckungsradius einer Einrichtung liegt,
vollkommen abgedeckt wird und jeder Nachfragepunkt, der sich außerhalb dieses
Abdeckungsradius befindet, nicht abgedeckt wird. Wenn man jedoch beispielhaft davon
ausgeht, dass man ein Netzwerk von Supermärkten in einer bestimmten Region mit
einem Abdeckungsradius von 1,5 Meilen positionieren will, so ist es schwer vorstellbar,
dass die Nachfrage der Kunden, welche 1,49 Meilen von der Einrichtung entfernt sind,
vollkommen abgedeckt wird und Kunden, die 1,51 Meilen entfernt sind, den
Supermarkt niemals besuchen. Weiterhin gibt es den Ansatz der individual coverage, in
dem die Abdeckung eines Nachfragepunktes abhängig von der Nähe zu der
nächstgelegenen, einzelnen Einrichtung ist. Hierbei hat schon die Einrichtung, die nach
der nächstgelegenen Einrichtung folgt, keinen Einfluss mehr auf die Abdeckung der
Nachfrage. Ein Beispiel hierzu wäre ein Netzwerk, welches sich dadurch charakterisiert,
dass ein Kunde, der drei Supermärkte innerhalb von zwei Meilen erreicht, jedoch keinen
Supermarkt innerhalb von 1,5 Meilen erreicht, eine schlechtere Abdeckung seiner
Nachfrage besitzt, als ein Kunde, der einen einzelnen Supermarkt innerhalb von 1,5
Meilen erreicht. Durch dieses Beispiel lässt sich erkennen, dass die individual coverage
an manchen Stellen ebenfalls nicht sonderlich realitätsnah ist. Auch der dritte Ansatz
des fixed coverage radius stellt keine vollkommen realistische Thematik dar. Dieser
Ansatz besagt, dass der Abdeckungsradius R, der durch die maximale Distanz festsetzt,
ob die Nachfrage eines Kunde abgedeckt wird oder nicht, keine Entscheidungsvariable
darstellt und von äußeren Einflüssen bestimmt wird. Die angesprochenen Zweifel, die
auch dieser Ansatz mit sich bringt, werden dadurch deutlich, dass im Beispiel ein
27
Abdeckungsradius von 1,5 Meilen, welcher hier fix festgesetzt wird, in manchen Fällen
regulierbar sein kann. Beispielsweise besitzen größere oder attraktivere Einrichtungen
auch größere Handelsbereiche. Folglich kann in diesen Fällen der Abdeckungsradius,
im Gegensatz zu dem Ansatz des fixed coverage radius, auch zu einer
Entscheidungsvariable werden.75
Zusätzlich bestehen weitere Schwierigkeiten der in der Arbeit vorgestellten
Standortmodelle darin, dass die Entscheidungen, welche mit Hilfe der Modelle über den
Standort von Einrichtungen getroffen werden, kostspielig und schwierig rückgängig zu
machen sind und sich die daraus resultierenden Auswirkungen über einen langen
Zeitraum erstrecken.76 Außerdem können die Parameter Kosten, Nachfrage und
Entfernungen, die für die Lösung von Standortproblemen relevant sind, während der
Entscheidungsphase stark schwanken. Auch diese aufgeführten Aspekte legen dar, dass
die Standortplanung mit ihren vielen unterschiedlichen Modellen durchaus Lücken bzw.
Ungenauigkeiten aufweist, welche die Lösung von Standortproblemen erschweren.
4.2 Forschungsansätze zur Vervollständigung der Modelle
Die drei unter anderem betrachteten Ansätze all or nothing coverage, individual
coverage und fixed coverage radius aus dem vorigen Kapitel weisen alle gewisse
Lücken im Bezug auf eine realistische Anwendung auf. Ein realistischeres Modell der
all or nothing coverage würde einen stufenweisen Rückgang der Dichte des
Kaufverhaltens mit einbeziehen. Diese Abnahme könnte man der Funktion der Distanz
zu der positionierten Einrichtung beifügen. Um den ersten Ansatz der all or nothing
coverage nun durch eine realistischere Annahme zu ersetzen, wird beispielsweise im
gradual cover model eine allgemeine Abdeckungs-Funktion (coverage function)
herangezogen, welche den Anteil der abgedeckten Nachfrage im Verhältnis zu einer
bestimmten Distanz von der Einrichtung aus darstellt. Außerdem wächst die
beschriebene Abdeckungs-Funktion nicht im Verhältnis zu der Distanz. Es lässt sich
festhalten, dass diese Funktion, welche dem Ansatz des all or nothing coverage
entgegenwirkt, eine Verbindung zwischen den Problemen des coverage-Bereichs und
75 Vgl. zu diesem Abschnitt Berman (2010), S. 1676. 76 Vgl. zu diesem und folgendem Satz Snyder (2006), S. 537.
28
anderen, klassischen Standortproblemen, wie dem p-Median Problem oder dem UFLP,
darstellt.77
Bei der zweiten Annahme, bei der von einer individual coverage ausgegangen wird,
wäre es ein fundierterer Ansatz, wenn jede Einrichtung in einer bestimmten Distanz zu
den potenziellen Kunden eine Auswirkung auf das Einkaufsverhalten jener Kunden
hätte. Dieser Ansatz des individual coverage wird im cooperative cover model durch
einen Mechanismus ersetzt, indem alle Einrichtungen zur Abdeckung der Nachfrage
jedes Kunden beitragen. Dieses wird dadurch erreicht, dass die Abdeckung als Signal
gesehen wird, welches von den Einrichtungen übertragen wird und mit zunehmender
Distanz geringer wird. Das Signal, das bei jedem Nachfragepunkt empfangen wird, ist
die Ansammlung der Übermittlungen von allen Einrichtungen. Falls nun die Stärke des
Signals an einem Nachfragepunkt eine gewisse Grenze überschreitet, so wird dieser
Punkt abgedeckt und andernfalls nicht.78
Die dritte zuvor aufgeführte Annahme, die von einem fixed coverage radius ausgeht,
wäre optimaler wenn eine Mischung aus kleineren Einrichtungen in bestimmten
Bereichen und größeren Einrichtungen in anderen Bereichen errichtet werden würde.
Um diesen Ansatz zu ersetzen, ist im variable radius model ein bestimmtes Budget
gegeben, mit dem Einrichtungen von unterschiedlichen Typen positioniert werden
können und dabei teurere Einrichtungen einen größeren Abdeckungsradius aufweisen.
Es wird also nicht mehr nur die Position, an der die Einrichtung positioniert werden
soll, betrachtet, sondern auch der Aspekt verfolgt, was für ein Typ einer Einrichtung
errichtet werden soll.79
Zusätzlich ist es in Zukunft notwendig, dass effiziente heuristische Algorithmen
entwickelt werden, welche Lösungen für Standortprobleme mit mehreren Zielsetzungen
identifizieren.80 Methoden, die die Qualität einer Lösung für Standortprobleme
feststellen, sind ebenfalls von großer Bedeutung für die Standortplanung und wären für
die Zukunft wichtig, um bestimmte Schwierigkeiten zu vermeiden.
77 Vgl. zu diesem Abschnitt Berman (2010), S. 1676. 78 Vgl. zu diesem Abschnitt Berman (2010), S. 1676. 79 Vgl. zu diesem Abschnitt Berman (2010), S. 1676. 80 Vgl. zu diesem und folgendem Satz Drezner (2004), S. 110.
29
5. Fazit
Wie die Literaturrecherche und die daraus resultierende Übersicht zeigt, weist die
Thematik der Standortplanung eine Vielzahl von unterschiedlichen Modellen auf, die
ungleiche Ziele verfolgen und vor allem zu verschiedenen Ergebnissen führen. Die
vorgestellten Ansätze des p-Median, p-Center und Covering, welche als Grundlage für
andere Probleme angesehen werden können, dienen zum besseren Verständnis und
geben einen allgemeinen Überblick über die Standortprobleme. Jedoch umfassen diese
nicht die komplette Anzahl der Probleme und lassen gewisse Aspekte in den
Lösungsmodellen unbeachtet.
Ein Fokus der Arbeit liegt auf der Darstellung des populären MCLP's, welches in
Kapitel 3 einschließlich mehrerer Erweiterungen erläutert wird. Auch wenn die
verschiedenen Erweiterungen des MCLP's einige Aspekte behandeln, auf die das
klassische Maximal Covering Location Problem nicht eingeht, weisen auch diese
Sonderfälle des MCLP's gewisse Lücken in ihren Ansätzen auf. Durch eine besondere
Konzentration auf bestimmte Einflussfaktoren, wie Entscheidungen über den Preis, die
Einbeziehung von negativen Einflüssen oder ob eine Einrichtung noch aktiv ist,
vernachlässigen die meisten der vorgestellten Erweiterungen wiederum andere Aspekte,
die für die Positionierung von Einrichtungen durchaus relevant sind. Dennoch stellt das
MCLP, das erstmals 1974 durch Church und ReVelle formuliert wurde, ein
erfolgreiches Modell dar, welches großen Anspruch findet und immer wieder durch
neue Zusätze erweitert bzw. angepasst wird.
Die Literatur zu den verschiedenen Standortproblemen und besonders die Literatur über
das Maximal Covering Location Problem und den davon abgeleiteten Erweiterungen
wächst in den letzten Jahren kontinuierlich. Alleine die Tatsache, dass in dieser Arbeit
ungefähr die Hälfte aller zitierten Artikel in den letzten 10-15 Jahren veröffentlicht
wurde, verdeutlicht das große Interesse an neuen Entwicklungen im Bereich der
Standortplanung mit Fokus auf dem MCLP. Jedoch ist der größte Teil der Literatur, der
sich mit den Modellen zur Standortplanung befasst, nicht auf einen spezifischen
Anwendungsbereich konzentriert, sondern beschäftigt sich vielmehr mit der
Formulierung von neuen Vorgehensweisen und der Modifizierung von existierenden
Modellen, die viele potenzielle Anwendungsbereiche besitzen. Außerdem wird versucht
effiziente Lösungstechniken für existierende oder neu formulierte Modelle zu finden.
Wie in Kapitel 4 beschrieben, weisen einige Ansätze der Standortplanung Lücken auf,
30
welche nur bedingt geschlossen werden können. Unter anderem die Einbeziehung von
bereits existierender Konkurrenz lässt die meisten Modelle auf Probleme stoßen und
führt dazu, dass besonders unter diesen Voraussetzungen kein einheitliches Ergebnis
erreicht wird.
Auf der Suche nach relevanten Artikeln im Bereich der Standortplanung erhält man eine
Vielfalt von wichtiger Literatur, die einen guten Überblick über die verschiedenen
Probleme und Modelle liefert. Jedoch beziehen sich viele der gefundenen Artikel auf zu
spezielle Fälle und sind dadurch nicht unbedingt für eine Übersicht der
Standortprobleme geeignet. Trotz der Quantität der Literatur und dem damit
verbundenen Aufkommen an neuen Modellen, sind einige Unsicherheiten und
Einflussfaktoren wohl auch in Zukunft nur schwer mit einzuberechnen.
31
Literaturverzeichnis
Benati (2003)
Stefano Benati: An Improved Branch & Bound Method for the Uncapacitated
Competitive Location Problem. In: Annals of Operations Research. 1-4, Jg. 122,
2003, S. 43-58
Berman, Drezner, Krass (2010)
Oded Berman, Zvi Drezner, Dmitry Krass: Generalized Coverage: New
Developments in Covering Location Models. In: Computers & Operations
Research. Nr. 10, Jg. 37, 2010, S. 1675-1687
Berman, Drezner, Wesolowsky (2009)
Oded Berman, Zvi Drezner, George O. Wesolowsky: The Maximal Covering
Problem with Some Negative Weights. In: Geographical Analysis. Nr. 1, Jg. 41,
2009, S. 30-42
Berman, Drezner, Wesolowsky (2001)
Oded Berman, Z. V. Drezner, George O. Wesolowsky: Location of Facilities on a
Network with Groups of Demand Points. In: IIE Transactions. Nr. 8, Jg. 33, 2001,
S. 637-648
Berman, Huang (2008)
Oded Berman, Rongbing Huang: The Minimum Weighted Covering Location
Problem with Distance Constraints. In: Computers & Operations Research. Nr. 2,
Jg. 35, 2008, S. 356-372
Berman, Simchi Levi (1990)
Oded Berman, David Simchi Levi: Conditional Location Problems on Networks.
In: Transportation Science. Nr. 1, Jg. 24, 1990, S. 77-78
32
Brandeau, Chiu (1989)
M. L. Brandeau, Samuel S. Chiu: An Overview of Representative Problems in
Location Research. In: Management Science. Nr. 6, Jg. 35, 1989, S. 645-674
Church, ReVelle (1974)
R. Church, C. ReVelle: The Maximal Covering Location Problem. In: Papers of the
Regional Science Association. Nr. 1, Jg. 32, 1974, S. 101-118
Church (2003)
Richard L. Church: Cobra: A New Formulation of the Classic p-Median Location
Problem. In: Annals of Operations Research. 1-4, Jg. 122, 2003, S. 103-120
Colomé, Lourenco, Serra (2003)
Rosa Colomé, Helena R. Lourenco, Daniel Serra: A New Chance-Constrained
Maximum Capture Location Problem. In: Annals of Operations Research. 1-4, Jg.
122, 2003, S. 121-139
Davari, Fazel Zarandi, Burhan Turksen (2013)
Soheil Davari, Mohammad H. Fazel Zarandi, I. Burhan Turksen: A Greedy
Variable Neighborhood Search Heuristic for the Maximal Covering Location
Problem with Fuzzy Coverage Radii. In: Knowledge-Based Systems. Nr. 43, Jg. 41,
2013, S. 68-76
Dolan, Krishnamurthy (1989)
June M. Dolan, Nirup N. Krishnamurthy: The Maximal Expected Covering
Location Problem: Revisited. In: Transportation Science. Nr. 4, Jg. 23, 1989, S.
277-287
Drezner, Hamacher (2004)
Z. Drezner, H.W Hamacher: Facility Location: Applications and Theory. 2004
33
Drezner, Wesolowsky, Drezner (2004)
Zvi Drezner, George O. Wesolowsky, Tammy Drezner: The Gradual Covering
Problem. In: Naval Research Logistics. Nr. 6, Jg. 51, 2004, S. 841-855
Erdemir u. a. (2008)
Elif T. Erdemir, Rajan Batta, Seth Spielman, Peter A. Rogerson, Alan Blatt, Marie
Flanigan: Location Coverage Models with Demand Originating from Nodes and
Paths: Application to Cellular Network Design. In: European Journal of
Operational Research. Nr. 3, Jg. 190, 2008, S. 610-632
Francis, Lowe (1983)
Richard L. Francis, Timothy J. Lowe: Location on Networks: A Survey. Part I: The
p-Center and p-Median Problems. In: Management Science. Nr. 4, Jg. 29, 1983, S.
482-497
Ghosh, MacLafferty (1987)
Avijit Ghosh, Sara MacLafferty: Location Strategies for Retail and Service Firms.
1. Aufl., Lexington Mass 1987
Hakimi (1964)
S. L. Hakimi: Optimum Locations of Switching Centers and the Absolute Centers
and Medians of a Graph. In: Operations Research. Nr. 3, Jg. 12, 1964, S. 450-459
Hale, Moberg (2003)
Trevor S. Hale, Christopher R. Moberg: Location Science Research: A Review. In:
Annals of Operations Research. 1-4, Jg. 123, 2003, S. 21-35
Kaveh, Esfahani (2012)
A. Kaveh, H. N. Esfahani: Hybrid Harmony Search for Conditional P-Median
Problems. In: International Journal of Civil Engineering. Nr. 1, Jg. 10, 2012, S. 32-
36
34
Minieka (1977)
Edward Minieka: The Centers and Medians of a Graph. In: Operations Research.
Nr. 4, Jg. 25, 1977, S. 641-650
Minieka (1980)
Edward Minieka: Conditional Centers and Medians of a Graph. In: Networks. Nr.
3, Jg. 10, 1980, S. 265-272
Peeters, Richard, Thisse (1985)
Dominique Peeters, Denis Richard, Jacques F. Thisse: The Minisum and Minimax
Location Problems Revisited. In: Operations Research. Nr. 6, Jg. 33, 1985, S. 1251-
1265
ReVelle (1986)
Charles ReVelle: Concepts and Applications of Backup Coverage. In: Management
Science. Nr. 11, Jg. 32, 1986, S. 1434-1444
Snyder (2006)
Lawrence V. Snyder: Facility Location Under Uncertainty: A Review. In: IIE
Transactions. Nr. 7, Jg. 38, 2006, S. 537-554
Swain, ReVelle, Bergman (1971)
Ralph Swain, Charles ReVelle, Lawrence Bergman: The Location of Emergency
Service Facilities. In: Operations Research. Nr. 6, Jg. 19, 1971, S. 1363-1373
Vanhaverbeke (2009)
Lieselot Vanhaverbeke: Maximal Covering Location Problem with Price Decision
for Revenue Maximization in a Competitive Environment. In: OR Spectrum. Nr. 3,
Jg. 31, 2009, S. 555-571
35
Xia u. a. (2009)
Li Xia, Ming Xie, Weida Xu, Jinyan Shao, Wenjun Yin, Jin Dong: An Empirical
Comparison of Five Efficient Heuristics for Maximal Covering Location Problems,
S. 747-753
Zarandi, Davari, Sisakht (2013)
Mohammad H. F. Zarandi, Soheil Davari, Seyyed A. H. Sisakht: The Large-Scale
Dynamic Maximal Covering Location Problem. In: Mathematical & Computer
Modelling. 3/4, Jg. 57, 2013, S. 710-719
