Es musste sich darüber abgestimmt werden, wie das Programm agieren soll, aus welchen Bestandteilen es bestehen soll usw.

1. Um zuerst einmal eine Grundlage zu schaffen, wurde ein simples Auswertungsprogramm geschrieben.

    def auswertung(zreihe):
    verspaetung=0
 
    for zug in zreihe:
        verspaetung=verspaetung+(zug["ankunft"]-zug["ankunftplan"])
 
    return verspaetung
 

1. Dazu definierten wir zuerst die Variable verspaetung, die die Gesamtverspätung eines Fahrplans angibt.
2. Anschließend ließen wir die Verspätung für jeden Zug aus der Differenz von geplanter und tatsächlicher Ankunftszeit berechnen und addierten sie für alle Züge.

1. Danach erstellten wir ein Programm, um vorgefertigte Daten zu Zügen aus einer Textdatei einzulesen

    def einlesen(datei):
	text = open(datei, "r")
	zuege = list(text.read().split('\n')) #splittet Text in Zuege
	ausgabe = []
	for zug in zuege:
		zug=list(zug.split(',')) #splittet Zuege in Zugdaten
		wbzug = {"vmax" : zug[0], "vist" : zug[1], "vziel" : zug[2], "abfahrt" : zug[3], "ankunft" : zug[4], "nummer" : zug[5], "ort" : zug[6], "beschl" : zug[7]}
		print wbzug
		ausgabe.append(wbzug)
 
	return ausgabe
	text.close()
 
print einlesen("zuege.txt")
 

1. Zuerst wird eine Textdatei eingelesen.
2. Anschließend wird diese gesplittet, sodass jede Zeile einen Zug darstellt.
3. Dann wird jeder Zug erneut gespalten, um für jeden Zug eine Liste aus einzelnen Eigenschaften zu erhalten.
4. Danach erstellen wir ein Wörterbuch für jeden Zug, in dem jeder Eigenschaft der Name zugeordnet wird, unter der sie aufgerufen werden kann.
5. Die Wörterbücher aller Züge werden dann in der Liste ausgabe zusammengefasst

1. Außerdem haben wir ein Programm für einen Algorithmus, der alle Möglichkeiten für die Ankuftsmöglichkeiten und Verspätungen der Züge, geschrieben

import itertools
import simulation
import auswertungsprogramm
 
zug1={"vavg":20,"vist":20,"abfahrt":0,"besetzung":100,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":595,"ort":2000}
zug2={"vavg":30,"vist":30,"abfahrt":2,"besetzung":50,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":123,"ort":0}
zug3={"vavg":30,"vist":20,"abfahrt":4,"besetzung":20,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":987,"ort":0}
 
zuege = [zug1, zug2, zug3]
 
 
def bruteforce(zugliste):
    #minimumzeit = auswertungsprogramm.auswertung(list(itertools.permutations(zugliste)[1]))
    for perm in itertools.permutations(zugliste): # Permutationen werden ermittelt
        temp = simulation.simuliere(list(perm)) # Permutationen werden gefahren
 
 
bruteforce(zuege)   

1. Als drittes haben die schon vorhandenen Programme (Simulation, Auswertung, Algorithmus)

1. Programme wurden wieder zum Laufen gebracht
2. es wurde erreicht, dass der Algorithmus für das Durchprobieren die beste Möglichkeit und die dazugehörige Reihenfolge ausgibt
3. Ein neues Auswertungsprogramm wurde begonnen
4. Eine kurze Zusammenfassung der bereits vorhandenen Programme wurde erstellt

• Simulation:
• enthalten sind: Streckenoptionen bestehend aus: Länge, Abstand, Zugdichte.
• Es kann (soll können): simulieren und auswerten

• Algorithmus:
• enthalten sind:
• Es kann (soll können): einlesen

• Masterprogramm:
• liest die anderen Programme (Klassen) ein und gibt dann die „Lösung“ und die Auswertung aus

   from auswertungsprogramm import auswertung
#from awneu import auswertung
from simulation import *
from read import *
from nfaq import *
from tauschheuristik import *
 
import time
 
import logging
import sys
 
# create logger
logger = logging.getLogger('simple_example')
logger.setLevel(logging.DEBUG)
 
# create console handler and set level to debug
ch = logging.StreamHandler(stream=sys.stdout)
ch.setLevel(logging.DEBUG)
 
# create formatter
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
 
# add formatter to ch
ch.setFormatter(formatter)
 
# add ch to logger
logger.handlers=[]
logger.addHandler(ch)
 
fh=logging.FileHandler("mylog2.log")
fh.setLevel(logging.DEBUG)
 
# create formatter
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
 
# add formatter to ch
fh.setFormatter(formatter)
 
# add ch to logger
logger.addHandler(fh)
 
######
 
def timeit(method):
 
    def timed(*args, **kw):
        ts = time.time()
        result = method(*args, **kw)
        te = time.time()
        print "#####################"
        print '%r (%r, %r) %2.5f sec' % \
              (method.__name__, args, kw, te-ts)
        print "#####################"
        return result
 
    return timed
 
anschlussdaten = [{"minute": 0, "intervall": 20}, {"minute": 13, "intervall": 30}, {"minute": 42, "intervall": 60}]
streckendaten = {"abstand": 1500, "streckenlaenge": 20000}
 
# print(simulieren(folge,streckendaten["abstand"],streckendaten["streckenlaenge"]),anschlussdaten)
 
#folge = tauschalgorithmus(reader("zuege.txt"),streckendaten, anschlussdaten)
#simuliert = simulieren(folge, streckendaten["abstand"], streckendaten["streckenlaenge"])
 
 
@timeit
def brutal():
    return auswertung(simulieren(nfaq(reader("zuege.txt"),streckendaten, anschlussdaten)),anschlussdaten)
 
@timeit
def tausch():
    #return auswertung(simulieren(tauschalgorithmus(reader("zuege.txt"),streckendaten, anschlussdaten, 50,3)),anschlussdaten)
    return auswertung(simulieren(tauschalgorithmus(reader("zuege.txt"),streckendaten, anschlussdaten, 50,3)),anschlussdaten)
print(tausch())
print(brutal())
 

Heute haben wir die Zeit genutzt, um die Arbeit der letzten Wochen mithilfe von Code-Teilen in der Wiki zu dokumentieren.
Außerdem haben wir schon einen ersten Blick in das Buch Automatische Erzeugung und Optimierung von Taktfahrplänen in Schienenverkehrsnetzen geworfen.

Jakob hat sich mit der Dissertation beschäftigt, die aufgrund ihrer Auslegung auf den ITF und die Erstellung von Taktknoten nur bedingt Hilfestellung für unsere Problemstellung liefert. Auf der Rückfahrt nach Berlin bot sich „dank“ spielender Kinder im Gleisbereich der Geislinger Steige ein regelrechter Zugstau in und um Ulm Hbf, das optimale Anwendungsszenario für unser Programm.

Nachdem aus ungeklärten Gründen nur ältere Versionen der Dateien verfügbar waren, war das Programm nicht mehr lauffähig. Deswegen wurden die Programmteile von Jakob weitestgehend neu geschrieben und um Funktionen erweitert.

Das Programm ist nun in der Lage, alle Kombinationen stupide durchzurechnen und die beste Reihenfolge, so wie die Gesamtverspätung auszugeben. Die Rechnung mit der Gesamtreisezeitverlängerung kann nach der Fertigstellung dieses Moduls durch Ricardo ohne Probleme eingefügt werden.

Es wurden erste Messungen durchgeführt, um zu zeigen wie schnell diese Methode an ihre Grenzen stößt. Hierzu wurden willkürliche Züge erstellt und die Rechenzeit gemessen (Ubuntu 15.10, i5-760)(Je nur ein Versuch. Deshalb nicht repräsentativ, aber als Größenordnung okay.):

Mit Ausgabe:

1. 3 Züge: 0m00,073s
2. 6 Züge: 0m12,757s
3. 7 Züge: 2m04,064s
4. 8 Züge: 20m55,436s

Das Einleseprogramm funktioniert nun auch wieder, aus bisher ungeklärten Gründen jedoch nicht in Verbindung mit dem Simulator.

Nächstes Ziel ist die Implementierung eines Tauschalgorithmus. Dieser wählt zwei zufällige Züge aus, tauscht deren Positionen aus und ermittelt, ob die neue Situation eine Verbesserung erzielt. Ist dem so, wird diese übernommen und der Algorithmus beginnt von vorne. Eine solche Tauschheuristik ist bei steigender Zugzahl sehr viel schneller als das Testen der n! Möglichkeiten.

Wichtig für weitere Algorithmen ist folgendes Modell zur Vorstellung: Alle Möglichen Lösungen (=ausgewertete Zugreihenfolgen) befinden sich auf einer Ebene. Nun wird je nach „Score“ der Auswertung diese Lösungen angehoben, es entsteht eine Hügellandschaft. Ziel eines jeden Algorithmus ist es nun, das „tiefste Tal“, also den geringsten Verspätungswert zu erreichen.

Große Gefahr besteht nun beim 2er-Tauschalgorithmus, in ein lokales Tal hineinzurutschen, da man aus ihm nie wieder hinaus gerät (Der Algorithmus geht ja nur Schritte bergab). Deshalb ist nächstes Ziel ein 3er-Tauschalgorithmus, der ggf. Optimierungen erzielen kann, die durch den 2er-Algorithmus nicht erreicht werden können.

Beispiel der Effizienz des 2er-Algorithmus:

#####################
'tausch' ((), {}) 0.97001 sec
#####################
8409.2
#####################
'brutal' ((), {}) 14.91523 sec
#####################
7184.0

Ricardo hat am Auswertungsprogramm weiter gearbeitet. Jakob hat die Fehler im Einleseprogramm gefunden, Problem war eine Inkonsistenz der Typen. Die 3er- Tauscheuristik wurde beinahe fertiggestellt.

auswertung_neu:

  <code python>
  def auswertung (ankunft, anschluss):

  #ZUWEISUNGEN
  summe = 0	#Summe der Wartezeiten
  key = ""	#Umsteigeanteile auf Anschlusszuege

  for ank in ankunft: #fuer jeden ankommenden Zug
	
      for i in range (0,len(anschluss)): #gehe jeden Anschlusszug durch
	# ZUWEISUNGEN
	anschl = anschluss[i]
	key = "auf" + str(i+1)
	abfahrt = 0
		
	#suche Zug, der als naechstes kommt
	n = 0
	while ank["ankunft"] >= abfahrt:
		abfahrt = anschl["minute"] + n* anschl["intervall"]
		n = n+1
	
	# BERECHNUNG
	time = (abfahrt - ank["ankunft"]) #Wartezeit pro  Person
	summe += ank[key] * ank["besetzung"] * time # Umsteigeanteil * Personen im Ankunftszug * Wartezeit pro Person
return summe
  </code python>
  

Seit dem letzten Eintrag wurde die auswertung()-Funktion neu geschrieben. Zudem wurde das auswertung_neu-File um Funktionen wie die Ermittlung der maximalen Wartezeit, der gesamten Verspätung und der maximalen Verspätung erweitert.

Jakob hat die 3er-Tauschheuristik prinzipiell fertig programmiert, welche 3 aufeinanderfolgende Züge nimmt, die beste Reihenfolge der drei Züge ermittelt, und dann diese wieder einsetzt. Eine andere Variante wäre, 3 komplett zufällige Züge zu wählen. Jedoch tauchte ein -bis dato ungelöster- Bug auf: Das Simulationsprogramm spielte absolut verrückt und ließ zB Züge fahren, die angekommen sind indem ihre Orte zurückgesetzt wurden und hängte sich in einer Endlosschleife auf, sämtliche Debug-Versuche schlugen fehl. Ruft man die Simulation von extern mit -identischen- Argumenten auf, funktioniert alles.

Aufgrund von mangelnder Priorität wurde das Debuggen zurückgestellt und Jakob hat sich dem „Simulated Annealing“ angenommen. Wir erinnern uns zurück an das Modell der Landschaft: Der Algorithmus arbeitet nun ähnlich dem 2er-Tauschalgorithmus, mit einer entscheidenden Änderung: Ähnlich des Abkühlens von Metallen oder Kristallisierung ist es dem Algorithmus möglich, auch Schritte „bergauf“ zu Springen um einem Möglichen lokalen Minimum zu entkommen. Die Sprungwahrscheinlichkeit ist abhängig von der „Temperatur“ des Systems, die abhängig von der Laufzeit ist. Die Geschwindigkeit und Form dieser Abkühlung ist nun imminent wichtig für den Erfolg des Annealing-Algorithmus.

Die sehr ähnliche Programmstruktur ergibt ähnliche Laufzeiten mit identischen Ergebnissen bei selber Tauschanzahl:

SimAnn: 175 Tauschversuche durchgeführt
#####################
'anneal' ((), {}) 3.93680 sec
#####################
8409.2
 
 
Tauschalgorithmus: 176 Tauschversuche durchgeführt
#####################
'tausch' ((), {}) 3.38647 sec
#####################
8409.2

Zum Vergleich die optimale Lösung mit n! Simulationen:

#####################
'brutal' ((), {}) 15.64856 sec
#####################
7184.0

Im Mathesis-Block konnte Ricardo leider nur kurz anwesend sein, um die Präsentationen zu hören. Der erste Tag wurde auf das erstellen der Präsentationen verwendet, der Rest floss in die Erstellung der Dokumentation und damit das Erstellen der Statistiken und Testen des Annealing.