19: Rudi rutscht aus / Slipping Rudi

  • Die Idee, die mich zum Ziel geführt hat, ist die Betrachtung der Gesamtwartezeit aller Gespanne (=“Umläufe“, um es in normaler Fahrplansprache auszudrücken) in einer Stunde. Zum Beispiel in Linie 1 sieht ein Umlauf so aus, dass man um 0:30 in Grönland losfährt, um 1:55 in Afrika ankommt, um 2:15 wieder zurückfährt und um 3:40 ankommt. Die nächste Fahrt kann dann ab 4:30 losgehen, weshalb man zunächst 4 Umläufe für diese Linie braucht. Die Wartezeit eines Umlaufs sind 20min in Afrika und 50min in Grönland, also 70min gesamt. Sehr einfach zu rechnen ist, dass dies auch der Gesamtwartezeit pro Stunde entspricht, denn jeder Umlauf wartet 70min/4h, es gibt aber auch 4 Umläufe. Dies muss auch immer so sein. Für die Linien 2,3,4,5 ergeben sich 70,90,60,80min, also insgesamt werden 370min pro Stunde gewartet. Wenn man nun einen Umlauf wie auch immer einsparen kann, dieser also gar nicht fährt, müssen exakt 60min Wartezeit pro Stunde wegfallen, da ja die Gesamtfahrzeit dieselbe bleibt.

    Das Schöne daran ist nun, dass nur an Endhaltestellen gewartet wird und man damit zum einen den Fahrplan auf diese reduzieren kann und zum anderen jede Endhaltestelle gesondert optimieren kann:


    Okavango Delta Depot: Hier fährt nur Linie 1, also haben wir in jedem möglichen Fahrplan 20min Wartezeit pro Stunde.

    Lama Logistik: Linie 4 und 5 fahren hier. Es gibt also die beiden Möglichkeiten, dass diese hier jeweils wenden oder dass durchgebunden wird. Letzteres ist offensichtlich wesentlich schlechter. Also beträgt die Wartezeit pro Stunde hier mindestens 50min.

    Grönland Geschenkelager: Hier enden vier Linien. Das scheint zwar kompliziert zu sein, ist es aber netterweise gar nicht. Jeder ankommende Schlitten muss ja, wenn er nicht dieselbe Linie zurückfährt, mindestens 15min warten. Da die Wendezeit jeder einzelnen Linie aber >15min ist, und gleichzeitig eine Durchbindung der Linie 2 auf 4 und der Linie 1 auf 3 in beiden Richtungen exakt 15min Wartezeit bringen, muss das die einzig optimale Möglichkeit sein. 2 Durchbindungen à 2 Richtungen à 15min macht 60min gesamt.

    Panda Pakete: Dies ist die interessanteste Station. Mit ein wenig Herumprobieren sieht man, dass zwei optimale Möglichkeiten existieren: A) Linie 2 endet hier und Linie 3 wird auf 5 durchgebunden – macht 60min Wartezeit. B) Ankommende Schlitten der Linie 3 fahren als 5 weiter, ankommende Linien 5 werden zu 2 und 2 wird zu 3.


    Insgesamt beträgt die Gesamtwartezeit pro Stunde also 190 min, und damit können (370-190)/60 = 3 Umläufe eingespart werden. Jetzt die Frage zu den Wünschen. Alle können sowieso nicht erfüllt werden, weil es die entsprechende Antwortmöglichkeit nicht gibt. Möglichkeit B sorgt dafür, dass es nur einen einzigen (25h langen) Umlauf gibt, der überall langfährt, also auch in Europa und Australien. 2 Wünsche können also erfüllt werden.

    Damit wäre man zwar fertig, aber die Begründung für die Unmöglichkeit aller 3 Wünsche hätte ich dann doch gerne auch mathematisch. B fällt wegen des langen Umlaufs direkt raus. Bei A erfüllt der Umlauf über die Linien 1,3 und 5 zwar den Wunsch von Riley, aber beide anderen nicht, da er nicht über Europa führt und 14h lang ist. Der andere Umlauf über 2 und 4 erfüllt zwar die Wünsche der beiden anderen (11h lang und über Europa), geht aber nicht über Australien. Damit bin ich wirklich fertig mit der Aufgabe.


    Schon im Feedback angekündigt: Sehr nett finde ich hieran, dass die Anzahl der optimalen Fahrpläne so stark beschränkt ist, trotz der Haltestelle in Grönland, die so kompliziert scheint. Es gab (auch hier im Kalender) schon öfters Aufgaben, bei denen man am Ende noch 20 oder so Möglichkeiten nach einem zweiten Kriterium durchforsten musste, hier waren es nur 2. Und ganz zum Schluss noch ein Tipp für alle evtl kommenden Fahrplanaufgaben der Zukunft: Es gibt eine sehr übersichtliche Notation für Taktfahrpläne, die meines Wissens sma+partner erfunden hat. Zu sehen ist sie beispielsweise im ITF von NRW, zu finden unter http://www.kcitf-nrw.de/servic…f/netzgrafik-nrw-2018.pdf . Wenn man sich so die An- und Abfahrtszeiten aufschreibt (und Ankunftszeiten, bei denen die :00 (mehrfach) überschritten wird, mit +1 (+2,+3,usw) versieht), bekommt an einen sehr viel besseren Überblick über das Ganze. Hat mir jedenfalls bei beiden Fahrplanaufgaben sehr geholfen. Generelles Wissen über Fahrpläne ist natürlich auch nett – so bedeutet ITF „Integraler Taktfahrplan“. Takt = alles wiederholt sich regelmäßig, üblicherweise jede Stunde (und Linien, die alle 5/10/15/20/30min fahren passen da natürlich auch rein). Integral = alle Linien treffen sich an gewissen Umsteigebahnhöfen, sodass kurze Umstiege möglich sind. Letzterer Punkt half natürlich vor allem bei der letzten Aufgabe. Eine weitere wichtige Eigenschaft vieler Fahrpläne ist die Symmetrieminute, also die Minute, zu der sich zwei Züge derselben Linie treffen. Ist dies auf jeder Linie dieselbe, spricht man von einem symmetrischen Fahrplan, der bei Umstiegen zwischen zwei Linien dieselbe Umsteigezeit in beide Richtungen garantiert. Bei dieser Aufgabe war das zwar nicht gegeben, aber bei der anderen wurde mit Symmetrieminute 0 gearbeitet – europaweit ist eigentlich 58,5 üblich (warum auch immer so eine krumme Zahl).

  • Ich hab mir hier eine Tabelle aus den möglichen Verbindungen gemacht, wobei ich die beiden Richtungen der gleichen Linie als unterschiedliche Verbindungen getrennt hab. In der Tabelle eingetragen steht dann die Wartezeit, um von der linken zur oberen Verbindung zu wechseln: [IMG:https://i.imgur.com/J78wAb2.png]

    Da muss man Einträge nehmen, sodass in jeder Spalte und Zeile genau ein Eintrag verwendet wird und die Summe minimal wird. Drei Einträge sind sofort offensichtlich, wenn wir die entsprechenden Spalten und Zeilen rausnehmen bleibt diese Tabelle: [IMG:https://i.imgur.com/EPCREXE.png]

    Die macht den Rest schon deutlich übersichtlicher und man kann schnell sehen, dass zwei zeitoptimale Möglichkeiten bleiben. Beide erfüllen je zwei Wünsche: Bei (1-1-3-5-5-2-4-4-2-3) fahren alle Rentiere alle Linien in beide Richtungen und Wünsche 1 und 2 werden erfüllt. Bei (1-1-3-5-5-3)(2-2-4-4) gibt es zwei Verbindungsschleifen wenn Rudis Team nur Linien 2 und 4 fährt, werden Wünsche 1 und 3 erfüllt, aber wenn sie mindestens einmal die andere Schleife fahren, werden wünsche 1 und 2 erfüllt.

  • Zusätzlich sollte man korrekterweise auch noch schauen, ob ein nahtloser Übergang vom Standard- zum obigem Notfallfahrplan ohne Ausfälle oder Verspätungen auch möglich ist.


    Wenn sich Rudi bei der gelben Landung in GG zur Minute 20 verletzt, kann beispielsweise das blaue Gespann nicht sofort die rote Linie zur Minute 30 bedienen. Denn zum Umspannen brauchen sie - selbst wenn die Notplanung sofort komplett durchdacht wäre - mindestens bis Minute 35. Rot und grün müssen also nach dem Unfall noch wie gehabt losfahren, erst von da an kann dann immer zyklisch gewechselt werden.


    20 Unfall (zu dieser Zeit warten gerade blau X, grün und rot)

    (30 rot ab)

    (35 grün ab)

    40 rot an -> 55 blau ab

    50 grün an -> 05 gelb ab

    15 blau an -> 30 rot ab

    20 gelb an -> 35 grün ab


    Blau X wurde also schon mal eingespart, zusätzlich zum Verlust von gelb. Analog kann man den Übergang in PP planen. Zur Unfallminute 20 warten dort grün, blau und rosa Y.


    (25 grün ab)

    (30 blau ab)

    40 blau an -> 55 rosa ab

    00 grün an -> 25 grün ab

    10 rosa an -> 30 blau ab


    Rosa Y kann eingespart werden. Für diese ganze Notfallplanung hat Rachel nach dem Unfall also bis zur Minute 40 gute 20 Minuten Zeit. Respekt :)