Weihnachtsmann rot

Aufgabe vom 17. Dezember

Wichtelrouten

Autoren: Enrico Bortoletto, Karlotta Kruschke, Niels Lindner

Projekt: Algebraic and Tropical Methods for Periodic Timetabling (MATH+ Incubator Project IN-A1)

Aufgabe:

Wie viele Kinder doch auf dieser Erde leben! Und an Weihnachten wollen sie alle Briefe an den Weihnachtsmann schreiben. In den letzten Jahren mussten die Elfen daher immer mehr Postämter bauen, um all die Briefe zu sortieren. Mittlerweile gibt es zwölf von ihnen, die über den ganzen Nordpol verstreut sind: das Hauptgebäude, genannt NP, und elf weitere Ämter, nummeriert von 1 bis 11.

Elf Ralph seufzt. Er und sein kleiner Bruder Steffan wurden angewiesen, den nächsten Stapel Briefe von den Postämtern in das NP-Gebäude zu bringen, wo sie bearbeitet werden sollten. Obwohl sie Rentiere nutzen dürfen, ist es nicht wirklich angenehm stundenlang durch den Schnee zu reiten. Ralph schaut auf die Karte, auf der nicht nur die Postämter und Reitwege eingezeichnet sind, sondern auch wie viele Minuten man auf den entsprechenden Wegen von Amt zu Amt unterwegs ist. Zusammen mit der Karte erhielt er auch eine Liste mit Postämtern, auf der angegeben ist, wie viele Briefe in jedem Postamt abgeholt werden müssen (s. Abb. 1). „Jeder unserer Rucksäcke kann genau 143 Briefe aufnehmen. Ich bin ziemlich sicher, dass wir das schaffen können“, behauptet Ralph. „Aber welchen Weg sollten wir wählen, um so schnell wie möglich fertig zu werden?“

Abbildung 1:
Die Karte der Postämtern. Die Kreise markieren die Postämter. Die Linien sind die Reitwege zwischen den Ämtern, wobei die Zahlen die Reitzeit in Minuten für die entsprechenden Reitwege angeben.
Liste der Postämter mit der Anzahl der abzuholenden Briefe.

Ralph und Steffan möchten ihren Auftrag so schnell wie möglich erledigen. Der Auftrag beginnt, sobald die beiden Wichtel das NP-Gebäude verlassen, und ist erledigt, wenn sie mit allen Briefen in das NP-Gebäude zurückkehren. Sie verlassen das Gebäude zur gleichen Zeit. Jedes Mal, wenn einer von ihnen ein Postamt erreicht, holt er entweder alle Briefe dort ab oder lässt sie alle im Postamt zurück. Um die Briefe abholen zu können, müssen sie natürlich genügend Platz in ihrem Rucksack haben. Da Ralph und Steffan begeisterte Sightseeing-Fans sind, möchte keiner von beiden zweimal dasselbe Postamt besuchen (mit Ausnahme des NP-Gebäudes, zu dem sie aber erst ganz am Ende zurückkehren). Ralph, der stärker ist, wird den längeren Weg nehmen.

Die beiden Wichtel denken eine Weile über ihre kommende Tour nach, sind aber nicht in der Lage, den besten Weg zu finden. Zum Glück kommt ihre Freundin Petra, die wirklich gut in Mathe ist, vorbei und kann ihnen helfen. Sie findet schnell die besten Touren für die beiden, sodass sie ihren Job in möglichst kurzer Zeit abschließen können. „Auf diese Weise wird Ralph nach 3 Stunden und 24 Minuten zurück sein“, meint Petra.

Ralph und Steffan diskutieren Petras Vorschlag:

  1. Steffan: „Obwohl Ralph die Briefe in Postamt 3 abholt, hätte ich genug Zeit um dort auch vorbeizufahren und unsere Cousine Luise zu besuchen. Ich würde sogar trotzdem noch vor Ralph zurück im NP-Gebäude sein!“

  2. Ralph: „Cool! Wir können zusammen zum ersten Postamt reiten.“

  3. Ralph: „Ich komme nicht am Postamt 4 vorbei.“

  4. Steffan: „Derjenige von uns, der die Briefe beim Postamt 3 abholt, wird auch die Briefe aus Postamt 9 mitnehmen.“

  5. Steffan: „Ich kann es schaffen, genau eine halbe Stunde vor Ralph zurück zu sein, um ihm einen leckeren Kakao zu kochen. Das wird ihm gefallen!“

Welche dieser Aussagen sind richtig?

Illustration: Friederike Hofmann

Die Aufgabe als PDF runterladen

Antwortmöglichkeiten:

  1. (a), (b) und (c).

  2. (a), (b) und (d).

  3. (a), (b) und (e).

  4. (a), (c) und (d).

  5. (a), (c) und (e).

  6. (a), (d) und (e).

  7. (b), (c) und (d).

  8. (b), (c) und (e).

  9. (b), (d) und (e).

  10. (c), (d) und (e).

Sie müssen sich einloggen um die Aufgaben abgeben zu können.

Projektbezug:
Das MATH+ Incubator Project Algebraic and Tropical Methods for Periodic Timetabling untersucht Verbindungen zwischen der mathematischen Optimierung von Fahrplänen im öffentlichen Verkehr und rein mathematischen Disziplinen. Das Planen von Fahrgast- und Fahrzeugtouren ist ein wichtiges Problem im öffentlichen Nahverkehr. Bei dem hier vorgestellten Problem handelt es sich um ein sogenanntes Capacitated Vehicle Routing Problem, das zur Klasse der NP-schweren Optimierungsprobleme gehört. Bisher wurde noch kein effizienter Algorithmus gefunden, der diese Art von Problemen optimal löst. Der Beweis über die Existenz eines solchen Algorithmus ist ein offenes Millennium-Problem.