Sitzplätze eines Zuges reservieren

Die folgende Applikation wird vorgestellt:

• Sitzplatzreservierung für den Fall, dass allen Reservierungen ein Sitzpkatz zugewiesen werden kann
  

Bedienung der Applikation

Die Applikation erlaubt das Hinzufügen und Entfernen von Reservierungen und das schrittweise Reservieren derselben bezüglich einer ausgewählten Strategie. 

Weitere Funktionen:

• Unter Settings werden die Anzahl Sitze und Stationen eingestellt
• Reserve reserviert die nächste Anfrage
• Cancel nimmt die Reservierung der letzten Anfrage zurück
• Remove löscht die als letztes gestellte Anfrage
• Add fügt eine neue Reservierung hinzu, deren Start- und Endstation in die entsprechenden Felder eingetragen sein müssen
• 3 Views (Sichten) stehen zur Auswahl. Eine Gesamtübersicht, sowie selektion eines Sitzplatzes oder einer Station
• Unit Cost ist ein voreingestelltes Scenario für die obere Schranke des Unit Cost Models
• Proportional Cost ist ein voreingestelltes Scenario für die obere Schranke des Proportional Cost Models

Zuerst sollten alle Anfragen hinzugefügt werden und dann können sie - Stück für Stück - reserviert werden.
Es kann auch zwischendurch die Strategie gewechelt werden. Die Sitzplatzzuweisungen werden automatisch angepasst.

---

Sitzplatzreservierungs-Applikation

[Applikation kann nicht gestartet werden]
Hier können Sie die Applikation jetzt schon starten.

Bewertung von Strategien
Strategien versuchen die Reservierungsanfragen so unterzubringen, die Einnahmen an den Ticketverkäufen maximiert werden. Dies bedeutet meist, dass möglichst viele oder Reservierungsanfragen zu langen Reisen untergebracht werden.
Untersucht werden an Hand von Beispielen die oberen Schranken der Güte von verschiedenen Strategien, außrdem wird das Einhalten von unteren Schranken beobachtet.
Zwei Kostenmodelle werden untersucht:

• Unit Cost Model: Jede Fahrt hat Kosten 1
• Proportional Cost Model: Die Kosten einer Fahrt sind proportional zu dessen Länge

Das Accommodating Ratio einer fairen Strategie bezüglich einer Sequenz von Reservierungsanfragen ist der

Quotient aus den Einnahmen unter Platzierung der Anfragen nach der Strategie und den Einnahmen des optimalen Algorithmus.

Bedingung ist, dass es möglich sein muss, alle Anfragen zu bedienen (accommodating). Außrdem darf keine Reservierungsanfrage abglehnt werden, wenn ihr ein Sitzplatz zugewiesen werden könnte (fair).

Untere Schranken sind allgemeingültig, obere Schranken werden jedoch nur von speziellen Beispielen eingehalten.

Ziel ist es,

• möglichst große untere Schranken zu beweisen
• Beispiele zu finden, von denen man möglichst kleine obere Schranken beweisen kann

Das aktuelle Ratio für das Unit Cost Model und für das Proportional Cost Model werden ständig aktualisiert.

Die folgenden Strategien stehen zur Auswahl:

• First Fit: Jede Anfrage wird auf den ersten freien Sitzplatz platziert
• Best Fit: Jede Anfrage wird in die kleinste Lücke platziert. Eine Lücke ist eine Reihe von Stationen wo der Sitzplatz durchgehend frei ist.
• Random: Unter allen möglichen Sitzplätzen wird einer zufällig ausgewählt.

---

Resultate

Im folgenden Abschnitt seien die Anzahl Stationen k.

Unit Cost Model

Allgemein

Untere Schranke:

Theorem Jede faire Strategie für das Sitzplatzreservierungsproblem ist 1/2 - accommodating

Obere Schranke:

Theorem Keine faire Strategie für das Sitzplatzreservierungsproblem ist besser als 6/7 - accommodating, wenn k ≥ 4

First Fit

Obere Schranke:

Theorem First Fit ist höchstens (2k-2)/(3k-6) - accommodating, wenn k ≥ 7 und k = 1 (mod 3)

Best Fit

Obere Schranke:

Theorem Best Fit ist höchstens (2k-2)/(3k-6) - accommodating, wenn k ≥ 7 und k = 1 (mod 3)

Proportional Cost Model

Allgemein

Untere Schranke:

Theorem Jede faire Strategie für das Sitzplatzreservierungsproblem ist 1/(k - 1) - accommodating

Obere Schranke:

Theorem Keine faire Strategie für das Sitzplatzreservierungsproblem ist besser als 11,211/(10,211+k) - accommodating, wenn k ≥ 4

First Fit

Obere Schranke:

Theorem First Fit ist höchstens 4/(k+2) - accommodating.

Best Fit

Obere Schranke:

Theorem Best Fit ist höchstens 4/(k+2) - accommodating.

Autoren: Simone Lehmann, Rainer Penninger

Literatur:

[1]:	Joan Bojar, Kim S. Larsen. Paper zu dem Sitzplatz-Reservierungsproblem.

© Universität Bonn, Informatik Abt. I -