Modellierungsthema

Unser Modellierungsproblem behandelt die Fragestellung, inwiefern eine Straßenbahn am effizientesten zwischen Ludwigshafen-Rheingönheim und Speyer gebaut werden kann.

Zwischen diesen beiden Städten befinden sich drei Ortschaften, wovon ein Großteil der Einwohner entweder in Speyer oder Ludwigshafen die Arbeitsstelle hat oder zur Schule geht. Hierbei wollen wir den Weg der Straßenbahn so optimieren, dass einerseits möglichst viele Einwohner eine Haltestelle in Reichweite haben und andererseits die Straßenbahn eine möglichst kurze Strecke zurücklegt.

Mit Hilfe unseres Modellierungsprozesses, wollen wir somit den Fahrweg für bestimmte, als sinnvoll erachtete Parameter, optimal berechnen.

Mögliche einzuholende Daten

Wie viele Einwohner haben die jeweiligen Ortschaften?
Wie viele Häuser/ Haushalte gibt es in den jeweiligen Dörfern?
Wie ist die Infrastruktur?
Wie weit sind die Orte voneinander entfernt?
Wie ist die landschaftliche Beschaffenheit?
Was kostet im Allgemeinen ein Streckenabschnitt einer Straßenbahn?
Wie schnell kann eine Straßenbahn auf verschiedenen Streckenabschnitten fahren?

Ziele

Wegoptimierung und Zeitersparnis des Straßenbahnnetzes
mathematische Modellierung des kürzesten Weges in Anlehnung an den Ameisenalgorithmus
möglichst hohe Effizienz der Straßenbahnlinie
Kostenoptimierung/Kostenminimierung

Softwarenutzung

Ameisenalgorithmus

Der Ameisenalgorithmus, häufig Ant Colony Optimization (ACO) genannt, bezieht sich auf das Phänomen, dass Ameisen einerseits in der Lage sind, den schnellsten Weg zu ihrer Nahrung zu finden, andererseits diesen Weg den anderen Ameisen mitteilen.

Bei der Suche des Futters hinterlassen Ameisen eine Spur, sogenannte Pheromone, wodurch sie ihren Weg zurück zu ihrem Bau wiederfinden und außerdem eine Orientierung für andere Ameisen ihres Volkes darstellen. Wenn eine Ameise nun einen kürzeren Weg findet, ist ihr Duftstoff intensiver, da sie häufiger zwischen der Futterquelle und dem Bau hin und her läuft und kennzeichnet so den anderen Ameisen den schnellsten Weg. Hätte eine Ameise zum Beispiel die Auswahl zwischen zwei Wegen und nicht die Möglichkeit des Ausstoßes von Pheromonen wäre die Wahl des Pfades rein zufällig.

Mit dem Ameisenalgorithmus, lernt der Computer so zu denken wie das Ameisenvolk und findet deshalb schnell einen kurzen Weg. Es gilt daher den Ameisenalgorithmus auf diese Modellierungsaufgabe anzuwenden, um den kürzesten Weg, den die Straßenbahn zurücklegen soll, zu erlangen.

Zuordnung des Themas zu den Nachhaltigkeitszielen der Vereinten Nationen

SDG 9: Industry, Innovation and Infrastructure
- Durch die Straßenbahnlinie findet eine Anbindung an den öffentlichen Nahverkehr statt, wodurch die Infrastruktur ausgebaut wird und die Einwohner schnell und effizient in die umliegenden Städte gelangen.

SDG 11: Sustainable Cities and Communities
- Der Belastung der Städte durch Autos und Lärm, wird mit Hilfe einer schnelle Anbindung der umliegenden Dörfer an den öffentlichen Nahverkehr entgegengewirkt, sodass auch die Einwohner dieser Ortschaften per Straßenbahn zu ihrer Arbeit gelangen können.
SDG 13: Climate Action
- Der Ausstoß von Treibhausgasen wird gesenkt, da die Straßenbahnlinie mit erneuerbaren Energien betrieben werden kann.
SDG 15: Life on Land
- Die Verkehrsbelastung innerhalb der Ortschaften wird verringert.

Niveaustufen

Sekundarstufe I

Den kürzesten Weg durch ausprobieren bzw. nachmessen finden
Daten erheben und tabellarische Datenauswertung von Einwohnerzahlen, Entfernungen und Anzahl der Haltestellen
Daten in ein Tabellenkalkulationsprogramm übertragen, einpflegen und auswerten (z.B. Streckenlängen)
Zu ausgewählten Daten Diagramme erstellen
Erstellen eines Graphen und diesen in in GeoGebra nachbilden (Schienennetz)
geometrische Berechnung durch Anwendung der Trigonometrie bei Dreiecken, sowohl Winkelfunktionen sin, cos, tan, als auch Kosinussatz, Sinussatz und Tangenssatz

Sekundarstufe II

Formulierung als lineares Problem (Regression)
Das Streckennetz mit Hilfe von Funktionen nachbilden
Matrizenrechnung

Universität

kombinatorische Optimierung in Anlehnung an den Ameisenalgorithmus

Modellierungszyklus I

Zielsetzung:

Ziel des ersten Zyklus ist es sich zunächst eines der vier Dörfer vorzunehmen, durch welches die Straßenbahnlinie führt. Dabei sollen genau 5 Haltestellen angefahren werden, dies jedoch in möglichst schnellster Zeit bzw. kürzester Strecke. Diese Informationen sollen aus einer Karte entnommen werden und in einem Tabellenkalkulationsprogramm zu einer Lösung führen. In der Tabelle sollen die Parameter Weglänge sowie Anzahl der Haltestellen betrachtet werden. Dabei hat die Straßenbahnlinie einen festen Start- und Endpunkt.
→ Mögliche Software: Tabellenkalkulation (Excel), Kartendienst (Google Maps)

Ablauf Modellierungszyklus I:

Zu Beginn dieses Zyklus haben wir mit Hilfe von Google Maps potenzielle Haltestellen innerhalb eines Dorfes eingezeichnet, wobei der rote Punkt den Startbahnhof darstellt und der blaue Punkt am Ortsausgang unten rechts das Ende skizziert. Anschließend soll mit Hilfe der Karte eine Skizze erstellt werden. Anhand der beigefügten Tabelle und der Skizze, welche zur Veranschaulichung dient, können dann die Weg- bzw. Streckenlängen abgelesen werden, sodass dadurch der kürzeste Weg bestimmt werden kann. Hierbei sollen die gewählten Wege möglichst nur einmal befahren werden. Die ausgewählten Wege werden anschließend in ein Tabellenkalkulationsprogramm (hier: LibreOffice) übertragen. Dabei muss man durch geschicktes Kombinieren überlegen, welche Strecken mit genau 5 Haltestellen möglich sind. Dies ist bei 11 verschiedenen Möglichkeiten der Fall, was man in der unteren Tabelle erkennen kann. Die Summe über die einzelnen Teilstrecken, um den kürzesten Weg zu ermitteln, wird letztendlich mit Hilfe des Tabellenkalkulationsprogramms mittels Addition der Einzelstrecken berechnet und der günstigste Weg im Streckennetz markiert.

Probleme & Alternativen:

Probleme für reales Modell:
- Nicht alle Haltestellen werden angefahren
- Einige Haltestellen sind besser zu erreichen als andere, da sich manche Haltestellen nicht in unmittelbarer Nähe von Wohngebieten befinden, sondern nur wenige Menschen im Umkreis ansprechen
- Wenn man alle Ortschaften betrachten würde, wäre es mit extrem großer Mühe verbunden, alle Möglichkeiten der Straßenbahnlinie zu berechnen und außerdem könnte man anschließend die Werte der Strecken nicht beliebig ändern

Alternative Berechnung:
- geometrische Berechnung mit Hilfe von Dreiecken, in denen mit vorgegebenen Werten Lösungen gefunden werden können

Alternative für Sekundarstufe II:
- Graphen-/ Streckennetz mit Hilfe von GeoGebra entwickeln (siehe unten)
- Auswerten der Graphen durch Funktionen

Roter Punkt = Startpunkt / Blauer Punkt = mögliche Haltestellen / schwarze Linien = Verbindungsstrecken

Modellierungszyklus II

Zielsetzung:

Das vorrangige Ziel des Modellierungszyklus II ist es, die kürzeste Wegstrecke der Straßenbahn innerhalb jedes einzelnen Ortes und letztendlich die Gesamtstreckenlänge herauszufinden. Dies wird möglich gemacht, indem man zunächst alle Strecken zwischen den einzelnen Haltestellen betrachtet. Dabei werden mit Hilfe eines in Octave geschriebenen Algorithmus die kürzesten Wege berechnet.

Ablauf Modellierungszyklus II:

Übertragen der Situation in mathematische Begriffe:

• Graph bildet Wegmöglichkeiten ab

• Startknoten entspricht Ameisenhaufen bzw. Nest

• Zielknoten spiegelt Futterquelle wider

→ Gesucht ist eine möglichst kurze Ameisenstraße bzw. ein kürzester Weg vom Start- zum Endpunkt im Graphen

→ Mögliche Software: Tabellenkalkulation, GeoGebra, Octave

Weg	Länge in km	Geogebra Streckennetz Neuhofen	Matrix (Octave)	Ergebnis (Octave)	Ergebnis (graphisch)
a	1,4	Abb.1a: Mögliche Haltestellen in Neuhofen	Abb.1b: Matrix des Streckennetzes von Neuhofen sowie die dazugehörige Permutationsmatrix	Abb.1c: kürzester Weg
b	1,1				Abb.1d: Ergebnis Neuhofen Geogebra
c	1,07
d	1
e	0,458
f	0,624
g	0,68
h	0,538
i	0,355
j	0,496
k	0,556
l	0,825
m	0,605
n	0,91

Weg	Länge in km	Geogebra Streckennetz Waldsee	Matrix (Octave)	Ergebnis (Octave)	Ergebnis (graphisch)
a	1,14	Abb.2a: Mögliche Haltestellen in Waldsee	Abb.2b: Matrix des Streckennetzes von Waldsee sowie die dazugehörige Permutationsmatrix	Abb.2c: kürzester Weg	Visualisierung des Ergebnisses
b	0,822
c	0,793
d	0,817
e	0,575
f	0,967
g	0,755
h	0,754
i	0,655
j	0,622
k	0,578
l	0,782

Weg	Länge in km	Geogebra Streckennetz Otterstadt	Matrix (Octave)	Ergebnis (Octave)	Ergebnis (graphisch)
a	1,42	Abb.3a: Mögliche Haltestellen in Otterstadt	Abb.3b: Matrix des Streckennetzes von Otterstadt sowie die dazugehörige Permutationsmatrix	Abb.3c: kürzester Weg	Abb.3d: Ergebnis Otterstadt Geogebra
b	0,765
c	0,697
d	0,812
e	0,436
f	0,486
g	0,473
h	0,415
i	1,91

Weg	Länge in km	Geogebra Streckennetz Speyer	Matrix (Octave)	Ergebnis (Octave)	Ergebnis (graphsich)
a	0,885	Abb.4a: Mögliche Haltestellen in Speyer	Abb.4b: Matrix des Streckennetzes von Speyer sowie die dazugehörige Permutationsmatrix	Abb.4c: kürzester Weg	Abb.4d: Ergebnis Speyer Geogebra
b	0,96
c	2,098
d	0,555
e	1,04
f	0,874
g	0,473
h	0,786
i	0,872
j	0,6
k	0,82
l	0,812
m	0,604
n	0,712
o	0,524
p	0,864
q	0,888
r	0,86
s	0,505

Ergebnisse:

Mit Hilfe einer Funktion, die wir in Octave implementiert haben, können wir den Ameisenalgorithmus bedingt anwenden. So erhalten wir durch das Einsetzen der Werte in eine Funktion die sogenannte "Gruchsmatrix". Mit Hilfe dieser Matrix kann man den kürzesten Weg ablesen, denn dort wo der Geruch am stärksten ist, hat die Matrix die höchsten Einträge und somit die kürzesten Wege.

Der kürzeste Weg durch Neuhofen führt über die Haltestellen 1, 4 & 7. Dabei muss vom Startpunkt aus, eine Strecke von 1,825 km zurückgelegt werden.

Der kürzeste Weg durch Waldsee führt über die Haltestellen 1, 3, 6 & 7. Dabei muss ausgehend von der letzten Haltestelle in Neuhofen, eine Strecke von 2,155 km zurückgelegt werden.

Der kürzeste Weg durch Otterstadt führt über die Haltestellen 1, 3 & 5. Dabei muss ausgehend von der letzten Haltestelle in Waldsee, eine Strecke von 1,17 km zurückgelegt werden.

Der kürzeste Weg durch Speyer führt über die Haltestellen 1, 3, 4, 7, 10 bis zum Endpunkt 11. Dabei muss ausgehend von der letzten Haltestelle in Otterstadt, eine Strecke von 3,282 km zurückgelegt werden.

Die Gesamtstrecke der Straßenbahnlinie, welche sich aus der Summe der Teilstrecken und den Verbindungsstrecken zusammensetzt, beträgt 14,302 km.

Probleme & Alternativen:

Nach dem Durchlauf des 2. Modellierungszyklus erhält man jeweils die kürzesten Wege. Allerdings sind die kürzesten Wege keineswegs die günstigsten Wege, denn bricht man die Bearbeitung an dieser Stelle ab, so könnte es passieren, dass die Straßenbahn an Haltestellen anhält, die ungünstig liegen (zu wenig Bewohner, die in der Umgebung wohnen). Zudem erhält man als Ergebnis auch mehrere Möglichkeiten, wie das Streckennetz verlaufen könnte, sodass der Modellierungszyklus noch nicht den genauen Weg anzeigt.

Die Alternative wäre alle möglichen Wege zu betrachten und durch aufsummieren den kürzesten Weg herauszufinden. Allerdings wäre dies für alle Ortschaften durchzuführen zum Einen fehleranfällig und zum Anderen sehr zeitintensiv.

Modellierungszyklus III

Zielsetzung

Im Modellierungszyklus III werden im Vergleich zum vorherigen Modellierungszyklus den einzelnen Haltestellen verschiedene Werte zugeordnet, die jeweils die Wichtigkeit der einzelnen Haltepunkte darstellen sollen. Das heißt, dass einige Haltestellen an Knotenpunkten von Straßen liegen, was bedeutet, dass diese besser zu erreichen sind bzw. sich viele Häuser in einem Radius von 300m befinden. So liegen einige Haltestellen an Punkten, bei denen beispielsweise im Umkreis von 300m nur 100 Wohnhäuser sind und andere wiederum in Wohngegenden, wo 400 Häuser in Reichweite der Straßenbahnhaltestelle liegen. Um so eine Klassifizierung zu erreichen, welche Haltestellen tatsächlich angefahren werden müssen, sollen im folgenden Zyklus die Haltestellen mittels Octave parametrisiert werden.

Ablauf Modellierungszyklus III

Daraus ergeben sich die vorliegenden Tabellen der jeweiligen Ortschaften, bei welchen nun den einzelnen Haltepunkten verschiedene prozentuale Werte zugeordnet wurden, die die Wichtigkeit, ob eine Haltestelle befahren werden sollte beinhalten. Wenn so zum Beispiel ein Punkt den Wert 1 zugeordnet bekommt, bedeutet das, dass diese Haltestelle auf jeden Fall befahren werden muss. Umgekehrt wird daraus ersichtlich, dass der Wert 0 angibt, die Haltestelle müsse nicht befahren werden, da sich vergleichsweise wenig bewohnte Fläche im Umkreis befindet.

→ Mögliche Software: Tabellenkalkulation, GeoGebra, Octave

Zum besseren Verständnis hilft dieser Link.

Ort und Häuseranzahl	Haltestelle	Anzahl an Häusern (Radius 300m)	Anteil an Gesamthäusern eines Dorfes (in %)	Muss befahren werden
LU-Rheingönheim	Startpunkt			Ja

Neuhofen (2042)	Punkt 1	185	9,06	Ja
	Punkt 2	221	10,82	Nein
	Punkt 3	345	16,90	Nein
	Punkt 4	259	12,68	Nein
	Punkt 5	337	16,50	Nein
	Punkt 6	184	9,01	Nein
	Punkt 7	220	10,77	Ja

Waldsee (2764)	Punkt 8	62	2,24	Ja
	Punkt 9	64	2,31	Nein
	Punkt 10	382	13,82	Nein
	Punkt 11	167	6,04	Nein
	Punkt 12	331	11,98	Nein
	Punkt 13	497	17,98	Nein
	Punkt 14	105	3,80	Ja

Otterstadt (1109)	Punkt 15	181	16,32	Ja
	Punkt 16	227	20,47	Nein
	Punkt 17	496	44,72	Nein
	Punkt 18	225	20,28	Nein
	Punkt 19	205	18,49	Ja

Speyer (10190)	Punkt 20	238	2,34	Ja
	Punkt 21	454	4,46	Nein
	Punkt 22	175	1,72	Nein
	Punkt 23	73	0,72	Nein
	Punkt 24	53	0,52	Nein
	Punkt 25	173	1,70	Nein
	Punkt 26	32	0,31	Nein
	Punkt 27	0 kein Wohngebiet (Industriegebiet)	0	Nein
	Punkt 28	262	2,57	Nein
	Punkt 29	187	1,84	Nein
	Endpunkt	353	3,46	Ja

Haltestelle	Anteil an Häusern im Umkreis von 300m (in %)	Normierte Haltestellenwerte (in %)	Normierte Streckenwerte für Matrix	Geogebra Streckennetz Neuhofen	Matrix (Octave)	Ergebnis (Octave)	Ergebnis (graphisch)
P1	1	0	b = 0,31 c = 0,5 d = 0,365 e = 0,81 f = 0,865 g = 0,56 h = 0,75 i = 0,98 j = 0,845 k = 0,73 l = 0,865 m = 0,98 n = 0,75	Abb.1a: Mögliche Haltestellen in Neuhofen	Abb.1b: Matrix des Streckennetzes von Neuhofen sowie die dazugehörige Bedingungsmatrix	Abb.1c: sinnvollster Weg	Visualisierung des Ergebnisses
P2	0,16	0,62
P3	0,26	1
P4	0,19	0,73
P5	0,25	0,96
P6	0,13	0,5
P7	1	1

Haltestelle	Anteil an Häusern im Umkreis von 300m (in %)	Normierte Haltestellenwerte (in %)	Normierte Streckenwerte für Matrix	Geogebra Streckennetz Waldsee	Matrix (Octave)	Ergebnis (Octave)	Ergebns (graphisch)
P1	1	0	b = 0,38 c = 0,06 d = 0,44 e = 0,235 f = 0,555 g = 0.88 h = 0,72 i = 0,515 j = 0,84 k = 1 l = 0,84	Abb.2a: Mögliche Haltestellen in Waldsee	Abb.2b: Matrix des Streckennetzes von Waldsee sowie die dazugehörige Bedingungsmatrix	Abb.2c: sinnvollster Weg	Visualisierung des Ergebnisses
P2	0,04	0,12
P3	0,26	0,76
P4	0,12	0,35
P5	0,23	0,68
P6	0,34	1
P7	1	1

Haltestelle	Anteil an Häusern im Umkreis von 300m (in %)	Normierte Haltestellenwerte (in %)	Normierte Streckenwerte für Matrix	Geogebra Streckennetz Otterstadt	Matrix (Octave)	Ergebnis (Octave)	Ergebnis (graphisch)
P1	1	0	b = 0,225 c = 0,5 d = 0,225 e = 0,725 f = 0,725 g = 1 h = 0,725	Abb.3a: Mögliche Haltestellen in Otterstadt	Abb.3b: Matrix des Streckennetzes von Otterstadt sowie die dazugehörige Bedingungsmatrix	Abb.3c: sinnvollster Weg	Visualisierung des Ergebnisses
P2	0,24	0,45
P3	0,53	1
P4	0,24	0,45
P5	1	1

Haltestelle	Anteil an Häusern im Umkreis von 300m (in %)	Normierte Haltestellenwerte (in %)	Normierte Streckenwerte für Matrix		Geogebra Streckennetz Speyer	Matrix (Octave)	Ergebnis (Octave)	Ergebnis (graphisch)
P1	1	0	a = 0,5 b = 0,189 c = 0 d = 0,581 e = 0,554 f = 0,581 g = 0,27 h = 0,135 i = 0,081 j = 0,554	k = 0,122 l = 0,541 m = 0,041 n = 0,784 o = 0,243 p = 0,203 q = 0,486 r = 0,784 s = 0,703	Abb.4a: Mögliche Haltestellen in Speyer	Abb.4b: Matrix des Streckennetzes von Speyer sowie die dazugehörige Bedingungsmatrix	Abb.3d: sinnvollster Weg	Visualisierung des Ergebnisses
P2	0,37	1
P3	0,14	0,378
P4	0,06	0,162
P5	0,04	0,108
P6	1	1
P7	0,03	0,081
P8	0	0
P9	0,21	0,567
P10	0,15	0,405
P11 (Endpunkt)	1	1

Ergebnisse:

Mit Hilfe einer Funktion, die wir in Octave implementiert haben, können wir den Ameisenalgorithmus bedingt anwenden, wobei diese Funktion nun etwas abgeändert ist, da eine sogenannte Bewertungs- oder Bedingungsmatrix zu der ursprünglichen Matrix addiert wird. So erhält man eine kumulierte "Geruchsmatrix", die den kürzesten Weg mit den am stärksten gewichteten Haltestellen angibt. Dabei muss sich nicht zwingend die Strecke geändert haben, da immernoch die kürzesten Wege betrachtet werden. Im Folgenden kann man dann den Begriff des "besten Weges" anwenden.

Der beste Weg durch Neuhofen führt über die Haltestellen 1, 3, 4, 5 & 7. Dabei muss vom Startpunkt aus, eine Strecke von 2,190 km zurückgelegt werden.

Der kürzeste Weg durch Waldsee führt über die Haltestellen 1, 3, 6 & 7. Dabei muss ausgehend von der letzten Haltestelle in Neuhofen, eine Strecke von 2,164 km zurückgelegt werden.

Der kürzeste Weg durch Otterstadt führt über die Haltestellen 1, 2, 3 & 5. Dabei muss ausgehend von der letzten Haltestelle in Waldsee, eine Strecke von 1,674 km zurückgelegt werden.

Der kürzeste Weg durch Speyer führt über die Haltestellen 1, 2, 5, 6, 9 bis zum Endpunkt 11. Dabei muss ausgehend von der letzten Haltestelle in Otterstadt, eine Strecke von 4,097 km zurückgelegt werden.

Die Gesamtstrecke der Straßenbahnlinie, welche sich aus der Summe der Teilstrecken und den Verbindungsstrecken zusammensetzt, beträgt 15,995 km.

Fazit

Nach Abschluss unseres Projektes können wir zusammenfassend sagen, dass wir unser Ziel erreicht und den kürzesten Weg für die Straßenbahnlinie durch die 4 Orte gefunden haben. Die Länge aller Straßen beträgt 14,302 km, wenn wir nur den Parameter mit den kürzesten Wegstrecke zwischen den einzelnen Haltestellen betrachten. Dem gegenüber steht eine Strecke von 15,995 km, die wir durch die Hinzunahme des gewichteten Parameters der Bevölkerungsdichte, im Umkreis um die jeweiligen Haltestellen, erreicht haben. Im Laufe des Modellierungsprozesses haben sich Schwächen des Programms Octave gezeigt: Zum Einen trat das Problem auf, dass das Programm Punkte mehrfach durchlaufen hatte, also Schleifen gebildet hatte. Das hat dazu geführt, dass die while-Schleifen sich in einem Endlosprozess befanden, da die Abbruchbedingung nie erreicht wurde. Zum Anderen wurden die Endpunkte hin und wieder gar nicht erreicht, sodass die Permutationen per "Handarbeit" angepasst werden mussten.