Das Ziel dieser Arbeit ist es, verschiedene Möglichkeiten zur Bestimmung geeigneter Standorte anzugeben, wobei eine Restriktion an den zulässigen Bereich in Form einer linearen Barriere in die Modellierung einbezogen werden soll. Derartige Problemstellungen wurden in der Literatur bereits für 1–Standortprobleme untersucht, jedoch nicht für den Fall, in dem N > 1 neue Standorte gesucht werden. Solche Modelle – und die dazugehörigen Lösungsverfahren – sollen hier hergeleitet und dann so verallgemeinert werden, dass unterschiedliche Abstandsfunktionen verwendet werden könne.
Inhaltsverzeichnis
- Notationen
- 1 Einleitung
- 2 Grundlagen
- 2.1 Abstandsbegriffe
- 2.2 Problemstellung
- 2.3 Vorbetrachtungen
- 2.4 Klassifikationsschema
- 2.5 Beispiele
- 2.5.1 Bergbaufolgelandschaften
- 2.5.2 Recyclingcontainer
- 2.5.3 Halle-Silberhöhe
- 3 1-Standort-Medianprobleme ohne Restriktionen
- 3.1 Probleme mit Manhattan-Entfernung
- 3.2 Probleme mit Tschebyscheff-Entfernung
- 3.3 Probleme mit quadratischer Euklidischer Entfernung
- 3.4 Probleme mit Euklidischer Entfernung
- 3.4.1 Vorbetrachtungen
- 3.4.2 Das Weiszfeld-Verfahren – Algorithmus 1
- 3.4.3 Zum Abbruchkriterium in Algorithmus 1
- 4 N-Standort-Medianprobleme ohne Restriktionen
- 4.1 Probleme mit Manhattan-Entfernung
- 4.2 Probleme mit Tschebyscheff-Entfernung
- 4.3 Probleme mit quadratischer Euklidischer Entfernung
- 4.4 Probleme mit Euklidischer Entfernung
- 4.4.1 Vorbetrachtungen
- 4.4.2 Verfahren zur approximativen Lösung von N|P|·|d2|Σ – Algorithmus 2
- 4.4.3 Zum Abbruchkriterium in Algorithmus 2
- 5 Die Eigenschaft der konvexen Hülle
- 6 1-Standort-Medianprobleme mit linearer Barriere
- 6.1 Folgerungen aus der Eigenschaft der konvexen Hülle für das 1–Standort-Medianproblem mit linearer Barriere
- 7 N-Standort-Medianprobleme mit linearer Barriere
- 7.1 Folgerungen aus der Eigenschaft der konvexen Hülle für das N-Standort-Medianproblem mit linearer Barriere
- 7.2 Approximative Verfahren zur Lösung von N|P|BL|dBL|Σ
- 7.2.1 Approximative Lösung von N|P|BL|dBL|Σ – Version 1–
- 7.2.2 Approximative Lösung von N|P|BL|dBL|Σ – Version 2–
- 7.3 Exakte Lösung von von 2|P|BL|dBL|Σ·
- 7.3.1 Barriere mit einem Übergang
- 7.3.2 Barriere mit zwei Übergängen
- 8 N-Standort-Medianprobleme mit gemischten Normen und linearer Barriere
- 8.1 Standortprobleme mit unterschiedlichen Abstandsfunktionen in beiden Halbebenen
- 8.1.1 Folgerungen aus der Eigenschaft der konvexen Hülle für das N-Standort-Medianproblem mit linearer Barriere und unterschiedlichen Abstandsfunktionen in beiden Halbebenen
- 8.1.2 Exakte Lösung von von 2|P|BL|dBL|Σ
- 8.1.2.1 Barriere mit einem Übergang
- 8.1.2.2 Barriere mit zwei Übergängen
- 8.2 Standortprobleme mit gemischten Abstandsfunktionen in einer der beiden Halbebenen
- 8.2.1 Folgerungen aus der Eigenschaft der konvexen Hülle für das N-Standort-Medianproblem mit linearer Barriere und gemischten Abstandsfunktionen in einer der beiden Halbebenen
- 8.2.2 Exakte Lösung von von 2|P|BL|dBL|Σ
- 8.2.2.1 Barriere mit einem Übergang
- 8.2.2.2 Barriere mit zwei Übergängen
- 8.1 Standortprobleme mit unterschiedlichen Abstandsfunktionen in beiden Halbebenen
- 9 Zusammenfassung und Ausblick
- Literaturverzeichnis
Zielsetzung & Themen
Diese Masterarbeit zielt darauf ab, verschiedene Methoden zur Bestimmung geeigneter Standorte zu entwickeln, wobei eine lineare Barriere als Restriktion in die Modellierung einbezogen wird. Bestehende Ansätze für 1-Standortprobleme werden dabei auf den Fall von N > 1 neuen Standorten verallgemeinert und für unterschiedliche Abstandsfunktionen erweitert.
- Standortoptimierung unter Berücksichtigung linearer Barrieren (z.B. Flüsse, Autobahnen).
- Verallgemeinerung von 1-Standort- auf N-Standortprobleme.
- Anwendung verschiedener Abstandsfunktionen (Manhattan, Tschebyscheff, Euklidisch).
- Entwicklung approximativer und exakter Lösungsverfahren für Standortprobleme.
- Analyse der Eigenschaften konvexer Hüllen im Kontext von Standortproblemen.
- Praxisnahe Anwendungsbeispiele und Fallstudien.
Auszug aus dem Buch
2 Grundlagen: Abstandsbegriffe und Problemstellung
Um die Entfernung zwischen zwei Standorten beschreiben zu können, ist es hilfreich, zunächst die Begriffe Metrik und Norm einzuführen.
Definition 1
Eine Abbildung d: Rn × Rn → R bezeichnen wir als Metrik, wenn folgende Eigenschaften auf sie zutreffen:
1. ∀x, y ∈ Rn gilt: d(x, y) ≥ 0 ⇔ x = y,
2. ∀x, y ∈ Rn gilt: d(x, y) = d(y, x) und
3. ∀x, y, z ∈ Rn gilt die Dreiecksungleichung: d(x, z) ≤ d(x, y) + d(y, z).
Definition 2
Eine Abbildung || . || : Rn → R heißt Norm, wenn sie folgende Eigenschaften erfüllt:
1. ∀x ≠ 0 gilt: ||x|| ≠ 0,
2. ∀α ∈ R, x ∈ Rn soll die positive Homogenität erfüllt sein: ||αx|| = |α|·||x|| und
3. ∀x, y ∈ Rn soll die Dreiecksungleichung ||x + y|| ≤ ||x|| + ||y|| gelten.
Definition 3
Eine Menge X ⊆ Rn heißt konvex, wenn ∀x, y ∈ X und ∀λ ∈ [0,1] auch λ·x + (1 − λ) · y ∈ X gilt.
Definition 4
Es sei X ⊆ Rn konvex. Eine Funktion f : X → R heißt konvex auf X, wenn ∀x, y ∈ X und ∀λ ∈ [0, 1] f(λ·x + (1 − λ) · y) ≤ λ·f(x) + (1 − λ) · f(y) gilt.
2.2 Problemstellung
Gegeben seien M ≥ 2 vorgegebene Standorte Ex = (Ex1,...,ExM)T∈ (R2)M, charakterisiert durch Punkte in R2. Wir suchen N neue Standorte Neu := (y1,...,yN)T ∈ (R2)N, die zu jedem Standort gemessen an einer durch eine Norm induzierten Metrik d : (Exm, yn) → R den geringsten Abstand hat. Die Distanzen zwischen gegebenen und neuen Standorten sollen die nichtnegativen Gewichte vmn, m∈ M := {1,...,M}, n∈ N := {1, ..., N} tragen, die beispielsweise das Verkehrsaufkommen zwischen den existierenden und den gesuchten neuen Standorten angeben können. Außerdem sollen die Abstände zwischen den neuen Standorten yn, yl, n,l ∈ N minimiert werden, wobei ihre Entfernung mit der Gewichtung wnl ≥ 0 versehen werden soll.
Mögliche Abstandsfunktionen d : (Exm, yn) → R sind
• d1(Exm, yn) = ||Exm - yn||1 = |Exm1 - yn1| + |Exm2 - yn2| (Manhattan-Entfernung),
• d2(Exm, yn) = ||Exm - yn||2 = √(Exm1 - yn1)2 + (Exm2 - yn2)2 (Euklidischer Abstand),
Zusammenfassung der Kapitel
1 Einleitung: Erläutert die wachsende Bedeutung der Standortoptimierung und stellt das Ziel der Arbeit vor: die Entwicklung von Lösungsansätzen für N-Standortprobleme mit linearer Barriere und verschiedenen Abstandsfunktionen.
2 Grundlagen: Führt grundlegende Definitionen wie Metriken, Normen und Konvexität ein und stellt die allgemeine Problemstellung der Standortoptimierung dar, inklusive verschiedener Abstandsfunktionen und Zielfunktionen.
3 1-Standort-Medianprobleme ohne Restriktionen: Beschreibt Lösungsansätze für das Problem, einen einzelnen neuen Standort ohne Barrieren zu finden, unter Verwendung unterschiedlicher Entfernungsfunktionen wie Manhattan, Tschebyscheff und Euklidisch.
4 N-Standort-Medianprobleme ohne Restriktionen: Erweitert die in Kapitel 3 vorgestellten Methoden auf Probleme, bei denen mehrere neue Standorte ohne Barrieren gesucht werden, und entwickelt einen neuen Algorithmus für euklidische Entfernungen.
5 Die Eigenschaft der konvexen Hülle: Bereitet die theoretischen Grundlagen für die Lösung von Problemen mit linearen Barrieren vor, indem sie die Eigenschaft der konvexen Hülle in Bezug auf optimale Standortmengen diskutiert.
6 1-Standort-Medianprobleme mit linearer Barriere: Behandelt die Bestimmung eines einzelnen neuen Standorts unter Berücksichtigung einer linearen Barriere und zeigt, wie dieses restringierte Problem auf unrestringierte Probleme zurückgeführt werden kann.
7 N-Standort-Medianprobleme mit linearer Barriere: Verallgemeinert die in Kapitel 6 vorgestellten Ansätze auf N-Standortprobleme mit linearer Barriere und entwickelt approximative sowie exakte Lösungsverfahren für zwei Standorte mit einem oder zwei Übergängen.
8 N-Standort-Medianprobleme mit gemischten Normen und linearer Barriere: Erweitert die Problemstellung auf gemischte Abstandsfunktionen in den Halbebenen und präsentiert exakte Lösungsansätze für 2-Standortprobleme mit einem oder zwei Übergängen.
9 Zusammenfassung und Ausblick: Fasst die Hauptergebnisse der Arbeit zusammen, insbesondere die entwickelten Algorithmen und die Reduktion restringierter auf unrestringierte Probleme, und gibt Anregungen für zukünftige Forschungsfragen.
Schlüsselwörter
Standortoptimierung, N-Standortproblem, lineare Barriere, Medianproblem, Abstandsfunktionen, Euklidische Entfernung, Manhattan-Entfernung, Tschebyscheff-Entfernung, konvexe Hülle, approximative Verfahren, exakte Lösung, Übergangspunkte, gemischte Normen.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Diese Arbeit befasst sich mit der Entwicklung und Verallgemeinerung von Modellen und Lösungsverfahren für N-Standortprobleme, insbesondere unter Berücksichtigung von Restriktionen in Form von linearen Barrieren.
Was sind die zentralen Themenfelder?
Die zentralen Themenfelder sind die Standortoptimierung, die Modellierung linearer Barrieren (z.B. Flüsse, Autobahnen) mit Übergangspunkten, die Untersuchung verschiedener Abstandsfunktionen und die Entwicklung von Algorithmen zur Lösung dieser komplexen Probleme.
Was ist das primäre Ziel oder die Forschungsfrage?
Das primäre Ziel ist es, Möglichkeiten zur Bestimmung geeigneter Standorte anzugeben, die eine lineare Barriere in die Modellierung einbeziehen, und bestehende 1-Standortprobleme auf N > 1 neue Standorte sowie unterschiedliche Abstandsfunktionen zu verallgemeinern.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt mathematische Modellierung und Optimierungsmethoden, einschließlich Differentialrechnung, um konvexe Zielfunktionen zu minimieren. Es werden sowohl approximative (z.B. Weiszfeld-Verfahren) als auch exakte Algorithmen hergeleitet und angewendet.
Was wird im Hauptteil behandelt?
Der Hauptteil behandelt die Lösungsansätze für 1- und N-Standortprobleme ohne Restriktionen, die Eigenschaft der konvexen Hülle, sowie 1- und N-Standort-Medianprobleme mit linearer Barriere, auch unter Verwendung gemischter Abstandsfunktionen in den Halbebenen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Schlüsselwörter wie Standortoptimierung, N-Standortproblem, lineare Barriere, Medianproblem, Abstandsfunktionen, Euklidische Entfernung, Manhattan-Entfernung, Tschebyscheff-Entfernung, konvexe Hülle, approximative Verfahren, exakte Lösung, Übergangspunkte und gemischte Normen charakterisieren die Arbeit.
Warum ist die Modellierung linearer Barrieren in der Standortoptimierung wichtig?
Lineare Barrieren wie Flüsse oder Autobahnen haben einen großen Einfluss auf Transportwege und Distanzen. Ihre Berücksichtigung in der Modellierung ist entscheidend, um realitätsnahe und optimale Standortentscheidungen zu treffen.
Welche Rolle spielt die Eigenschaft der konvexen Hülle in dieser Arbeit?
Die Eigenschaft der konvexen Hülle ist ein grundlegendes theoretisches Konzept, das es ermöglicht, restringierte Standortprobleme mit linearen Barrieren auf unrestringierte Probleme zurückzuführen, wodurch die Lösungsfindung erheblich vereinfacht wird.
Gibt es eine besondere Herausforderung bei der Lösung von N-Standortproblemen mit Euklidischer Entfernung?
Ja, laut der Einleitung existierten für N-Standortprobleme mit Euklidischer Entfernungsfunktion in der Literatur bisher keine Lösungsvorschläge, weshalb in dieser Arbeit ein spezielles Näherungsverfahren entwickelt wurde.
Welche praktischen Anwendungen werden im Buch als Beispiele genannt?
Als praktische Anwendungsbeispiele werden unter anderem die Standortbestimmung in Bergbaufolgelandschaften, die Platzierung von Recyclingcontainern in einer Stadt und die Planung von Parkplätzen in Stadtteilen wie Halle-Silberhöhe genannt.
- Arbeit zitieren
- Elisabeth Köbis (Autor:in), 2011, N–Standortprobleme mit linearer Barriere, München, GRIN Verlag, https://www.grin.com/document/203629
