Constant-Factor Algorithms for Revenue Management with Consecutive Stays

Immaginate di essere il manager di una stazione ferroviaria frenetica o di una popolare catena alberghiera. Ogni giorno migliaia di persone si presentano, ognuna con il desiderio di prenotare un posto o una camera per un determinato arco di tempo. Alcuni vogliono l'intero viaggio; altri solo alcune fermate. Il problema è che avete un numero limitato di posti o camere e, una volta ceduto uno di essi, è andato per quel determinato intervallo di tempo. Questo è il cuore della Gestione dei Ricavi di Rete (Network Revenue Management): l'arte di decidere a chi dire "sì" e a chi dire "no", in modo da guadagnare il massimo senza esaurire l'inventario per i grandi spenditori che arriveranno più tardi.

Nel mondo della matematica e dell'informatica, questo è un classico enigma. Di solito, il modo migliore per risolverlo è guardare l'intero futuro, sapere esattamente chi arriverà e quando, e poi pianificare la tabella di marcia perfetta. Ma nel mondo reale, non si può vedere il futuro. Bisogna prendere decisioni sul colpo, un cliente alla volta, senza sapere chi verrà dopo. Questo è chiamato un problema "online". Per anni, i matematici hanno lottato per trovare una regola semplice e veloce che garantisse di incassare una cifra decente, anche senza conoscere il futuro. La grande domanda è stata: possiamo trovare una strategia che sia garantita essere "abbastanza buona" (una frazione costante del miglior risultato possibile) indipendentemente da quanto siano lunghe le prenotazioni o da quanto siano complicati i clienti?

Questo articolo di Ming Hu e Tongwen Wu affronta esattamente questa questione. Esaminano due diversi modi in cui i clienti potrebbero comportarsi. Nel primo scenario, è come un biglietto del treno: o accetti il passeggero e gli assegni un posto specifico, o lo rifiuti. Nel secondo scenario, più complesso, è come un boutique hotel o un Airbnb: mostri al cliente un menu di camere disponibili e lui sceglie quella che preferisce in base alle proprie preferenze. Gli autori hanno sviluppato nuovi algoritmi informatici veloci per gestire queste situazioni. Hanno dimostrato che i loro metodi sono matematicamente garantiti per incassare almeno il 63,2% del denaro che il "perfetto" pianificatore che conosce il futuro incasserebbe nel caso semplice del biglietto del treno. Quando i clienti possono scegliere da un menu, la garanzia scende al 27,1%. Anche quando la durata del soggiorno è casuale e imprevedibile, i loro algoritmi riescono comunque a garantire una solida fetta del potenziale ricavo, dimostrando che non serve essere dei sensitivi per gestire un'attività redditizia: basta avere la giusta matematica.

L'enigma dei posti mancanti

Pensate al problema come a un enorme puzzle variabile dove i pezzi cambiano forma continuamente. Nel mondo "Accetta-o-Rifiuta" (come l'esempio del treno), ogni volta che un passeggero chiede un posto dalla Stazione A alla Stazione F, dovete decidere istantaneamente: "Ti do il Posto 101? O lo tengo per qualcuno che potrebbe volerlo più tardi?". Se lo cedi troppo presto, potresti perdere una grande prenotazione di gruppo. Se lo tieni troppo stretto, potresti lasciare il posto vuoto per sempre.

Gli autori si sono resi conto che, invece di cercare di prevedere il futuro, si può usare un trucco astuto chiamato "rilassamento fluido" (fluid relaxation). Immaginate che i posti non siano blocchi solidi ma un liquido in movimento. Calcolate quanta parte di quel "liquido" di posto debba essere riservata a diversi tipi di viaggiatori in base alle probabilità. Poi, hanno costruito un algoritmo di "Proposta-Scarto" (Proposal-Discarding). Ecco come funziona in parole semplici:

Prima ancora che un cliente arrivi al bancone, il computer simula uno scenario "cosa succederebbe se". Chiede a ogni posto disponibile: "Se si presentasse un cliente di questo tipo, saresti disposto ad accoglierlo?". Ogni posto lancia una moneta basandosi sulla matematica per decidere se alzare la mano. Se più posti alzano la mano, il computer sceglie quello che genererebbe più denaro. Se nessuno alza la mano, il cliente viene gentilmente respinto.

Ma ecco il colpo di scena magico: anche se un posto non è stato scelto per il cliente reale, il computer finge che lo sia stato. Segna quel posto come "occupato" nella sua simulazione interna. Questo mantiene la matematica onesta ed evita che il sistema diventi troppo avido. Questo stato di "occupato virtuale" assicura che l'algoritmo non vada accidentalmente a doppiare un posto nei suoi calcoli, mantenendo le probabilità indipendenti e la matematica risolvibile.

Quando i clienti scelgono

La seconda parte dell'articolo è ancora più divertente perché aggiunge la scelta umana. Immaginate un hotel dove non assegnate semplicemente una camera, ma mostrate all'ospite una lista di tre camere disponibili: una con vista, una con balcone e una più economica. L'ospite sceglie poi quella che preferisce. Questo è lo scenario "basato su BAM" (Modello di Attrazione di Base).

Questo è più difficile perché la scelta dell'ospite dipende dall'intera lista che gli mostrate. Se mostrate una camera lussuosa, potrebbero sceglierla. Se mostrate una camera lussuosa e una economica, potrebbero scegliere quella economica. Gli autori hanno dovuto inventare un nuovo modo per collegare le scelte "virtuali" del computer con le scelte reali dell'ospite. Hanno usato una tecnica chiamata "accoppiamento randomizzato" (randomized coupling). Pensatelo come al trucco di un mago: il computer genera una lista casuale di camere da offrire, ma lo fa in un modo che garantisce matematicamente che la scelta dell'ospite sia allineata con il piano del computer, nonostante l'ospite stia compiendo una scelta libera.

Hanno scoperto che, sebbene questa scelta aggiunga complessità, il loro algoritmo funziona comunque. Nello scenario del "menu", hanno dimostrato che la loro politica incassa almeno il 27,1% del ricavo ottimale. Se anche la durata del soggiorno è casuale (come un ospite che dice: "Potrei stare 2 giorni, o forse 5"), la garanzia scende un po' di più, ma rimane positiva: 17,1% per lo scenario del menu e 39,9% per il semplice scenario del treno.

Perché questo è importante

Prima di questo articolo, le migliori garanzie per questi tipi di problemi erano molto deboli. Dipendevano da quanto fossero lunghe le prenotazioni. Se le persone prenotavano viaggi molto lunghi, la garanzia diminuiva fino a quasi annullarsi. Era come dire: "La nostra strategia è ottima, a meno che tu non resti per un mese, nel qual caso diventa inutile".

Gli autori hanno dimostrato che non è così. Hanno provato che è possibile avere una garanzia a "fattore costante". Ciò significa che indipendentemente dalla durata dei soggiorni, indipendentemente da quanti elementi si hanno a disposizione, la vostra strategia catturerà sempre una percentuale fissa e sana del miglior guadagno possibile. Hanno anche dimostrato che non si può fare molto meglio del 63,2% per il caso semplice (dimostrando che è "difficile" avvicinarsi al 100%), il che significa che la loro soluzione è in realtà molto vicina alla migliore risposta possibile che possiamo sperare di ottenere.

In breve, hanno preso un problema del mondo reale disordinato e imprevedibile e gli hanno dato una solida struttura matematica. Hanno dimostrato che con l'algoritmo giusto, non serve essere perfetti per essere redditizi; basta essere abbastanza intelligenti da sapere quando dire "sì", quando dire "no" e come lasciare che i clienti scelgano senza rimetterci le penne.