Das Problem

Ein Hotel hat durch einen Fehler in seiner Buchungssoftware mehr Zimmer vermietet als eigentlich zur Verfügung stehen. Nun müssen einzelne Reservierungen storniert werden.
Jedes Zimmer hat denselben Wert, der Preis den die Gäste für ein Zimmer zahlen varriert allerdings. Daher möchte das Hotel natürlich die günstigeren Buchungen stornieren während teure Buchungen beibehalten werden sollen. Buchungen können auch über mehrere Tage getätigt worden sein.
Finde einen Algorithmus der die Zimmer so storniert, dass der Umsatz maximiert wird.

Uebertrag auf uns bekannte Algorithmen

Wir möchten das Problem als einen b-Fluss darstellen und diesen dann mit Hilfe der uns bekannten Algorithmen (z.B. Minimum-Mean-Cycle-Canceling Algorithmus) minimieren. Alle dann vom b-Fluss genutzten Kanten entsprechen den Reservierungen welche wir beibehalten.

Die Anzahl der Zimmer:

Die Anzahl der Zimmer legen wir mit \(Z\) fest.

Die Tage:

Jeder Tag wird durch einen Knoten \(v_i\) dargestellt, wir betrachten den Zeitraum von Tag \(v_1\) bis \(v_t\), \(1 \leq i \leq t\)

\(V = \{v_i : 1 \leq i \leq t\}\)

Die b-Werte:

Wir möchten, wenn möglich, jeden Tag alle Zimmer belegen. Da ein b-Fluss immer genausoviel Fluss hat wie \(b(s) = b(t)\) entscheiden wir uns dass:

\(b(e_1) = Z\)
\(b(e_t) = -Z\)
\(b(e_i) = 0\) \(\forall 1 < i < t\)

Das bedeutet dass jeden Tag \(Z\) Buchungen auslaufen und \(Z\) neue Buchungen getätigt werden müssen. Diese Erkentniss greifen wir gleich noch einmal auf.

Die Buchungen:

Jede Buchung wird durch eine Kante von Starttag zum Endtag der Buchung dargestellt. Dabei entspricht das Gewicht der Kante dem negierten Wert des Preises der Buchung.

Entspricht das Gewicht der Kante der Buchung müssten wir alle Kanten in den Graph aufnehmen welche maximal sind. Wir kennen allerdings nur Algorithmen um b-Flüsse mit minimalen Kosten zu ermitteln, daher müssen wir die Buchungskosten negieren.
\(e_{b_i} = (v_g, v_h)\), Kante welche die \(i\)-te Buchung von Tag \(g\) nach Tag \(h\) repräsentiert.
\(u(e_{b_i}) = 1\) gilt, da jede Buchung nur einmal akzeptiert werden kann.
\(c(e_{b_i}) = -(\)Buchungsgebühr der \(i\)-ten Buchung\()\)

Ein kleines Problem haben wir noch:
Sollten wir zwischen zwei Tagen weniger als \(Z\) Buchungen haben, können wir keinen b-Fluss von \(v_1\) nach \(v_t\) mehr finden, da irgendwo mittendrinne kein Fluss \(Z\) möglich ist.
Daher fügen wir zwischen zwei aufeinanderfolgenden Tagen eine weitere Kante mit Gewicht 0 und Kapazität \(Z\) ein. Somit ist gewährleistet dass ein \(Z\) Fluss immer möglich ist. Da alle anderen Kanten negatives Gewicht haben wird diese nur genutzt wenn keine weiteren Buchungen vorliegen.

\(e_{l_i} = (v_i, v_{i+1})\) \(\forall 1 \leq i < t\)
\(u(e_{l_i}) = Z\)
\(c(e_{l_i}) = 0\)

Dass es diese Kanten gibt ist insoweit praktisch, dass wir direkt eine Startkonfiguration für den b-Fluss haben. Zu Beginn des Algorithmus' welcher unseren b-Fluss minimieren soll fließt der Fluss komplett über diese Leerlaufkanten.

\(E = \{e_{b_i} : i\)-te Buchung \(\} \cup \{e_{l_i} : 1 \leq i < t\} \)

Nochmal in kurz:

  • Jeder Knoten stellt einen Tag dar.
    • Die b-Werte sind, außer beim ersten und letzten Tag, 0.
    • b-Wert des ersten Tages: Z
    • b-Wert des letzten Tages: -Z
  • Wir haben Kanten welche Buchungen darstellen sowie zwischen jeweils zwei aufeinanderfolgenden Tagen Leerlaufkanten um fehlende Buchungen auszugleichen.
    • Buchungskanten haben Kapazität 1 und als Gewicht die negierten Kosten der Buchung
    • Leerlaufkanten haben Kapazität Z und Gewicht 0
  • Wir suchen nun einen bezüglich der Kosten minimalen b-Fluss. Jede nicht in diesem b-Fluss genutzte Buchungdkante stellt eine zu stornierende Buchung dar.

Ein Beispiel:

Folgt demnächst...