Kurs:Mathematische Modellbildung/Themen/2024-25 Wintersemester/Thema 3

Evakuierung einer Großstadt am Beispiel von Honolulu

Gruppenteilnehmer

Laura Walsemann
Alexander Scherer
Behcet Öztürk

Einleitung und Zielsetzung

Die Evakuierung von Großstädten spielt im Hinblick auf die zunehmende Bedrohung durch Naturkatastrophen, insbesondere Überschwemmungen, eine wichtige Rolle im Hinblick auf Katastrophenmanagement und Städtesicherheit. Ausgelöst werden viele dieser Katastrophen unteranderem durch die zunehmend schwerwiegenden Folgen des Klimawandels. Hierzu möchten wir eine Modellierung einer Evakuierung einer Großstadt am Beispiel von Honolulu, Hawaii, darstellen.Die Gefahr von Überschwemmungen, sei es durch steigende Meeresspiegel, extreme Regenfälle oder Sturmfluten stellen eine erhebliche Bedrohung für die Lebenssicherheit der Bevölkerung dar. Vor diesem Hintergrund ist es von größter Bedeutung, eine durchdachte und schnell umsetzbare Evakuierungsstrategie zu entwickeln. Ein entscheidender Aspekt wird die modellhafte Berechnung der verfügbaren Ressourcen, wie etwa die Länge und Breite der Straßen, die verschiedenen Evakuierungsrouten und sowie die gleichzeitig bewegende Bevölkerungsdichte.

Zuordnung zu den Nachhaltigkeitszielen

Abb.1: SDG 9: Industrie, Innovation und Infrastruktur

SDG 9: Industrie, Innovation und Infrastruktur

Eine Grundlage um eine effektive Evakuierung zu gewährleisten, sind die Kombination innovativer Technologien und Infrastrukturplanung. Eine vorausschauend geplante Infrastruktur kann dazu betragen eine Evakuierung zu optimieren. Eine Modernisierung der Infrastruktur, besonders in Entwicklungsländern, schafft eine nachhaltige Grundlage, um besonders ärmere Länder auf folgenschwere Naturkatastrophen vorzubereiten und eine schnelle und effektive Evakuierung im Notfall überhaupt möglich zu machen.

Abb.2: SDG 11: Nachhaltige Städte und Gemeinden

SDG 11: Nachhaltige Städte und Gemeinden

Eng verknüpft mit SDG 9 bezüglich des Katastrophenschutzes ist SDG 11: Nachhaltige Städte und Gemeinden. Ein konkretes Unterziel ist hierbei die Reduktion der Anzahl der Menschen, die von Naturkatastrophen betroffen sind. Um dies zu erreichen wird in den Städtebau und Forschung für die Stadt in der Zukunft investiert. Hier zeigt sich der starke Bezug zu SDG 9: je ausgebauter das Infrastrukturnetz einer Stadt, desto besser und effektiver kann auf eine mögliche Katastrophe reagiert werden und mehr Menschen gerettet werden. Dies gilt von der kleinen Gemeinde bis hin zu einer Großstadt wie Honolulu. Besonders im Hinblick darauf, dass sich Honolulu auf einer Insel befindet, ist dort besonders wichtig eine ausgebaute und moderne Infrastruktur zu besitzen, da es keinerlei Ausweichmöglichkeiten auf umliegendes Festland gibt. Ein weiteres Unterziel ist der Ausbau des kommunalen Kompetenzen des Katatstrophenschutzes. Zu einer Evakuierung einer Stadt gehört nicht nur eine ausgebaute Infrastruktur, sondern auch die Möglichkeiten einer Gemeinde oder Stadt die Evakuierung überhaupt einzuleiten, zeitnah zu reagieren, zu organiseren und möglichst schnell auszuführen. All dies kann dazu beitragen eine nachhaltige Stadt zu erschaffen und zu halten.

Abb.3: SDG 13: Maßnahmen zum Klimaschutz

SDG 13: Maßnahmen zum Klimaschutz

Somit eins der wichtigsten Ziele, um die Ursache für Naturkatastrophen zu minimieren, sind Maßnahmen zum Klimaschutz und somit unteranderen gegen den Klimaerwärmung zu ergreifen. Der Klimawandel führt vermehrt zu Extremwetterbedingungen, wie auch Überschwemmungen oder Tsunamis. Aus diesem Grund ist es dringend notwendig den Klimawandel gemeinsam mit Hilfe verschiedener Maßnahmen zu stoppen. Der globale Temperaturanstieg soll auf 1,5 Grad Celsius begrenzt werden, sowie globale Treibhausgas-Neutralität zur Jahrhundertmitte erreicht werden. So kann auch nachhaltig und präventiv dafür gesorgt werden, dass sich die Ursachen für Naturkatastrophen minimieren. Des Weiteren sollen die politischen Rahmenbedingungen in Schwellen- und Entwicklungsländern für den Klimaschutz verbessert werden. So kann dafür gesorgt werden, dass im Falle eines Notfalls möglichst die besten Rahmenbedingungen existieren, um die Menschen in der Stadt zu retten und zu versorgen.

Annahmen & Datenerhebung

Für die Modellierung der Evakuierung werden folgende Daten benötigt:

Bevölkerungsdichte
Breite und Länge der Straßen
Größen der Evakuierungszonen / möglichen Notunterkünfte
Geschwindigkeit der Personen

Datenerhebung:

Straßenlängen: Google Maps (Abstandsmessung)
Straßenbreiten: Infrastrukturbericht der Stadt Honolulu

Befinden sich auf einer festgelegten Strecke mehrere Straßen mit unterschiedlichen Breiten, so wurde für die gesamte Strecke angenommen, dass diese den Durchschnitt der Straßenbreiten besitzt.

Anzahl der Straßenspuren: Google Earth

Aufgrund von Messfehlern können die Daten leichte Abweichungen zur Realität enthalten.

Bevölkerungsdichte:

127.270 Einwohner im relevanten Stadtteil (homogene Bevölkerungsdichte) ^[1]
92 Kreuzungen, jeweils 1.383 Personen

Die Anzahl der Personen pro Kreuzung wird folgendermaßen berechnet:

$\frac{127270}{92} \approx 1.383$

Es befinden sich dementsprechend 1.383 Personen an jeder Kreuzung.

Da im Modell mit 10 Kreuzungen gerechnet wird:

$10 \times 1.383 = 13.830$

Im Modell wird also mit einer Gesamtbevölkerung von 13.830 gerechnet. Hierbei handelt es sich um ca. 10 Prozent der Gesamtbevölkerung.

$\frac{r e d u z i e r t e B e v o e l k e r u n g}{G e s a m t b e v o e l k e r u n g} = \frac{13830}{127270} \approx 0.10$

Geschwindigkeit der Personen:

Die Geschwindigkeit der Personen wurde von Internetquellen entnommen ^[2]. Darin sind verschiedene Laufgeschwindigkeiten von 8 km/h bis 22 km/h angegeben. Als Mittel wurden 16 km/h als Geschwindigkeit gewählt, was einem Tempo von 4,4 m/s entspricht.

Evakuierungszonen:

Gebäude: Flächenmessung, Verfügbarkeit des benötigten Platzes pro Person & Kapazitäten
Platzbedarf: 45 m² pro Person (inkl. Versorgungseinrichtungen)^[3]^[4]^[5]^[6]

Ziel	d1	d2	d3	d4	d5	d6	d7	d8	d9	d10
Gesamtfläche (m²)	104130	142830	9585	64035	8640	17640	135180	2655	47160	90495
benötigte Fläche pro Mensch (m²)	45	45	45	45	45	45	45	45	45	45
Personen (Kapazität)	2314	3174	213	1423	192	392	3004	59	1048	2011

Freiflächen: Google Earth-Messung, realistische Belegung

Verwendete Programme

Geogebra
Octave
OpenOffice

Modellierungszyklus I (Mathematische Hintergründe)

Erklären des allgemeinen Prinzips

Die Schülerinnen und Schüler werden mit einer Textaufgabe konfrontiert, bei der sie einen Stadtteil der Stadt Honolulu evakuieren sollen. Dabei wird das System als Netzwerk aus Knoten und Kanten modelliert (vgl. Abb.4). Da es sich hierbei um ein stark vereinfachtes Modell handelt, konnten keine Annahmen über echte Werte getroffen werden. Aus diesem Grund wurde mit Beispielwerten verfahren.

Knoten: Kreuzungen der Stadt
Kanten: Straßen, die die Kreuzungen verbinden

Ablauf der Evakuierung

Zeitschritte:

Zu t = 0 befinden sich alle Personen an ihren Startknoten.
Zu t = 1 bewegen sich die Personen zur nächstgelegenen Kreuzung.

Der Prozess wiederholt sich, bis alle Personen ihr Ziel erreicht haben. Das System ist beendet, wenn alle Knoten A,B,C,D keine Personen mehr beherbergen und am Ziel angekommen sind.

Kapazitätsbegrenzung:

Jede Straße hat eine maximale Anzahl an Personen, die sie pro Zeitschritt aufnehmen kann.
Sind mehr Personen am Startknoten als die Straße zulässt, bleiben die übrigen Personen dort und bewegen sich erst im nächsten Zeitschritt weiter.

Gabelungen (mehrere mögliche Wege) an Punkt A:

Personen bevorzugen die präferierte Route nach D, diese wird von allen genutzt bis sie voll ist, danach wird die alternative Strecke nach B genutzt

Allgemeines Rechenverfahren

Aufbau der Tabelle

Die Kopfzeile enthält alle Knoten inklusive des Zielknotens
Links steht der am weitesten entfernte Knoten, rechts das Ziel
Links neben den Knoten befindet sich eine Spalte für die Zeitschritte (t)

Startbedingungen (t = 0)

Die Zeile unter der Kopfzeile zeigt die Anzahl der Personen an jedem Knoten zu Beginn

Übergang von t = 0 zu t = 1

Personen bewegen sich zum nächsten Knoten gemäß der Kapazität der Straßen

mögliche Beispielrechnung von Schülern
t	A	B	D	C	Ziel
0	1000	10000	200	750	0
-	-300 zu D	-500 zu C	-200 zu C	-750 zu Ziel	+750 von C
-	-400 zu B	+400 von A	+300 von A	+200 von D
-				+500 von B
1	300	9900	300	700	750
-	-300 zu D	-500 zu C	-300 zu C	-700 zu Ziel	+700 von C
-	-0 zu B	+0 von A	+300 von A	+ 300 von C
-				+500 von B
2	0	9400	300	800	1450
...	...	...	...	...	...
n	0	0	0	0	11950

Knoten A (Startpunkt)

Bewegung zu D:

Berechne das Minimum aus Personen an A und Kapazität KAD
Falls Personen an A > KAD, können nur KAD Personen weiterziehen
Falls Personen an A ≤ KAD, ziehen alle weiter

Bewegung zu B:

Min( $A_{R e s t}$ ,KAB)
Danach ergibt sich der neue Wert für $A_{t = 1}$

Knoten B

Berechnung der abgehenden Personen: Min(B, KBC)
Berechnung der ankommenden Personen: Min(A, KAB)
Neuer Wert für B bei t = 1:

$B_{t = 1} = B_{t = 0} - \min (B, K B C) + \min (A, K A B)$

Knoten D

Berechnung der abgehenden Personen: $\min (D, K D C)$

Berechnung der ankommenden Personen: $\min (A, K A D)$
Neuer Wert für D bei t = 1:

$D_{t = 1} = D_{t = 0} - \min (D, K D C) + \min (A, K A D)$

Knoten C (Zusammenfluss von B und D)

Personen aus zwei Richtungen (B und D) strömen nach C
Berechnung der abgehenden Personen: $\min (C, K C Z i e l)$
Berechnung der ankommenden Personen: $\min (D, K D C) + \min (B, K B C)$
Neuer Wert für C bei t = 1:

$C_{t = 1} = C_{t = 0} - \min (C, K C Z i e l) + \min (D, K D C) + \min (B, K B C)$

Zielknoten

Personen gelangen nur aus C zum Ziel
Berechnung der ankommenden Personen: $\min (C, K C Z i e l)$
Neuer Wert für das Ziel bei t = 1:

$Z i e l_{t = 1} = Z i e l_{t = 0} + \min (C, K C Z i e l)$

Modellierungszyklus I (Programmieren Sek I und Sek II)

OpenOffice (Sek I)

Das Programmieren in OpenOffice lässt sich im Informatikunterricht der Mittelstufe bearbeiten. Wie in dem händisch berechneten Verfahren befindet sich auf der linken Seite die Spalte, welche die jeweiligen Zeitpunkte angibt. Anschließend findet man die Punkte A,B,D,C,Ziel. Nach dem Punkt A muss man jedoch weitere Nebenrechnungen einbauen, da man von Punkt A aus mehrere Wege gehen kann und den Reiseverlauf der Menschen definieren muss. Am Zahlenbeispiel von oben ergeben sich folgende Einträge in OpenOffice:

.

Oktave (Sek II)

Das Programmieren in Octave lässt sich im Informatikunterricht der Oberstufe bearbeiten.

% Definition der Knoten und Kanten
knoten = {"A", "B", "C", "D", "Ziel"};
kapazitaet = struct("A_B", 400, "A_D", 300, "B_C", 500, "D_C", 600, "C_Ziel", 1000);
start_population = struct("A", 1000, "B", 10000, "C", 750, "D", 200, "Ziel", 0);

% Initialisierung der Variablen
zeit = 0;
fluesse = struct("A_B", 0, "A_D", 0, "B_C", 0, "D_C", 0, "C_Ziel", 0);

disp("Start der Evakuierung...");
while start_population.A + start_population.B + start_population.D + start_population.C > 0
    zeit += 1;
    printf("Zeit %d:\n", zeit);
    printf("  Population: A = %d, B = %d, D = %d, C = %d, Ziel = %d\n", ...
           start_population.A, start_population.B, start_population.D, start_population.C, start_population.Ziel);

    % Flüsse von A zu B und D
    fluesse.A_D = min(kapazitaet.A_B, start_population.A);
    fluesse.A_B = min(kapazitaet.A_D, start_population.A - fluesse.A_D);

    % Aktualisierung von A, B und D
    start_population.A -= (fluesse.A_B + fluesse.A_D);
    start_population.B += fluesse.A_B;
    start_population.D += fluesse.A_D;

    % Flüsse von B und D zu C
    fluesse.B_C = min(kapazitaet.B_C, start_population.B);
    fluesse.D_C = min(kapazitaet.D_C, start_population.D);

    % Aktualisierung von B, D und C
    start_population.B -= fluesse.B_C;
    start_population.D -= fluesse.D_C;
    start_population.C += (fluesse.B_C + fluesse.D_C);

    % Fluss von C zum Ziel
    fluesse.C_Ziel = min(kapazitaet.C_Ziel, start_population.C);

    % Aktualisierung von C und Ziel
    start_population.C -= fluesse.C_Ziel;
    start_population.Ziel += fluesse.C_Ziel;

    % Flüsse anzeigen
    printf("  Flüsse: A->B = %d, A->D = %d, B->C = %d, D->C = %d, C->Ziel = %d\n", ...
           fluesse.A_B, fluesse.A_D, fluesse.B_C, fluesse.D_C, fluesse.C_Ziel);
end

% Gesamte Evakuierungszeit ausgeben
printf("Gesamte Evakuierungszeit: %d Zeiteinheiten\n", zeit);

Dabei simuliert der Code eine Evakuierung von Menschen aus mehreren Ausgangspunkten über verschiedene Wege, die eine begrenzte Kapazität haben, bis sie alle am Ziel angekommen sind. Es gibt mehrere Knotenpunkte, an denen sich Menschen sammeln oder durch die sie transportiert werden. Jeder Knoten hat zu Beginn eine bestimmte Anzahl von Menschen. In jedem Zeitschritt wird berechnet, wie viele Menschen sich auf den Wegen zwischen den Knoten bewegen können. Sobald alle Menschen das Ziel erreicht haben, endet die Simulation und die Zeit wird ausgegeben.

Vor-/Nachteile

Ein Vorteil dieser Rechenmethode ist, dass sie sehr einfach händisch zu berechnen ist. Als nachteilig stellt sich heraus, dass bei größeren Szenarien der Rechenaufwand enorm wächst, da man jede einzelne Bewegung der Personen berücksichtigen muss. Programmiert birgt dieses Verfahren ebenfalls Herausforderungen, da man in OpenOffice keine Schleifen programmieren kann. Mit zunehmender Bevölkerung und Größe der Karte nimmt die Matrix bedeutend zu. Die Vergrößerung des Programms in Octave nimmt aufgrund der Möglichkeit, Schleifen einzusetzen, in nicht so extremen Ausmaß zu.

Modellierungszyklus II

Im Modellierungszyklus 2 wird auf Uniniveau das Gütertransportverfahren angewendet. Ziel ist es von Ortschaften s₁,.., s_m (s = source) Güter, in unserem Fall Menschen, in Zieldestinationen d₁,...,d_n (d = Destination) zu transportieren. ^[7]^[8]

Mathematisierung

Das Ziel ist es die passende Anzahl an Personen x_ij zu finden, die von s_i nach d_j (i = 1,...,m;j = 1,...,n) transportiert werden sollen, wobei für jeden Transportweg bestimmte Transportkosten c_ij anfallen. Diese Kosten entsprechen der insgesamt benötigten Transportzeit. Die Gesamttransportzeit wird durch die folgende Formel beschrieben:

\sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{i j} x_{i j}

Ziel des Verfahren ist es, diese Gesamtzeit zu minimieren.

Bestimmung der Transportkosten

Um die Transportzeitkosten zu bestimmen, wurden folgende Überlegungen gemacht:

Angenommen wird, dass jeder Mensch eine Rechteckfläche mit den Maßen 2[m] * 1[m] zur Fortbewegung benötigt. Dies wird umgerechnet in "Menscheneinheit M", wobei eine Menscheneinheit eine Breite von 1 Meter und eine Länge von 2 Meter hat. So kann aufgrund der Straßenbreite die Anzahl an Menschen berechnet werden, die sich gleichzeitig nebeneinander fortbewegen können. Dies führt dazu, dass c_ij folgendermaßen dargestellt werden kann:

c_{i j} = \frac{l_{i j}}{v_{i j}}

wobei $l_{i j}$ die Länge der Straße zwischen $s_{i}$ und $d_{j}$ in "Menscheneinheiten" [M] ist, und $v_{i j}$ die Anzahl der Menschen beschreibt, die sich auf der Straße pro Sekunde gleichzeitig fortbewegen können, diese Anzahl ist abhängig von der Breite der Straße, umgerechnet in Menschenlängen und der Länge der Menschen:

$v_{i, j} = \frac{Breite der Straße [M] \times Länge der Menschen [M]}{1 [s]}$

Die Einheiten dieser Geschwindigkeit der Menschenmasse sind:

$[v_{i, j}] = \frac{M \cdot M}{s} = \frac{M^{2}}{s}$

Länge der Menschen bedeutet, wie viele Menschenlängen sich pro Sekunde fortbewegen. Diese ist also direkt von der Geschwindigkeit der Personen abhängig und setzt sich folgendermaßen zusammen:

$G e s c h w i n d i g k e i t [m / s] = \frac{Länge der Menschen [m]}{1 [s]}$

$G e s c h w i n d i g k e i t [m / s] \times 1 [s] = Länge der Menschen [m]$

$Länge der Menschen [M] = \frac{Länge der Menschen [m]}{2}$

Durch das Einsetzen von $c_{i j}$ in die Kostenfunktion ergibt sich:

$\sum_{i = 1}^{m} \sum_{j = 1}^{n} \frac{l_{i, j}}{v_{i, j}} x_{i, j} .$

Für die Einheiten der Kostenfunktion gilt: $\sum_{i = 1}^{m} \sum_{j = 1}^{n} \frac{l_{i, j} [M]}{v_{i, j} [M^{2} / s]} x_{i, j} [M] = s$

Matrixdarstellung

In einer Matrix werden die Quellen und die Zieldestinationen dargestellt mit den jeweiligen Transportkosten für jede mögliche Route von s₁,.., s_m nach d₁,...,d_n und die Anzahl der bewegten Menschen wird eingetragen.

\begin{matrix} d_{1} & d_{2} & \dots & d_{n} \\ s_{1} & \begin{matrix} c_{11} & x_{11} \end{matrix} & \begin{matrix} c_{12} & x_{12} \end{matrix} & \dots & \begin{matrix} c_{1 n} & x_{1 n} \end{matrix} \\ s_{2} & \begin{matrix} c_{21} & x_{21} \end{matrix} & \begin{matrix} c_{22} & x_{22} \end{matrix} & \dots & \begin{matrix} c_{2 n} & x_{2 n} \end{matrix} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ s_{m} & \begin{matrix} c_{m 1} & x_{m 1} \end{matrix} & \begin{matrix} c_{m 2} & x_{m 2} \end{matrix} & \dots & \begin{matrix} c_{m n} & x_{m n} \end{matrix} \end{matrix}

Methode der Nordwestecke

Die Methode der Nordwestecke beginnt in der obersten linken Ecke (Zeile 1, Spalte 1, Nordwest-Ecke) als Startpunkt. Dort werden die Transportmengen zugeordnet: jede Zelle der Matrix wird von oben links nach unten rechts ausgefüllt. Es wird der Zelle die minimale Menge zugeordnet, die durch das Angebot der Quelle und die Nachfrage der Zieldestination begrenzt ist. Dieser Wert wird in die Zelle eingetragen. Wenn das Angebot in einer Zeile aufgebraucht ist, wird die nächste Zeile betrachtet und der Prozess wiederholt. Bei der Nachfrage wird ebenfalls nach diesem Schema vorgegangen bis alle Angebote und Nachfragen zugeteilt werden. Am Ende erhält man eine erste Lösung für das Transportproblem. Diese Lösung ist nicht unbedingt optimal, aber sie dient als Ausgangsmatrix für weitere Optimierungen. Aus dieser ersten Matrix wird eine erste Gesamttransportzeit berechnet.

Optimierungsverfahren

Das Verfahren mit der Nordwestecke liefert eine Möglichkeit, die benötigte Zeit für die Evakuierung zu bestimmen. Diese gegebene Zeit ist zulässig, jedoch nicht optimal. Um diese Zeit zu optimieren, nimmt man die Nordwestecke mit den Kosten als Startpunkt. Die Werte der Nordwestecke bilden die so genannten Basiswerte und werden markiert (hier durch das B).

\begin{matrix} d_{1} & d_{2} & \dots & d_{n} & a_{i} \\ s_{1} & c_{11} 𝐁 & c_{12} & \dots & c_{1 n} & a_{1} \\ s_{2} & c_{21} 𝐁 & c_{22} 𝐁 & \dots & c_{2 n} & a_{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ s_{m} & c_{m 1} & c_{m 2} & \dots & c_{m n} 𝐁 & a_{m} \\ b_{j} & b_{1} & b_{2} & \dots & b_{n} \end{matrix}

Als ersten Schritt erweitert man die Matrix um die Zeile v_j und Spalte u_i.

\begin{matrix} d_{1} & d_{2} & \dots & d_{n} & a_{i} & u_{i} \\ s_{1} & c_{11} 𝐁 & c_{12} & \dots & c_{1 n} & a_{1} \\ s_{2} & c_{21} 𝐁 & c_{22} 𝐁 & \dots & c_{2 n} & a_{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ s_{m} & c_{m 1} & c_{m 2} & \dots & c_{m n} 𝐁 & a_{m} \\ b_{j} & b_{1} & b_{2} & \dots & b_{n} \\ v_{j} \end{matrix}

Anschließend bestimmt man die Hilfsvariablen, sodass c_ij = u_i + v_j, die in der obigen Matrix bereits dargestellten Kosten darstellen. Für die erste Variable muss man einen beliebigen Wert annehmen, um die anderen Werte ermitteln zu können. In der Regel wird angenommen, dass dieser Wert v_j = 0 ist. Der andere Wert u_i bildet sich aus c_ij - v_j. Es ist jedoch wichtig zu betonen, dass nur das c_ij gewählt wird, welches zu einem markierten Basiswert gehört. Aus diesen beiden Werten lässt sich durch Umstellen von c_ij = u_i + v_j die anderen Werte u_i und v_j berechnen.

\begin{matrix} d_{1} & d_{2} & \dots & d_{n} & a_{i} & u_{i} \\ s_{1} & c_{11} 𝐁 & c_{12} & \dots & c_{1 n} & a_{1} & u_{1} \\ s_{2} & c_{21} 𝐁 & c_{22} 𝐁 & \dots & c_{2 n} & a_{2} & u_{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ s_{m} & c_{m 1} & c_{m 2} & \dots & c_{m n} 𝐁 & a_{m} & u_{m} \\ b_{j} & b_{1} & b_{2} & \dots & b_{n} \\ v_{i} & v_{1} & v_{2} & \dots & v_{n} \end{matrix}

Im nächsten Schritt werden die sogenannten reduzierten Kosten c̄_ij = c_ij - u_i - v_j gebildet. Diese geben an, um wie viel die Gesamtkosten steigen, wenn man eine bestimmte (z.B. ungenutzte) Route mehr nutzt.

\begin{matrix} d_{1} & d_{2} & \dots & d_{n} & a_{i} & u_{i} \\ s_{1} & c_{11} 𝐁 & c_{12} {\overline{c}}_{12} & \dots & c_{1 n} {\overline{c}}_{1 n} & a_{1} & u_{1} \\ s_{2} & c_{21} 𝐁 & c_{22} 𝐁 & \dots & c_{2 n} {\overline{c}}_{2 n} & a_{2} & u_{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ s_{m} & c_{m 1} {\overline{c}}_{m 1} & c_{m 2} {\overline{c}}_{m 2} & \dots & c_{m n} 𝐁 & a_{m} & u_{m} \\ b_{j} & b_{1} & b_{2} & \dots & b_{n} \\ v_{i} & v_{1} & v_{2} & \dots & v_{n} \end{matrix}

Nachdem man alle reduzierten Kosten berechnet hat, bestimmt man, ob alle c̄_ij größer oder gleich 0 sind. Ist das der Fall, ist die Lösung mit der Nordwestecke optimal.
Wenn es jedoch negative c̄_ij gibt, so ist die Matrix nicht optimiert. Um die Optimierung zu starten, wählt man den negativsten Wert. Wenn es mehrere negative Zahlen mit dem gleichen Wert gibt, so kann man sich einen frei wählen.
Nun will man den gewählten negativen Wert erhöhen. Hierfür baut man eine Art Viereck. Dazu setzt man ein +θ an den negativen Wert. Um diese Erhöhung in den Werten darunter und daneben auszugleichen, schreibt man ein -θ an die Zahl. Um ebendiese Erhöhung auszugleichen, schreibt man an die Zahl in der gegenüberliegenden Ecke der negativen Zahl ein +θ. Wichtig ist, dass an allen drei Eckpunkten, mit Ausnahme des negativen Werts, Zahlen stehen, die aus der Basislösung, der Nordwestecke, übernommen wurden. Es dürfen also nicht die reduzierten Kosten c̄_ij gewählt werden. Kann man mit der gewählten negativen Zahl kein solches Viereck bilden, so muss man eine andere nehmen.

\begin{matrix} d_{1} & d_{2} & \dots & d_{n} & a_{i} & u_{i} \\ s_{1} & c_{11} 𝐁 (- θ) & c_{12} (- {\overline{c}}_{12}) & \dots & c_{1 n} {\overline{c}}_{1 n} & a_{1} & u_{1} \\ s_{2} & c_{21} 𝐁 (+ θ) & c_{22} 𝐁 (- θ) & \dots & c_{2 n} {\overline{c}}_{2 n} & a_{2} & u_{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ s_{m} & c_{m 1} {\overline{c}}_{m 1} & c_{m 2} {\overline{c}}_{m 2} & \dots & c_{m n} 𝐁 & a_{m} & u_{m} \\ b_{j} & b_{1} & b_{2} & \dots & b_{n} \\ v_{i} & v_{1} & v_{2} & \dots & v_{n} \end{matrix}

Das Viereck darf auch vergrößert werden, es müssen, mit Ausnahme des negativen Wertes, aber immer die Werte bestehend auf der Basislösung an den Ecken stehen. Bei einem größeren Viereck werden die Werte, die nicht in den Ecken stehen nicht beachtet.
Der Wert von θ ist der Wert der kleinsten Zahl, die mit einem -θ markiert ist.
Nun ersetzt man die negative Zahl mit dem Wert des kleinsten -θ. An dessen vorheriger Stelle steht nun eine 0. Die anderen Zahlen werden entsprechend mit dem θ verrechnet.
Ist dies vollzogen, so hat man die erste Iteration geschafft. Um zu sehen, ob diese Lösung optimal ist, beginnt man mit dem Prozess von neuem und bestimmt erneut die Hilfsvariablen v_j und u_i, bzw. die reduzierten Kosten c̄_ij.
Das Verfahren ist optimiert, wenn keine negativen Werte mehr auftreten. Für die nun optimierten Transportkosten werden die neu bestimmten Basiswerte mit den jeweiligen Kosten multipliziert und aufaddiert.
Sollten noch Nicht-Basiswerte negativ sein und sich kein Viereck - in dessen drei anderen Ecken Basiswerte stehen - bilden lassen, ist das Verfahren für den Startwert v_j = 0 optimiert. Durch Wählen anderer Startpunkte können sich die negativen Zahlen in der weiteren Optimierung auflösen. ^[9]

Evakuierung von Honolulu

In dem betrachteten Abschnitt wurde ein Stadtviertel in Küstennähe ausgewählt ^[10], welches evakuiert wird .Die Quellen wurden regelmäßig über das Stadtviertel verteilt, um eine Evakuierung des gesamten Stadtviertels zu ermöglichen. Weiter auf dem Festland wurden die Destinationen festgelegt, die die Menschen aus ihren verschiedenen Quellen erreichen müssen, um als "evakuiert" zu gelten. Zur besseren Übersichtlichkeit dienen nur ein paar Punkte als Sammelpunkte für die Menschen und es wurde darauf verzichtet alle Kreuzungen der Stadt als Quelle zu nutzen. Die Kapazität der Punkte wurde so berechnet, dass die umliegende Bevölkerungsdichte erhoben wurde und auf den verschieden Quellen und Destinationen komprimiert wurde. Die Destinationen stellen verschiedene Sammelpunkte in der Realität dar, Gebäude mit größerer Kapazität wie zum Beispiel Schulen oder große Flächen wie Parks.

Die Breiten der Straßen haben je nach Anzahl der Spuren unterschiedliche Breiten ^[11] (vgl. Abb. 8):

Straßenspuren und Breiten
Spuren	Breite (m)	Farbe
2	5,4	Schwarz
3	6,7	Blau
4	8,8	Grün
5	10,5	Orange
8	15,9	Pink

Besitzt eine festgelegte Strecke mehrere Straßen, die unterschiedliche Breiten besitzen, so wird mit der Durchschnittsbreite der Straßen gerechnet.

Die Längen und Breiten für die einzelnen Routen lauten wie folgt:

Im Folgenden werden für die Strecke von s₁ zu d₁ die Kosten c_1,1 berechnet. Die Rechnung für die anderen Punkte läuft analog:

$c_{i j} = \frac{l_{i j}}{v_{i j}}$

$l_{1, 1} = 283 m = 141.5 M$

$v_{i, j} = \frac{Breite der Straße [M] \times Länge der Menschen [M]}{1 s}$

$Breite der Straße = 18,9m = 18,9M$

$Länge der Menschen [m] = G e s c h w i n d i g k e i t \frac{[m]}{[s]} \times 1 s$

$Länge der Menschen [M] = \frac{Länge der Menschen [m]}{2}$

$4, 4 \frac{m}{s} \times 1 s = 4, 4 m = 2, 2 M$

$v_{1, 1} = \frac{18,9M \times 2,2M}{1 s} = 41, 58 \frac{M^{2}}{s}$

$c_{1, 1} = \frac{141,5M}{41, 58 \frac{M^{2}}{s}} = 3, 4030784031 \frac{M}{\frac{M^{2}}{s}}$

Die Kosten für die einzelnen Routen lauten:

Werte über Nordwesteckenverfahren

Die Rechnungen für die Evakuierungszeiten wurden sowohl für die Nordwesteckenregel, als auch für die Optimierung in OpenOffice realisiert. Für die Nordwesteckenregel wurden zwei Matrizen gebaut. Einerseits die Kostenmatrix, welche c_ij abbildet, andererseits die Anzahl der Personen x_ij, die die jeweiligen Strecken laufen. Über den Summenprodukt-Befehl wurde die Doppelsumme über OpenOffice realisiert. Als über die Nordwesteckenregel ermittelte Evakuierungszeit wurde ein Wert von 252.184 herausgegeben.

Um diese in Stunden umzurechnen, teilen wir sie durch 3600, um die Sekunden in Stunden umzurechnen: $\frac{252.184}{3600} = 70, 05 Stunden$

Da die Berechnung auf 10 % der Gesamtbevölkerung basiert, multiplizieren wir mit 0,10:

$70, 05 \times 0, 10 = 7, 005 Stunden$

Somit ergibt sich eine endgültige Evakuierungszeit von 7,005 Stunden.

Werte des Optimierungsverfahren

Die beiden Matrizen der Nordwestecke, also die Kosten- und Menschenmatrix wurden für das Optimierungsverfahren zusammengefügt. Weiterhin wurden die Bewegung der Personen markiert und die Matrix um u_i und v_j erweitert. Als Startwert wurde v₁ = 0 gewählt. Im Folgenden dargestellt sind die Matrizen der Nordwestecke und Iterationsschritte.

Die Zeiten in den verschiedenen Iterationen lauten wie folgt:


Schritt	Zeit in Stunden
0	7,00511111
1	6,916972222
2	6,721722222
3	6,66538889
4	6,66538889

Insgesamt hat die Optimierung vier Iterationen gedauert. Die Zeiten für die Evakuierung wurden von 7,005 Stunden auf 6,665 Stunden reduziert. Dadurch, dass es sich bei den beiden Werten um die Summe aller Zeiten handelt, muss man diese noch durch die Anzahl der betrachteten Routen dividieren. Man erhält dadurch den Durchschnitt der Zeit für die Evakuierungszeit der Stadt. Da mit zehn Routen gerechnet wurde, teilt man die 7,005 Stunden und die 6,6665 Stunden durch 10.


Aufsummierte Zeit	7,005 h	6,6665 h
Durchschnittszeit	42,03 min	39,59 min

Man erkennt, dass sich die Zeit von Iteration 3 zu Iteration 4 nicht verbessert. Um zu überprüfen, ob das System somit optimiert ist, führt man einen fünften Schritt, einen Prüfungsschritt durch. Im Prüfungsschritt erkennt man, dass sich keine Vierecke bilden lassen, in dessen Ecke eine negative Zahl steht, mit drei Basiswerten in den anderen Ecken. Somit ist die Optimierung für v₁ = 0 abgeschlossen. Man kann die Optimierung noch weiterführen, indem man für v₁ andere Werte annimmt. Aufgrund der zunehmenden Komplexität wurde darauf verzichtet.

Fazit

Für eine präzisere Berechnung könnten die exakten Daten zur Straßenbreite sowie zu Fahrrad- und Fußwegen berücksichtigt werden.

Auch die Tatsache, dass viele Menschen häufig Autos nutzen, könnte als zusätzlicher Faktor in die Berechnung einfließen, wodurch die Reisegeschwindigkeit erhöht und die Bewegungsfläche vergrößert wird. Eine weitere Verbesserung wäre, die genaue Anzahl der Bewohner pro Straße und Kreuzung zu erfassen und in die Berechnung einzubeziehen. Zusätzlich könnte für jede Kreuzung oder Straße eine separate Berechnung vorgenommen werden, um genauere Ergebnisse zu erzielen.

Als Alternative zum Transportproblem lässt sich das so genannte „Agent-Based-Model“ (ABM) angeben. Dieses ist ein computerbasiertes Transportproblem, welches die Handlungen von einzelnen Handlungsträgern bestimmt. Dieses Modell zielt darauf ab, das Verhalten und den Ausgang von Situationen zu bestimmen, in denen eine Anzahl an Individuen beteiligt ist. Die Entscheidungen werden wahrscheinlichkeitstheoretisch bestimmt.^[12]

Zusammenfassend sind die Werte nah an der Wirklichkeit, wenn man bedenkt, dass in einigen Bereichen mit starken Vereinfachungen gerechnet wurde. Im offiziellen Evakuierungsbericht von Honolulu wurde eine Evakuierungszeit von 28 Minuten berechnet, wobei hier alle Faktoren und Genauigkeiten berücksichtigt wurden. In unserer Modellierung wurde mit einer Geschwindigkeit von $4, 4 \frac{m}{s}$ gerechnet, wobei sich die Menschen zu Fuß fortbewegen. Wäre ein anderes Fortbewegungsmittel gewählt worden, wie zum Beispiel Autos, würden sich die einzelnen Menschen viel schneller fortbewegen und die Evakuierungszeit wurde sich verringern.

Ein weiterer möglicher Grund für eine Verzerrung könnte sein, dass mit der Durchschnittsbreite von Straßen gerechnet wurde, falls sich auf der Strecke Straßenabschnitte unterschiedlicher Breite befinden. Um dies zu vermeiden, könnten die einzelnen Abschnitte nochmals einzeln betrachtet werden.

Quellenverzeichnis

↑ Bevölkerungsanzahl - [1]
↑ Laufgeschwindigkeit - [2]
↑ Kapazität von Gebäude 1 -[3]
↑ Kapazität von Gebäude 2-[4]
↑ Kapazität von Gebäude 3-[5] Kapazität von Gebäude 3
↑ Größe der Notunterkünfte-[6]
↑ John Haigh: Mathematics in Everyday Life, Springer, 2012. - [7]
↑ Gütertransport (Vorlesung Frau Prof. Dr. Hundertmarkt)
↑ Operations Research - [8] Operations Research
↑ Karte der Insel - [9]
↑ Daten der Straßen - [10] Daten der Straßen
↑ Alternativmodel -[11]

[1] Bevölkerungsanzahl - [1]

[2] Laufgeschwindigkeit - [2]

[3] Kapazität von Gebäude 1 -[3]

[4] Kapazität von Gebäude 2-[4]

[5] Kapazität von Gebäude 3-[5] Kapazität von Gebäude 3

[6] Größe der Notunterkünfte-[6]

[7] John Haigh: Mathematics in Everyday Life, Springer, 2012. - [7]

[8] Gütertransport (Vorlesung Frau Prof. Dr. Hundertmarkt)

[9] Operations Research - [8] Operations Research

[10] Karte der Insel - [9]

[11] Daten der Straßen - [10] Daten der Straßen

[12] Alternativmodel -[11]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Kurs:Mathematische Modellbildung/Themen/2024-25 Wintersemester/Thema 3

Inhaltsverzeichnis

Evakuierung einer Großstadt am Beispiel von Honolulu

Gruppenteilnehmer

Einleitung und Zielsetzung

Zuordnung zu den Nachhaltigkeitszielen