Constant-Factor Algorithms for Revenue Management with Consecutive Stays

Imaginez que vous soyez le gestionnaire d'une gare très fréquentée ou d'une chaîne d'hôtels populaire. Chaque jour, des milliers de personnes arrivent, chacune voulant réserver un siège ou une chambre pour une période spécifique. Certains veulent tout le trajet ; d'autres juste quelques arrêts. Le hic ? Vous disposez d'un nombre limité de sièges ou de chambres, et une fois que vous en avez donné un, il est épuisé pour ce créneau horaire précis. C'est le cœur du Revenue Management de Réseau : l'art de décider à qui dire « oui » et à qui dire « non », afin de maximiser vos revenus sans manquer de stock pour les gros clients qui arriveront plus tard.

Dans le monde des mathématiques et de l'informatique, c'est un casse-tête classique. Habituellement, la meilleure façon de le résoudre consiste à examiner tout le futur, savoir exactement qui arrivera et quand, puis à planifier l'emploi du temps parfait. Mais dans le monde réel, vous ne pouvez pas voir l'avenir. Vous devez prendre des décisions au fur et à mesure, client par client, sans savoir qui sera le suivant. C'est ce qu'on appelle un problème « en ligne » (online). Pendant des années, les mathématiciens ont lutté pour trouver une règle simple et rapide qui garantisse que vous gagnerez une quantité décente d'argent, même sans connaître l'avenir. La grande question était : peut-on trouver une stratégie qui soit garantie d'être « assez bonne » (une fraction constante du meilleur résultat possible) quels que soient la durée des réservations ou la complexité des clients ?

Cet article de Ming Hu et Tongwen Wu s'attaque précisément à cette question. Ils examinent deux manières différentes dont les clients peuvent se comporter. Dans le premier scénario, c'est comme un billet de train : soit vous acceptez le passager et lui attribuez un siège spécifique, soit vous le rejetez. Dans le second scénario, plus complexe, c'est comme un hôtel de charme ou un Airbnb : vous présentez au client un menu de chambres disponibles et celui-ci choisit celle qui lui plaît le plus selon ses préférences. Les auteurs ont développé de nouveaux algorithmes informatiques rapides pour gérer ces situations. Ils ont prouvé que leurs méthodes garantissent mathématiquement de gagner au moins 63,2 % de l'argent qu'un planificateur « parfait » connaissant l'avenir réaliserait dans le cas simple du billet de train. Lorsque les clients choisissent parmi un menu, la garantie tombe à 27,1 %. Même lorsque la durée du séjour est aléatoire et imprévisible, leurs algorithmes parviennent tout de même à sécuriser une part solide du revenu potentiel, prouvant qu'il n'est pas nécessaire d'être un voyant pour diriger une entreprise rentable — il suffit d'avoir la bonne approche mathématique.

Le puzzle des sièges manquants

Voyez ce problème comme un immense puzzle géant et mouvant dont les pièces changent de forme constamment. Dans le monde de l'« Acceptation ou Rejet » (comme l'exemple du train), chaque fois qu'un passager demande un siège de la Station A à la Station F, vous devez décider instantanément : « Est-ce que je leur donne le Siège 101 ? Ou est-ce que je le garde pour quelqu'un qui pourrait le vouloir plus tard ? » Si vous le donnez trop tôt, vous pourriez manquer une réservation de groupe importante. Si vous le gardez trop jalousement, vous pourriez laisser le siège vide pour toujours.

Les auteurs ont réalisé qu'au lieu d'essayer de prédire l'avenir, on peut utiliser une astuce ingénieuse appelée « relaxation fluide ». Imaginez que les sièges ne soient pas des blocs solides mais un liquide en mouvement. Vous calculez quelle quantité de ce « liquide » de siège devrait être réservée pour différents types de voyageurs en fonction de probabilités. Ensuite, ils ont construit un algorithme de « Proposition-Élimination » (Proposal-Discarding). Voici comment cela fonctionne en langage courant :

Avant même qu'un client n'arrive au comptoir, l'ordinateur simule un scénario de type « et si ». Il demande à chaque siège disponible : « Si un client de ce type se présentait, seriez-vous prêt à le prendre ? » Chaque siège lance une pièce basée sur les mathématiques pour décider s'il lève la main. Si plusieurs sièges lèvent la main, l'ordinateur choisit celui qui rapporterait le plus d'argent. Si personne ne lève la main, le client est poliment éconduit.

Mais voici le tour de magie : même si un siège n'a pas été choisi pour le vrai client, l'ordinateur fait comme s'il avait été utilisé. Il marque ce siège comme « occupé » dans sa simulation interne. Cela permet de maintenir l'honnêteté mathématique et d'empêcher le système de devenir trop gourmand. Ce statut de « occupation virtuelle » garantit que l'algorithme ne réserve pas accidentellement un siège en double dans ses calculs, maintenant ainsi l'indépendance des probabilités et la résolution mathématique.

Quand les clients choisissent

La seconde partie de l'article est encore plus amusante car elle ajoute le choix humain. Imaginez un hôtel où vous ne vous contentez pas d'attribuer une chambre ; vous présentez à l'hôte une liste de trois chambres disponibles : une avec vue, une avec balcon, et une moins chère. L'hôte choisit ensuite celle qu'il préfère. C'est le scénario « basé sur le BAM » (Modèle d'Attraction Basique).

C'est plus difficile car le choix de l'hôte dépend de la liste entière que vous lui présentez. Si vous lui montrez une chambre luxueuse, il pourrait la choisir. Si vous lui montisez une chambre luxueuse et une chambre bon marché, il pourrait choisir la moins chère. Les auteurs ont dû inventer une nouvelle façon de lier les choix « virtuels » de l'ordinateur aux choix réels de l'hôte. Ils ont utilisé une technique de « couplage aléatoire ». Voyez cela comme un tour de magicien : l'ordinateur génère une liste aléatoire de chambres à proposer, mais il le fait de manière à garantir mathématiquement que le choix de l'hôte s'alignera sur le plan de l'ordinateur, même si l'hôte fait un choix libre.

Ils ont découvert que, bien que ce choix ajoute de la complexité, leur algorithme fonctionne toujours. Dans le scénario du « menu », ils ont prouvé que leur politique rapporte au moins 27,1 % du revenu optimal. Si la durée du séjour est également aléatoire (comme un client disant : « Je pourrais rester 2 jours, ou peut-être 5 »), la garantie diminue un peu, mais reste positive : 17,1 % pour le scénario du menu et 39,9 % pour le scénario simple du train.

Pourquoi cela importe

Avant cet article, les meilleures garanties pour ce genre de problèmes étaient très faibles. Elles dépendaient de la durée des réservations. Si les gens réservaient pour de très longs voyages, la garantie s'effondrait presque jusqu'à néant. C'était comme dire : « Notre stratégie est excellente, sauf si vous restez un mois, auquel cas elle est inutile. »

Les auteurs ont démontré que ce n'est pas le cas. Ils ont prouvé que l'on peut obtenir une garantie de « facteur constant ». Cela signifie que peu importe la durée des séjours, peu importe le nombre de ressources dont vous disposez, votre stratégie captera toujours un pourcentage fixe et sain de l'argent le plus élevé possible. Ils ont également montré qu'on ne peut pas faire beaucoup mieux que 63,2 % pour le cas simple (prouvant qu'il est « difficile » de s'approcher de 100 %), ce qui signifie que leur solution est en réalité très proche de la meilleure réponse possible que nous puissions espérer.

En résumé, ils ont pris un problème du monde réel, désordonné et imprévisible, et lui ont donné une base mathématique solide. Ils ont montré qu'avec le bon algorithme, il n'est pas nécessaire d'être parfait pour être rentable ; il suffit d'être assez intelligent pour savoir quand dire « oui », quand dire « non », et comment laisser les clients choisir sans se ruiner.