Resolución mediante grafos del problema Yield Management aplicado a la gestión hotelera

V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 ƒ Índice Resolución mediante grafos del problema Yield Management aplicado a la gestión hotelera José Guadix1, Juan Larrañeta2, Luis Onieva3, Pablo Cortés4 y Jesús Muñuzuri5 1 Ingeniero Industrial, Ingeniería de Organización, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla. [email protected] 2 Doctor Ingeniero Industrial, Ingeniería de Organización, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla. [email protected] 3 Doctor Ingeniero Industrial, Ingeniería de Organización, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla. [email protected] 4 Doctor Ingeniero Industrial, Ingeniería de Organización, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla. [email protected] 5 Doctor Ingeniero Industrial, Ingeniería de Organización, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla. m[email protected] RESUMEN Yield Management es una técnica que cada vez está tomando más importancia en el sector servicios, debido a que la mayoría de las empresas que lo integran presentan simultaneidad en la producción y consumo del servicio prestado, junto con la imposibilidad de almacenamiento del producto por ser perecedero. Con esta técnica se busca vender cada unidad de inventario al tipo de cliente adecuado, en el instante preciso y al precio conveniente. En este trabajo se analiza el caso de aplicación de la técnica a la gestión hotelera, se recorre un camino que va desde los primeros modelos aplicados en el sector aéreo y se continúa proponiendo otros más avanzados y exclusivos para el caso de un hotel. Palabras clave: Yield Management, Grafos, Revenue Management, Hoteles. 1. Introducción. El concepto en el que se fundamentan las técnicas Yield Management (YM) se puede entender con facilidad centrándose en el sector hotelero. Yield se refiere a los ingresos por miles de plazas existentes o a los ingresos por miles de huéspedes. Los hoteles normalmente ofrecen distintos tipos de servicios, tales como Preferencial, Suite y Standard. Preferirían llenar sus hoteles con clientes de primera clase, pero esto raramente ocurre, por lo que tratan de cubrir las plazas libres ofreciendo otros servicios diferentes. Hay que llegar a un punto de equilibrio entre el uso máximo de la capacidad, que sería lo deseable, y la venta de las habitaciones al precio máximo. Debido a que las unidades que forman el inventario en los hoteles son perecederas, una habitación vacía en una noche tiene asociado un coste de oportunidad. Los hoteles deben decidir cuánto descontar al precio de los servicios para asegurar su venta, y al mismo tiempo estar seguros que dejan suficientes habitaciones libres para venderlas a los huéspedes que lleguen a última hora con intención de ocupar habitaciones de primera clase. Las empresas en las que resulta óptima la aplicación de esta técnica deben cumplir una serie de requisitos tales como estar dotadas de una capacidad fija, disponer de unas unidades de inventario (servicios) que se puedan segmentar con su precio y poder vender por adelantado estas unidades ofertadas. Además, los servicios ofertados son perecederos y presentan una V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 demanda fluctuante con el tiempo. Los posibles aumentos del número total de inventario son demasiado costosos. 2. Modelos de Resolución. Con estos modelos matemáticos se pretende determinar, a priori, cuantas unidades de inventario deberán asociarse a cada categoría. Se consideran como hipótesis para todos los modelos: x todas las reservas son utilizadas, es decir ninguna reserva se cancela. Esta hipótesis elimina el overbooking x independencia entre las demandas de las distintas categorías x inexistencia de grupos, son todos clientes individuales A continuación se distingue el estudio de los modelos según sea posible una estancia máxima de un día (estancia simple) o por el contrario se contemple la posibilidad de una duración de estancia decidida por la gerencia del hotel (estancia múltiple). 2.1 Estancias Simples. El primer estudio realizado sobre la base de este enfoque lo hizo Littlewood (1972). En esta primera aproximación, se divide el inventario en dos posibles categorías, la “2” con descuento y la “1” que ofrece los servicios sin descuento. El problema se reduce a determinar un límite a la cantidad ofrecida con descuento, y el resto será ofertado en la categoría superior. Se considera, como hipótesis de partida, que el inventario con descuento se vende antes que el inventario sin descuento, y que todas las reservas son utilizadas, es decir, ninguna reserva se cancela. Los parámetros que intervienen son: qT: capacidad total fija d1: variable aleatoria que estima el número de peticiones de reservas para unidades de inventario sin descuento r1: ingresos producidos por una unidad sin descuento r2: ingresos producidos por una unidad con descuento La variable a determinar es, x1: número de unidades de inventario sin descuento Se deben seguir ofreciendo unidades de inventario de la categoría con descuento mientras se cumpla la siguiente condición: >@ Prr dxt ! 21 1 1 (1) siendo P[ ] la probabilidad, en este caso, de que al llegar el momento de ofrecer el servicio no se tengan disponibilidades para atender la petición. V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 La consecuencia del resultado obtenido es que se continuará ofreciendo un servicio más con descuento, mientras los ingresos con descuento sean mayores o iguales a los ingresos esperados para la categoría superior (sin descuento). Otro modo de resolución del problema nace de la idea que considera que las empresas deben tener un número de unidades de inventario que potencien la demanda de consumidores de alto poder adquisitivo. Hay que alcanzar una distribución tal que el ingreso esperado por una venta adicional en la gama alta sea igual al nivel actual de ingresos que se tienen en la gama inferior. Esta distribución determina el número óptimo de servicios a asignar a cada categoría. La distribución óptima del inventario, se alcanza cuando el ingreso marginal de la venta del último servicio en una clase sea el mismo que el que se produce para cualquier otra. Este modelo del ingreso marginal esperado por servicio, se conoce con el nombre EMSR, correspondiente a las siglas de su nombre en inglés, formulado por Belobaba (1987). Se usa la demanda probabilística porque el número de peticiones esperadas, para cada categoría, se debe estimar de datos históricos. Para un ejemplo de dos categorías, “1” y “2”, se definen las variables: () ii bx : función de densidad definida como el número de reservas esperadas para la categoría i. 1 ()Px : la probabilidad de recibir x1 o más peticiones para la categoría 1. ri : los ingresos obtenidos por la venta de un servicio de la categoría i. Hay que maximizar la función ingresos totales, R: 11 2 2 1 n ii i R rx rx r x  ¦ (2) Para las dos categorías, la capacidad total se descompone en función de las ventas realizadas en las dos categorías, de modo que 12  Txqx . Los ingresos totales son función de la distribución que se elija, xi, por lo que interviene la función densidad. Operando en la función ingresos totales, se tiene: () () () ( ) () ( ) 11 2 2 11 2 1 111 2 2 1 T T RRxRx RxRqx rbx rbq x      (3) El modelo del ingreso marginal esperado por servicio, nos indica que el ingreso obtenido por cada categoría debe ser igual, es decir, ij ij RR E MSR EMSR xx ww ww (4) En nuestro caso, simplificado para solo dos categorías, R x w w1 0 . Luego operando resulta: . Expresión que indica que los ingresos marginales esperados por la venta de un servicio adicional en cada categoría deben ser igual a cero. () ()rPx rPx 112 2 0 V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 Si se expresa de otra forma: 12 21 () () Px r Px r (5) Se pueden relacionar fácilmente los ingresos de cada categoría con las probabilidades del número de peticiones de servicio en cada categoría. De esta manera, a partir de los precios a priori de cada categoría, se determina la relación de probabilidades de vender cada categoría. Como resultado de estos valores, se obtiene la distribución de la capacidad total en las distintas categorías. 2.2 Estancias Múltiples. Al incorporar el concepto de estancias múltiples al modelo se formula un problema de programación matemática para maximizar los ingresos obtenidos, una vez que se han previsto los clientes futuros. Asumimos que los precios en las distintas categorías y la demanda son deterministas. Por ello, la información de la demanda la tenemos desagregada en categorías, días de llegada y duración de la estancia o servicio. En el modelo usamos los siguientes parámetros: i, l, j : índices de fechas (i, l, j = 1,..., N) i, l se refieren al día de llegada j se refiere al día de partida (fin del servicio) k : índice de la categoría (k = 1,..., K) rk : ingresos en la categoría k bi : capacidad (número de habitaciones) del hotel en el día i dijk : demanda esperada para clientes que lleguen el día i, y finalicen la estancia el día j, en una categoría k Con las variables: xijk : número de servicios para una llegada el día i y salida el día j, i<j, en la categoría k. Se plantea el problema de la forma: ,, max ( ) s.a. i 0 entera k ijk ijk ljk i lii j k ijk ijk ijk jirx xb xd x d  d dd ¦ ¦¦¦ (6) V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 El criterio es tratar de maximizar los ingresos producidos por la venta de las xijk unidades. Esta maximización está sujeta a una serie de restricciones. En primer lugar, que la suma del número de unidades vendidas, que constituyen el inventario, debe ser cada día menor que la capacidad disponible. Por otro lado, para cada posible estancia, las ventas deben ser menores que la demanda esperada de clientes. Se obliga a que las variables xijk sean enteras. Es lógico, teniendo en cuenta que no es posible vender una fracción del servicio. Una primera forma de resolución del modelo (6) es con la relajación de las variables xijk a continuas. Con esta relajación, no se pierde mucha información, ya que como veremos más adelante, la mayoría de las variables resultarían enteras. Otra forma de resolver el modelo (6) es plantearlo como el flujo máximo en una red, problema propuesto para el sector aéreo por Glover (1982). En nuestro caso, sería similar al problema de trasbordo con capacidades en los arcos [Larrañeta (1987)]. El modelo se estructura mediante el grafo (,)GNA representando los nodos N los días de la estancia del hotel y los arcos A las posibles noches. Los arcos entre nodos los representamos dobles señalando la posibilidad de estancias en las distintas categorías k. Cada uno de estos arcos tienen su capacidad limitada por la demanda esperada dijk. En el ejemplo de la figura se supone una estancia máxima de dos noches, aunque se puede generalizar a S noches. Además, aparecen unos arcos que representan la capacidad bi y que no aparecen en la función objetivo, luego se le asigna un coste nulo. 1i-1 i j j+1 N Figura 1: Estructura del grafo G=(N, A). La función que hay que maximizar es ijk F , ( ) si ,, : 0 si k ijk jir jiS ijk A F ij     ®! ¯ d (7) Para comprobar la restricción de capacidad total del hotel, basta con realizar un corte entre dos nodos. 3. Análisis de los modelos múltiples. Dado que el problema estancias simples se puede considerar como uno particular de los tratados en este trabajo, solo analizaremos los segundos. Aunque como históricamente se trató V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 de forma diferenciada, se incluyeron los distintos modelos utilizados y se remite a un trabajo más amplio en Guadix (2003). A continuación solo se analizan los modelos propuestos para estancias múltiples. Ante una batería de 96 problemas, se estudiaron las soluciones de las variables xijk. Los datos de los modelos múltiples, las demandas para cada día, categoría y número de noches de estancias fueron generados aleatóriamente. Para ello se realizaron estudios para dos tipos de hoteles, uno de 200 habitaciones que representa un único hotel en una ciudad o un problema con 1000 habitaciones que sería para el caso de varios hoteles pertenecientes a una cadena. Asimismo se crearon dos posibilidades en las demandas de clientes, una en temporada alta con gran demanda y una temporada baja con una demanda inferior de algunas categorías. Además se probaron diferentes duraciones de estancias, con 180, 270 y 360 días. Cada uno de los 96 problemas generados aleatóriamente se resolvió con el programa CPLEX [ILOG CPLEX 8.0 (2002)] de las dos formas expuestas anteriormente. Mediante programación lineal (6), con los algoritmos primal y dual, y con el algoritmo de grafos (7) o network. En la tabla 1 se muestra el sumario de los resultados. Todos los tiempos de ejecución vienen expresados en segundos sobre un Intel Pentium III 850 MHz. Problema Soluciones Tiempo de Conmutación Total Nº de Iteraciones Solución Primal 0.06 96 Dual 0.06 13 ALTA1 Network 0.05 100 126270 Primal 0.05 2 Dual 0.06 2 BAJA1 Network 0.05 13 43260 Primal 0.22 1266 Dual 0.28 323 ALTA2 Network 0.04 3173 1077570 Primal 0.05 14 Dual 0.05 1 BAJA2 Network 0.01 97 540750 Tabla 1: Sumario de Resultados Promedios. Para el primer tipo de hotel al ser pequeño no se aprecia la diferencia en los tiempos de conmutación. Sin embargo, para el segundo se comprueba la ventaja obtenida al introducir el problema en forma de grafo. La solución obtenida de la función objetivo es la misma en todos los problemas resueltos por los tres métodos. Además se obtiene una información adicional al reparto óptimo de servicios (habitaciones). En concreto interesan las variables duales de las restricciones de capacidad total. Estas duales indican el precio que debería tener un servicio (habitación) que se agregue a los ya vendidos. Para ello, hay que suponer que se puede aumentar la capacidad en una unidad. Este precio dual reflejaría el mínimo necesario para que un nuevo cliente resultara beneficioso frente a la situación que ya se tiene. V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 A continuación se presenta como se puede exponer la información obtenida con las variables duales de las restricciones para uno de los casos resueltos. Para cada día se tiene un precio dual de la restricción de capacidad y unos precios ponderados para las distintas duraciones de estancias. ESTANCIAS PROBLEMA ALTA1 1 NT 2 NT 3 NT 1 NT 2 NT 3 NT 4 NT 5 NT DIA PRECIO DUAL 1 NT 2 NT 3 NT 4 NT 5 NT 60 € 90 € 1 0 0 0 30 45 54 2 0 0 45 60 68 72 3 90 90 90 90 90 108 X X X X 4 90 90 90 90 113 X X X X 5 90 90 90 120 X X X X 6 90 90 135 X X X 7 180 180 X X Tabla 2: Ejemplo de Variables Duales. En la fila del día 1 están abiertas todas las estancias en las dos categorías, debido a que siempre el precio ofrecido por los clientes es mayor que el dual ponderado. Mientras que si se observa la fila del tercer día, para la categoría inferior (60 €) no se admite ningún cliente nuevo, ya que los duales ponderados son mayores que el precio de la categoría. Sin embargo en la categoría superior (90 €), para estancias inferiores a cuatro noches si se admiten nuevos clientes, mientras que en la estancia de cinco noches ya influye el dual del día 7 que es muy elevado, por lo que hace que el dual ponderado sea superior al precio ofrecido y por consiguiente se cierra esta posibilidad de cliente. 4. Conclusiones En este trabajo se ha estudiado el problema de la gestión hotelera de clientes, diferenciando la duración de la estancia. Para estancias simples, tras exponer los distintos métodos conocidos se resolvieron varios ejemplos y se concluye que es un caso particular de las estancias múltiples. En el caso de estancias múltiples, se analizaron los distintos modelos y se estudiaron una amplia gama de problemas. Se ha comprobado como al ser capaz de intuir la presencia de un grafo en el modelo (6), y representarlo en la estructura expuesta en la figura 1, la resolución del problema halla la misma solución, aunque con un cómputo inferior en el tiempo. Las variables continuas obtenidas en la programación lineal resultan ser enteras, por lo que se puede afirmar que para modelos de Yield Management en hoteles el modelo (6) presenta unimodularidad. Asimismo, tras la implementación del problema lineal continuo, se obtiene el valor de las variables duales de las restricciones, y su significado posterior para la aceptación o rechazo de nuevos clientes. V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 Referencias [1] McGill, Jeffrey I., y Van Ryzin, Garrett J. (1999) “Revenue Management: research overview and prospects”, Transportation Science, vol 33, no 2, 233-256. [2] Littlewood, K. (1972) “Forecasting and Control of Passenger Bookings”, AGIFORS Symp. Proc., no 12, 95-117. [3] Belobaba, Peter P. (1987) “Airline Yield Management: An Overview of Seat Inventory Control”, Transportation Science, vol. 21, no 2, 63-73. [4] Glover, Fred; Glover, Randy; Lorenzo, Joe y McMillan, Claude (1982) “The PassengerMix Problem in the Scheduled Airlines”, Interfaces, vol. 12, no 3, 73-80. [5] Larrañeta, Juan (1987): Programación Lineal y Grafos. Publicaciones de la Universidad de Sevilla. [6] Guadix, José; Larrañeta, Juan y Onieva, Luis (2003) “Yield Management Aplicado a la Gestión de un Hotel”, 27 Congreso Nacional de Estadística e Investigación Operativa., Lérida. [7] ILOG CPLEX 8.0 (2002): User´s Manual.