Sitzplätze eines Zuges reservieren

Die folgende Applikation wird vorgestellt:

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:

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:
Das Accommodating Ratio einer fairen Strategie bezüglich einer Sequenz von Reservierungsanfragen ist der
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, 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:

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.