Constant-Factor Algorithms for Revenue Management with Consecutive Stays

Stel je voor dat je de manager bent van een druk treinstation of een populaire hotelketen. Elke dag komen er duizenden mensen aan, die elk een zitplaats of een kamer willen boeken voor een specifieke periode. Sommigen willen de hele reis; anderen slechts een paar haltes. Het addertje onder het gras? Je hebt een beperkt aantal zitplaatsen of kamers, en zodra je er één weggeeft, is hij weg voor dat specifieता tijdslot. Dit is de kern van Netwerk Revenue Management: de kunst van het beslissen aan wie je "ja" zegt en tegen wie je "nee" zegt, zodat je de meeste winst maakt zonder dat je opraakt voor de grote betalers die later kunnen arriveren.

In de wereld van de wiskunde en informatica is dit een klassiek puzzelstuk. Meestal is de beste manier om dit op te lossen door naar de gehele toekomst te kijken, precies te weten wie wanneer zal arriveren, en dan een perfect schema te plannen. Maar in de echte wereld kun je de toekomst niet zien. Je moet beslissingen nemen on the fly, één klant tegelijk, zonder te weten wie de volgende is. Dit wordt een "online" probleem genoemd. Jarenlang hebben wiskundigen geprobeerd om een eenvoudige, snelle regel te vinden die garandeert dat je een redelijke hoeveelheid geld verdient, zelfs zonder de toekomst te kennen. De grote vraag was: kunnen we een strategie vinden die gegarandeerd "goed genoeg" is (een constant deel van de best mogende uitkomst), ongeacht hoe lang de boekingen zijn of hoe lastig de klanten zijn?

Dit artikel van Ming Hu en Tongwen Wu pakt exact die vraag aan. Ze kijken naar twee verschillende manieren waarop klanten zich kunnen gedragen. In het eerste scenario is het als een treinkaartje: je accepteert de passagier en wijst een specifieke zitplaats toe, of je wijst hem af. In het tweede, complexere scenario, is het als een boetiekhotel of Airbnb: je toont de klant een menu van beschikbare kamers en zij mogen de kamer kiezen die zij het beste vinden op basis van hun eigen voorkeuren. De auteurs hebben nieuwe, snelle computeralgoritmes ontwikkeld om deze situaties te beheersen. Ze bewezen dat hun methoden wiskundig gegarandeerd ten minste 63,2% van het geld verdienen dat de "perfecte", toekomstwetende planner zou maken in het eenvoudige treinkaartjesgeval. Wanneer klanten kunnen kiezen uit een menu, daalt de garantie naar 27,1%. Zelfs wanneer de duur van het verblijf willekeurig en onvoorspelbaar is, weten hun algoritmes nog steeds een solide deel van de potentiële omzet veilig te stellen, wat bewijst dat je geen helderziende hoeft te zijn om een winstgevende onderneming te runnen — je hebt alleen de juiste wiskunde nodig.

De Puzzel van de Ontbrekende Zitplaatsen

Denk aan het probleem als een gigantische, verschuivende legpuzzel waarbij de stukjes voortdurend van vorm veranderen. In de "Accept-or-Reject"-wereld (zoals het treinvoorbeeld) moet je elke keer dat een passagier om een zitplaats vraat van Station A naar Station F direct beslissen: "Geef ik ze Zitplaats 101? Of bewaar ik deze voor iemand die er later misschien behoefte aan heeft?" Als je de zitplaats te vroeg weggeeft, mis je misschien een grote groepsboeking. Als je te streng vasthoudt, laat je de zitplaats voor altijd leeg.

De auteurs realiseerden zich dat je, in plaats van de toekomst te proberen te voorspellen, een slimme truc kunt gebruiken die een "fluid relaxation" wordt genoemd. Stel je voor dat de zitplaatsen geen vaste blokken zijn, maar een stromende vloeistof. Je berekent hoeveel van die "vloeibare" zitplaats moet worden gereserveerd voor verschillende soorten reizigers op basis van waarschijnlijkheden. Vervolgens bouwden ze een "Proposal-Discarding"-algoritme. Zo werkt het in begrijpelijke taal:

Nog voordat een klant zelfs maar bij de balie staat, simuleert de computer een "wat als"-scenario. De computer vraat aan elke beschikbare zitplaats: "Als een klant van dit type zou verschijnen, zou je hen dan willen accepteren?" Elke zitplaats werpt een muntje op basis van de wiskunde om te beslissen of hij zijn hand opsteekt. Als meerdere zitplaatsen hun hand opsteken, kiest de computer de zitplaats die het meeste geld zou opleveren. Als niemand zijn hand opsteekt, wordt de klant beleefd afgewezen.

Maar hier komt de magische wending: zelfs als een zitplaats niet werd gekozen voor de echte klant, doet de computer alsof deze wel werd gebruikt. Hij markeert die zitplaats als "bezet" in zijn interne simulatie. Dit houdt de wiskunde eerlijk en voorkomt dat het systeem te hebberig wordt. Deze "virtuele bezette" status zorgt ervoor dat het algoritme per ongels niet dubbel boekt in zijn berekeningen, waardoor de waarschijnlijkheden onafhankelijk blijven en de wiskunde oplosbaar blijft.

Wanneer Klanten Kiezen

Het tweede deel van het artikel is nog leuker omdat het menselijke keuze toevoegt. Stel je een hotel voor waar je niet zomaar een kamer toewijst, maar een gast een lijst met drie beschikbare kamers laat zien: één met uitzicht, één met een balkon en één die goedkoper is. De gast kiest dan de kamer die hij het beste vindt. Dit is het "BAM-gebaseerde" scenario (Basic Attraction Model).

Dit is moeilijker omdat de keuze van de gast afhangt van de hele lijst die je laat zien. Als je een luxe kamer laat zien, kiezen ze die misschien. Als je een luxe kamer en een goedkope kamer laat zien, kiezen ze misschien de goedkere. De auteurs moesten een nieuwe manier uitvinden om de "virtuele" keuzes van de computer te koppelen aan de echte keuzes van de gast. Ze gebruikten een techniek genaamd "randomized coupling". Denk aan een goocheltruc: de computer genereert een willekeurige lijst met kamers om aan te bieden, maar doet dit op een manier die wiskundig garandeert dat de keuze van de gast overeenkomt met het plan van de computer, ook al maakt de gast een vrije keuze.

Ze ontdekten dat hoewel deze keuze extra complexiteit toevoegt, hun algoritme nog steeds werkt. In het "menu"-scenario bewezen ze dat hun beleid ten minste 27,1% van de optimale omzet oplevert. Als de duur van het verblijf ook willekeurig is (zoals een gast die zegt: "Ik blijf misschien 2 dagen, of misschien wel 5"), daalt de garantie iets meer, maar blijft deze positief: 17,1% voor het menu-scenario en 39,9% voor het eenvoudige treinscenario.

Waarom Dit Ertoe Doet

Vóór dit artikel waren de beste garanties voor dit soort problemen erg zwak. Ze waren afhankelijk van hoe lang de boekingen waren. Als mensen voor zeer lange reizen boekten, kromp de garantie tot bijna niets. Het was alsof zeggen: "Onze strategie is geweldig, tenzij je een maand blijft, dan is hij nutteloos."

De auteurs toonden aan dat dit niet waar is. Ze bewezen dat je een "constant-factor" garantie kunt hebben. Dit betekent dat ongeacht hoe lang de verblijven zijn, ongeacht hoeveel middelen je hebt, je strategie altijd een vast, gezond percentage van de best mogende winst zal pakken. Ze toonden ook aan dat je niet veel beter kunt doen dan 63,2% voor het eenvoudige geval (wat bewijst dat het "moeilijk" is om dichter bij de 100% te komen), wat betekent dat hun oplossing eigenlijk heel dicht bij het best mogende antwoord ligt dat we kunnen hopen te krijgen.

Kortom, ze namen een rommelig, onvoorspelbaar echt scenario en gaven het een solide wiskundige ruggengraat. Ze lieten zien dat met het juiste algoritme, je niet perfect hoeft te zijn om winstgevend te zijn; je moet alleen slim genoeg zijn om te weten wanneer je "ja" zegt, wanneer je "nee" zegt, en hoe je klanten laat kiezen zonder dat je de controle over je zaken verliest.