Constant-Factor Algorithms for Revenue Management with Consecutive Stays

Stellen Sie sich vor, Sie sind der Manager eines belebten Bahnhofs oder einer beliebten Hotelkette. Jeden Tag kommen Tausende von Menschen an, die alle einen Sitzplatz oder ein Zimmer für einen bestimmten Zeitraum buchen wollen. Einige wollen die gesamte Reise; andere nur ein paar Stopps. Der Haken dabei? Sie haben eine begrenzte Anzahl an Sitzplätzen oder Zimmern, und sobald Sie einen weggegeben haben, ist er für diesen spezifischen Zeitraum weg. Dies ist das Herzstück des Netzwerk-Revenue-Managements: die Kunst zu entscheiden, wem man „Ja“ sagt und wem man „Nein“ sagt, um den meisten Umsatz zu erzielen, ohne die Kapazitäten für die zahlungskräftigen Kunden zu erschöpfen, die erst später eintreffen könnten.

In der Welt der Mathematik und Informatik ist dies ein klassisches Rätsel. Normalerweise ist der beste Weg, es zu lösen, die gesamte Zukunft zu betrachten, genau zu wissen, wer wann ankommen wird, und dann einen perfekten Zeitplan zu erstellen. Aber in der realen Welt können Sie die Zukunft nicht sehen. Sie müssen Entscheidungen im laufenden Betrieb treffen, einen Kunden nach dem anderen, ohne zu wissen, wer als Nächstes kommt. Dies wird als „Online-Problem“ bezeichnet. Jahrelang haben Mathematiker versucht, eine einfache, schnelle Regel zu finden, die garantiert, dass Sie einen ordentlichen Gewinn erzielen, auch ohne die Zukunft zu kennen. Die große Frage war: Können wir eine Strategie finden, die garantiert „gut genug“ ist (ein konstanter Bruchteil des bestmöglichen Ergebnisses), unabhängig davon, wie lang die Buchungen sind oder wie schwierig die Kunden sind?

Dieses Paper von Ming Hu und Tongwen Wu widmet sich genau dieser Frage. Sie untersuchen zwei verschiedene Arten, wie sich Kunden verhalten könnten. Im ersten Szenario ist es wie ein Zugticket: Sie nehmen den Fahrgast entweder an und weisen ihm einen bestimmten Sitzplatz zu, oder Sie lehnen ihn ab. Im zweiten, komplexeren Szenario ist es wie ein Boutique-Hotel oder Airbnb: Sie zeigen dem Kunden ein Menü der verfügbaren Zimmer, und er wählt dasjenige aus, das ihm am besten gefällt, basierend auf seinen eigenen Vorlieben. Die Autoren entwickelten neue, schnelle Computeralgorithmen, um diese Situationen zu bewältigen. Sie haben bewiesen, dass ihre Methoden mathematisch garantiert mindestens 63,2 % des Geldes verdienen, das ein „perfekter“, die Zukunft kennender Planer im einfachen Zugticket-Fall erzielen würde. Wenn Kunden aus einem Menü wählen dürfen, sinkt die Garantie auf 27,1 %. Selbst wenn die Aufenthaltsdauer zufällig und unvorhersehbar ist, schaffen ihre Algorithmen immer noch einen soliden Teil des potenziellen Umsatzes, was beweist, dass man kein Hellseher sein muss, um ein profitables Geschäft zu führen – man braucht nur die richtige Mathematik.

Das Rätsel der fehlenden Sitzplätze

Denken Sie bei dem Problem an ein riesiges, sich ständig veränderndes Puzzlespiel, bei dem sich die Teile ständig in ihrer Form verändern. In der „Annehmen-oder-Ablehnen“-Welt (wie beim Zugbeispiel) müssen Sie jedes Mal, wenn ein Fahrgast einen Platz von Station A nach Station F anfragt, sofort entscheiden: „Gebe ich ihnen Sitzplatz 101? Oder hebe ich ihn auf, um ihn für jemanden aufzubewahren, der ihn später vielleicht möchte?“ Wenn Sie ihn zu früh hergeben, könnten Sie eine große Gruppenbuchung verpassen. Wenn Sie sich zu sehr zurückhalten, lassen Sie den Sitzplatz für immer leer.

Die Autoren erkannten, dass man, anstatt die Zukunft vorherzusagen, einen cleveren Trick namens „Fluid Relaxation“ (Flüssigkeits-Relaxierung) anwenden kann. Stellen Sie sich vor, die Sitzplätze sind keine festen Blöcke, sondern eine fließende Flüssigkeit. Sie berechnen, wie viel von diesem „flüssigen“ Sitzplatz basierend auf Wahrscheinlichkeiten für verschiedene Arten von Reisenden reserviert werden sollte. Dann bauten sie einen „Proposal-Discarding“-Algorithmus (Vorschlag-Verwerfungs-Algorithmus). So funktioniert er in einfachem Deutsch:

Noch bevor ein Kunde überhaupt zum Schalter kommt, simuliert der Computer ein „Was-wäre-wenn“-Szenario. Er fragt jeden verfügbaren Sitzplatz: „Wenn ein Kunde dieses Typs auftauchen würde, wärst du bereit, ihn zu nehmen?“ Jeder Sitzplatz wirft eine Münze basierend auf der Mathematik, um zu entscheiden, ob er die Hand hebt. Wenn mehrere Sitzplätze die Hand heben, wählt der Computer denjenigen, der den meisten Umsatz generieren würde. Wenn niemand die Hand hebt, wird der Kunde höflich abgewiesen.

Aber hier kommt die magische Wendung: Selbst wenn ein Sitzplatz nicht für den echten Kunden ausgewählt wurde, tut der Computer so, als wäre er tatsächlich benutzt worden. Er markiert diesen Sitzplatz in seiner internen Simulation als „besetzt“. Dies hält die Mathematik ehrlich und verhindert, dass das System zu gierig wird. Dieser „virtuelle Besetzt“-Status stellt sicher, dass der Algorithmus nicht versehentlich einen Sitzplatz in seinen Berechnungen doppelt bucht, wodurch die Wahrscheinlichkeiten unabhängig und die Mathematik lösbar bleibt.

Wenn Kunden wählen dürfen

Der zweite Teil des Papers macht noch mehr Spaß, weil er die menschliche Wahl hinzufügt. Stellen Sie sich ein Hotel vor, in dem Sie nicht einfach ein Zimmer zuweisen, sondern dem Gast eine Liste von drei verfügbaren Zimmern zeigen: eines mit Aussicht, eines mit Balkon und eines, das günstiger ist. Der Gast wählt dann dasjenige aus, das ihm am besten gefällt. Dies ist das „BAM-basierte“ Szenario (Basic Attraction Model).

Dies ist schwieriger, da die Wahl des Gastes von der gesamten Liste abhängt, die Sie ihm zeigen. Wenn Sie ein luxuriöses Zimmer zeigen, entscheidet er sich vielleicht dafür. Wenn Sie ein luxuriöses Zimmer und ein günstiges Zimmer zeigen, entscheidet er sich vielleicht für das günstige. Die Autoren mussten eine neue Methode entwickeln, um die „virtuellen“ Entscheidungen des Computers mit den realen Entscheidungen des Gastes zu verknüpfen. Sie verwendeten eine Technik namens „Randomized Coupling“ (Zufällige Kopplung). Denken Sie an einen Zaubertrick: Der Computer generiert eine zufällige Liste von Zimmern, die angeboten werden, aber er tut dies so, dass mathematisch garantiert ist, dass die Wahl des Gastes mit dem Plan des Computers übereinstimmt, obwohl der Gast eine freie Wahl trifft.

Sie fanden heraus, dass der Algorithmus trotz der durch die Wahl entstehenden Komplexität weiterhin funktioniert. Im „Menü“-Szenario haben sie bewiesen, dass ihre Strategie mindestens 27,1 % des optimalen Umsatzes erwirtschaftet. Wenn die Aufenthaltsdauer auch zufällig ist (wie bei einem Gast, der sagt: „Ich bleibe vielleicht 2 Tage oder vielleicht 5“), sinkt die Garantie etwas stärker, bleibt aber positiv: 17,1 % für das Menü-Szenario und 39,9 % für das einfache Zug-Szenario.

Warum das wichtig ist

Vor diesem Paper waren die besten Garantien für diese Art von Problemen sehr schwach. Sie hingen davon ab, wie lange die Buchungen dauerten. Wenn Menschen sehr lange Reisen buchten, schrumpfte die Garantie gegen Null. Es war so, als würde man sagen: „Unsere Strategie ist großartig, außer Sie bleiben einen Monat, dann ist sie nutzlos.“

Die Autoren zeigten, dass dies nicht stimmt. Sie bewiesen, dass man eine „Konstanten-Faktor“-Garantie (Constant-Factor Guarantee) haben kann. Das bedeutet, dass Ihre Strategie, egal wie lange die Aufenthalte sind, egal wie viele Ressourcen Sie haben, immer einen festen, gesunden Prozentsatz des bestmöglichen Geldes einfährt. Sie zeigten auch, dass man im einfachen Fall nicht viel besser als 63,2 % werden kann (was beweist, dass es „schwer“ ist, näher an 100 % zu kommen), was bedeutet, dass ihre Lösung tatsächlich sehr nah an der bestmöglichen Antwort liegt, die wir erhoffen können.

Kurz gesagt: Sie haben ein unordentliches, unvorhersehbares Realweltproblem genommen und ihm ein solides mathematisches Rückgrat gegeben. Sie haben gezeigt, dass man mit dem richtigen Algorithmus nicht perfekt sein muss, um profitabel zu sein – man muss nur klug genug sein zu wissen, wann man „Ja“ sagt, wann man „Nein“ sagt und wie man Kunden wählen lässt, ohne sich das Geschäft zu ruinieren.