Constant-Factor Algorithms for Revenue Management with Consecutive Stays

Imagina que eres el gerente de una estación de tren bulliciosa o de una popular cadena de hoteles. Cada día, miles de personas se presentan, cada una queriendo reservar un asiento o una habitación para un tramo específico de tiempo. Algunos quieren todo el trayecto; otros solo unos pocos paradas. El problema es que tienes un número limitado de asientos o habitaciones, y una vez que entregas uno, se ha ido para ese intervalo de tiempo específico. Este es el corazón de la Gestión de Ingresos de Red (Network Revenue Management): el arte de decidir a quién decirle "sí" y a quién decirle "no", para obtener la mayor cantidad de dinero sin quedarnos sin inventario para los grandes clientes que lleguen más tarde.

En el mundo de las matemáticas y la informática, este es un rompecabezas clásico. Usualmente, la mejor manera de resolverlo es observar todo el futuro, saber exactamente quién llegará y cuándo, y luego planificar el horario perfecto. Pero en el mundo real, no puedes ver el futuro. Tienes que tomar decisiones sobre la marcha, cliente a cliente, sin saber quién vendrá después. Esto se llama un problema "en línea" (online). Durante años, los matemáticos han luchado por encontrar una regla simple y rápida que garantice que obtendrás una cantidad decente de dinero, incluso sin conocer el futuro. La gran pregunta ha sido: ¿Podemos encontrar una estrategia que esté garantizada para ser "suficientemente buena" (una fracción constante del mejor resultado posible) sin importar cuán largas sean las reservas o qué tan complicados sean los clientes?

Este artículo de Ming Hu y Tongwen Wu aborda exactamente esa pregunta. Analizan dos formas diferentes en las que los clientes podrían comportarse. En el primer escenario, es como un billete de tren: o aceptas al pasajero y le asignas un asiento específico, o lo rechazas. En el segundo, más complejo escenario, es como un hotel boutique o un Airbnb: le muestras al cliente un menú de habitaciones disponibles y este elige la que más le guste según sus preferencias. Los autores desarrollaron nuevos algoritmos informáticos rápidos para manejar estas situaciones. Demostraron que sus métodos están matemáticamente garantizados para ganar al menos un 63.2% del dinero que el "planificador perfecto" que conoce el futuro obtendría en el caso simple del billete de tren. Cuando los clientes eligen de un menú, la garantía cae al 27.1%. Incluso cuando la duración de la estancia es aleatoria e impredecible, sus algoritmos logran asegurar una parte sólida de los ingresos potenciales, demostrando que no necesitas ser un psíquico para dirigir un negocio rentable: solo necesitas las matemáticas correctas.

El rompecabezas de los asientos faltantes

Piensa en el problema como un gigantesco rompecabezas de piezas móviles donde las piezas cambian de forma constantemente. En el mundo de "Aceptar o Rechazar" (como el ejemplo del tren), cada vez que un pasajero pide un asiento de la Estación A a la Estación F, tienes que decidir instantáneamente: "¿Le doy el Asiento 101? ¿O lo guardo para alguien que pueda quererlo más tarde?". Si lo entregas demasiado pronto, podrías perderte una gran reserva de grupo. Si te aferras demasiado, podrías dejar el asiento vacío para siempre.

Los autores se dieron cuenta de que, en lugar de intentar predecir el futuro, se puede usar un trucción inteligente llamada "relajación fluida" (fluid relaxation). Imagina que los asientos no son bloques sólidos, sino un líquido que fluye. Calculas cuánto de ese asiento de "líquido" debe reservarse para diferentes tipos de viajeros basándose en probabilidades. Luego, construyeron un algoritmo de "Propuesta-Descarte" (Proposal-Discarding). Así es como funciona en lenguaje sencillo:

Antes de que un cliente siquiera se acerque al mostrador, la computadora simula un escenario de "¿qué pasaría si...?". Le pregunta a cada asiento disponible: "Si apareciera un cliente de este tipo, ¿estarías dispuesto a aceptarlo?". Cada asiento lanza una moneda basada en las matemáticas para decidir si levanta la mano. Si múltiples asientos levantan la mano, la computadora elige el que generaría más dinero. Si nadie levanta la mano, el cliente es cortésmente rechazado.

Pero aquí está el giro mágico: incluso si un asiento no fue elegido para el cliente real, la computadora finge que sí fue utilizado. Marca ese asiento como "ocupado" en su simulación interna. Esto mantiene las matemáticas honestas y evita que el sistema se vuelva demasiado codicioso. Este estatus de "ocupado virtual" asegura que el algoritmo no reserve accidentalmente un asiento doble en sus cálculos, manteniendo las probabilidades independientes y las matemáticas resolubles.

Cuando los clientes eligen

La segunda parte del artículo es aún más divertida porque añade la elección humana. Imagina un hotel donde no solo asignas una habitación; le muestras al huésped una lista de tres habitaciones disponibles: una con vista, otra con balcón y una que es más barata. El huésped entonces elige la que más le gusta. Este es el escenario basado en BAM (Modelo de Atracción Básica).

Esto es más difícil porque la elección del huésped depende de toda la lista que le muestres. Si les muestras una habitación lujosa, podrían elegirla. Si les muestras una habitación lujosa y una barata, podrían elegir la barata. Los autores tuvieron que inventar una nueva forma de vincular las elecciones "virtuales" de la computadora con las elecciones reales del huésped. Utilizaron una técnica llamada "acoplamiento aleatorio" (randomized coupling). Piensa en esto como el truco de un mago: la computadora genera una lista aleatoria de habitaciones para ofrecer, pero lo hace de una manera que garantiza matemáticamente que la elección del huésped se alineará con el plan de la computadora, a pesar de que el huésped está tomando una decisión libre.

Descubrieron que, aunque esta elección añade complejidad, su algoritmo sigue funcionando. En el escenario del "menú", demostraron que su política obtiene al menos el 27.1% de los ingresos óptimos. Si la duración de la estancia también es aleatoria (como un huésped diciendo: "Podría quedarme 2 días, o tal vez 5"), la garantía cae un poco más, pero se mantiene positiva: 17.1% para el escenario del menú y 39.9% para el escenario simple del tren.

Por qué esto es importante

Antes de este artículo, las mejores garantías para este tipo de problemas eran muy débiles. Dependían de qué tan largas fueran las reservas. Si la gente reservaba viajes muy largos, la garantía se reducía casi a nada. Era como decir: "Nuestra estrategia es genial, a menos que te quedes un mes, en cuyo caso es inútil".

Los autores demostraron que esto no es cierto. Probaron que puedes tener una garantía de "factor constante". Esto significa que, sin importar cuán largas sean las estancias, sin importar cuántos recursos tengas, tu estrategia siempre capturará un porcentaje fijo y saludable de la mejor ganancia posible. También demostraron que no se puede hacer mucho mejor que el 63.2% para el caso simple (probando que es "difícil" acercarse al 100%), lo que significa que su solución es en realidad muy cercana a la mejor respuesta posible que podemos esperar.

En resumen, tomaron un problema del mundo real desordenado e impredecible y le dieron un sólido respaldo matemático. Demostraron que con el algoritmo adecuado, no necesitas ser perfecto para ser rentable; solo necesitas ser lo suficientemente inteligente para saber cuándo decir "sí", cuándo decir "no" y cómo permitir que los clientes elijan sin que pierdas el control de tu negocio.