Mathematical models for group revenue management

MATHEMATICAL MODELS FOR GROUP REVENUE MANAGEMENT José Guadix, Juan Larrañeta, Luis Onieva Industrial Organization and Management Department Industrial Engineering School – University of Seville Seville, Spain [email protected] Abstract – Revenue Management is a technique focus to decision rules for maximizing profit from sale of perishable inventory units. This paper deals with the special case of hotel revenue management, which can be solved using deterministic and stochastic mathematical programming techniques. We first describe the problem with a theoretical framework that sets the revenue maximization criteria for a hotel. We consider the general case of the problem that accept independent and group guests, with a general mixed integer linear programming model that maximize the total forecasting. Finally, we made comparisons between different proposed models and were found goodquality solutions in short running times. Keywords: Yield Management; Group Revenue Management; Hotels; Mathematical Models. I. INTRODUCTION Recent years have seen an increased interest in using yield management techniques to maximize profitability in capacity constrained situations. Most of the characteristics underlying this technique have been used before in different industries. Perishable firms, such as bakers, grocers, fresh fruit sellers or theatre managers, managed demand by varying prices in time. After US Airline Deregulation Act in 1978, any airline could operate any route at any frequency with whatever fares are chose, Smith et al. (1992). Companies adopted differentiated pricing in order to be able to compete for price sensitive travellers, without giving up the revenue from their existing, full fare customers. Yield management, also referred to as revenue management, is a sophisticated form of supply and demand management that balances both pricing and inventory to maximize revenue for every available unit of capacity. An increasing number of service industries have recognized the rapidly growing importance of yield management in their ability to increase sales, especially profitability. Services industries (such as airlines, hotels, rental car agencies, freight transport and broadcast advertising), have been able to market their services (seat on an aircraft, room in a hotel, rent a car, spaces on coaches or advertising time periods) as a perishable product. In this way, Yield Management can be defined as sell the right inventory unit to the right customer at the right time. For Yield Management to be applicable the service industry needs five conditions (Kimes 2000). 1. Limited capacity. Yield Management is designed for capacity-constrained services firms. The units of inventory are sold in a short time with a fixed capacity, measured by the number of rooms or the number of seats. 2. Market segmentation. Services industries make use of segmentation because these can choose between different types of customers. Arbitrary price is not allowed, so the service should have some characteristic that distinguish it. So the same unit of capacity can be used to deliver many different services. 3. Future demand is uncertain. Yield Management must be able to forecast the demand variability so that managers can increase the price during periods of high demand and decrease the price during periods of low demand. Services firms cannot quickly available capacity to available demand. 4. Perishable units of inventory. The inventory distinguishes service firms from manufacturing firms. Units of inventory services industries unsold after a specific date are wasted, services cannot be stored. These characteristics decide to sell services in advance. 5. Appropriate cost and pricing structure. Many services firms present a fixed capacity cost expensive and cannot be rapidly adjusted demand. In the same way additional cost associated to an additional visitor in unused capacity is very low. The revenue management models we study in this paper include group acceptance in hotels. Therefore, in this work we modelled the customer typology as individual or group. We tested a variety of different rooms optimization algorithms, based on deterministic and stochastic programming techniques. The paper is organized as follow. In Section 2 we study the particular case where the forecasting demand is deterministic, in which groups are allowed or not. In Section 3 we formulate the problem as a stochastic model, without and with groups. That case is close to real-world situations, so the results were better. Computational comparisons are described in Section 4, using linear programming and mixed integer linear programming problem. Finally, conclusions are drawn in Section 5. II. DETERMINISTIC MODEL Yield management has focused mainly on forecasting, reservation systems and optimization models. For a International Conference on Knowledge Engineering and Decision Support 375 compressive overview of the literature we refer to McGill and Van Ryzin (1999). The model needs to forecast the demand of customer and obtains the optimal allocation of rooms over the forecasted demand. Forecast is essentially in the hotel yield management system. For hotel forecasting we need historical information about arrivals by length of stay and rate category. We can use different methods (Lee, 1990): historical, advanced and combined booking models. Traditional forecasting techniques were: moving average bookings, exponential smoothing and ARIMA times series models. Advanced booking models is used to predict customer pickup, it is the incremental bookings received during a certain time interval. The chosen methods were additive and multiplicative models. Hybrid models can be regression methods in which independent variables were number of reservations on hand for a day particular day or economics parameters from customer countries and the dependent variable was the final number of rooms sold. It is not exit the best method, every hotel own particular characteristics, and a hotel may use a forecasting method depending on what period of calendar. In general terms regression model, linear or loglinear regression, will be a good fitted data. Unpublished studies used combination forecasts, After using a good forecasting model, the system relies on fills all available capacity and charges the highest unit price, this means that ensures that those customers most willing to pay for a room can do so. About optimization models, Williamson (1992) study the problem of maximizing revenue in the airline industry using a deterministic mathematical programming. In the hotel industry, let k denote departure day menus arrival day (length of stay), pj the rate class price, bi the capacity for the hotel on day i, dijk the demand forecasted to guest arriving on day i, staying during k days at j rate class and xijk the number of rooms reserved to guest with ijk characteristics. The hotel model is then formulated as follows: ,, () Maximize subject to 0 integer (DP) jijk ijk ljk i li j lk i ijk ijk ijk kpx xb i xd x ≤+> ⋅ ≤∀ ≤≤ ∑ ∑∑ ∑ The objective is to find the room allocation to maximize revenue from selling room and satisfies the capacity constraints in a hotel. This integer problem solves relaxing to a linear program because the constraint matrix is unimodular. The problem is able to solve with an associated network flow, nodes represent days and arcs represents rooms will sell to customers. In section 4 we show different examples compared the linear and network flow solution. We are thus solving a subproblem within an overall approach that integrates forecasting and reservation systems. In this way, it maximizes average profit per available unit, by anticipating the price sensitivity of different customers and anticipates selling to the highest paying customers. On the other hand, this process mitigates seasonality of demand, by shifting excess demand away from peak periods and into the off season. In these models we do not consider cancellations rooms, guests which no show after make a reservation. In due form, overbooking is not take into account here. Overbooking occurs when a hotel accepts more reservations than it has rooms available. It raises legal issues when hotel manager use airline overbooking as justification for the practice. The difference is that specific federal laws, which do not apply to hotels, govern the airline industry. An extension of this model introduced by Svrcek (1991) includes group reservation. Groups are special clients because usually bookings are with time, request blocks of rooms, need conference space and are sensitive about price. We will denote by i* the day of arrival, λ g number of days the group wants to stay, µ g group size, cg group rate and binary variable xg represent if acceptance or not this group. The group model is now formulated as follows: {} {} ,, () () Maximize subject to *,..., * *,..., * jijk gg gg ijk g ljk i g li j lk i ljk g g i g li j lk i ijk ijk kpx c x xb iii xxbiii xd λµ λ µ λ ≤+> ≤+> ⋅ ≤∀∉ + +≤∀∈ + ≤≤ ∑∑ ∑∑ ∑ ∑∑ ∑ + 0 {} integer 0,1 (DGP) ijk g x x∈ This problem will be a mixed-integer programming model. In real situations, the group rate is usually negotiated with tour operators or travel agents. During negotiation the tour operators contacts with the reservation supervisor and request a specific number of rooms for a time period. In addition, group needs extra services such as food and beverage, conference rooms, etc. In this request the hotel required the minimum profitable room for accept or reject decisions, and we will use it to consider for auction theories. A method to calculate the minimum group rate is solved this problem twice. The first time we find the revenue without group, it chooses the first model. Then we calculate the revenue with the group, we solve the second model. This difference reve- International Conference on Knowledge Engineering and Decision Support 376 nue value will be the minimum income that hotel needs to sell the room blocks the length of stay. Group requests could displace individual customers paying higher fares. Some group customers may occupy rooms with higher expected marginal revenue than others customers. But the total group revenue may be higher than selling these rooms to individual customers. III. STOCHASTIC MODEL In this section we assume that demand is stochastic, so the number of allocates rooms could be different from the forecasting rooms. Here we consider a stochastic programming with simple recourse problem. This case is equivalent to a separate objective function, a linear part or the left-hand side and functions of random variables in the right-hand side. These particular stochastic problems do not cause severe computational difficulties, Kall and Wallace (1994). De Boer et al. (2002) introduced a stochastic model for the airline industry. Suppose that the demand Dijk can take on only a limited number of discrete values { } ,1 ,2 , ... ijk ijk ijk r dd d<<< . This discrete values are possible scenarios depends on customer demand. ,, =1 , , , 1() ,1 ,1 ,,,1 , Max Pr( ) s.t. i =2,..., 0 integer S j ijk ijk r ijk r rijk S ljk r i rlijlki ijk ijk ijkr ijkr ijkr ijk r kp D d x xb xd xdd r S x =≤ +> − ⋅⋅ ≥ ⋅ ≤∀ ≤ ≤− ∀ ≥ ∑∑ ∑∑∑ ∑ (SP) In this model, the decision variables xijk,r is a integer variable which represent the part of demand Dijk that falls in the interval . Number of rooms reserved x ,1 , (, ijk r ijk r dd −] ) Pr( ) ijk ijk r ijk ijk r xd xd − === . However, ijk is divide in possible scenarios, so we will find the decision variables xijk,r. The solution of this model, xijk,r will be different to zero when xijk,r-1 is equal to dijk,r-1, i.e. Pr( the sum of x ,1 , ijk,r rooms sold to customers in S scenarios will be agree with the daily capacity constraint. We solve a linear problem relaxation of the stochastic model because the constraint matrix is unimodular in the same terms, so the solution consists of integer values. The deterministic model is a particular model because it considers only one demand scenario (over S possible). With three demand scenarios is enough to capture most of the extra revenue generated by extra customers. These demands are calculated from forecasting adding up and take away the standard deviation for every rate class price. Although we have used a stochastic model for individual customer, we can use it with group. In this model, the objective function has a stochastic term with the group revenue that is modelled as a deterministic demand. {} {} S ,, r=1 , , S** , r=1 ( ) S** , r=1 ( ) Max Pr( ) s.t. ,..., ,..., j ijk ijk r ijk r g g g g ijk g ljk r i g li j lk i ljk r g g i g li j lk i kp D d x c x xb iii xxb iii λµ λ µ λ ≤+> ≤+> ⋅⋅ ≥ ⋅ + ≤∀∉ +≤ ∀∈ + ∑∑ ∑ ∑∑∑ ∑ ∑∑∑ ∑ {} ,1 ,1 ,,,1 , - =2,..., 0 integer 0,1 ijk ijk ijk r ijk r ijk r ijk r g xd xdd r S x x − ≤ ≤∀ ≥ ∈ (SGP) + We solve the problem in similar way, needing the minimum group rate of a new group. So with a forecasting dijk the model built three different scenarios (with the standard deviations as limits) and could find it solving the model twice, in the same way of the deterministic mixed linear integer problem. Another possibility is working solving if the scenarios are more important than prices. Hence, the new group displace the less possibility scenario customers at first time, r=3. When this scenario is empty, the model going on to displace the below scenario. This way of operate was less real than the first one, so that we will not use it. IV. EXPERIMENTAL RESULTS The first stage in our computational experiences involved the construction of a set of problems. To construct a set of instances we considered a hotel with 200 identical rooms and we have tested the deterministic and stochastic programming models for individual customers and groups. Individual guests can be booked in five different rates, described in Table I. Table I- Individual Price Classes Class Price Premiere / Luxury fare 250 € Business / Superior fare 175 € Standard / Normal fare 125 € Economy / Discount fare 90 € Supereconomy / Superdiscount fare 75 € Others inputs were randomly generated the time horizon of problems has been within the interval [0, 180] or maximum length of stay within the interval [0, 21]. For each SP problem are used three scenarios; low, average and high. For the probabilities, we are checked International Conference on Knowledge Engineering and Decision Support 377 three possibilities: p1 0.8/0.6/0.4; p2 0.6/0.4/0.2 and p3 0.7/0.5/0.3. To test DP model and SP model, we solved the same set of problems using twice. Thus, four instances were randomly generated for each problem size, once for DP model and three, once for scenario, in the SP model. This means that in total we solved the SP model 24 times. To examine the impact of stochastic programming we solved the same set of problems using DP, DGP, SP and SGP models. In order to measure the effectiveness of the proposed models, the average results show in the figure 1. Computations were done using CPLEX as a solver. 4,68E+06 4,69E+06 4,70E+06 4,71E+06 4,72E+06 4,73E+06 4,74E+06 4,75E+06 4,76E+06 12345678 Instances Revenue (€) DP DGP SP SPG Figure 1- The average revenue for problems by the DP, DGP, SP and SGP models Note that the revenue obtained by DP is bigger than SP models. The difference between deterministic and stochastic models is called the expected value of perfect information, EVPI. It shows how much one could expect to win if one were told what would happen before making one’s decision. It measures the value of randomness, but it does not show that the deterministic models cannot function well. A small EVPI means that randomness plays a minor role in the model than if EVPI value is bigger. At the same time, group models obtained better solutions than individual models. Because if the tour operator offer is worse than the expected revenue of individual customers, manager hotel refuse the group. The percentage errors have been computed with respect the maximum revenue. The difference between them is less than 8%, so we will use SPG model to solve customer problems. Figure 2 shows the summary of time obtained by DP and the average time for SP and group models. The computing time required by the proposed models is very low. All running times are given in CPU seconds on an Intel Pentium III 850 MHz with 64 Mb of RAM. 0 0,5 1 1,5 2 2,5 3 3,5 4 12345678 Instances Time DP DGP SP SGP Figure 2- The average time for problems by the DP, DGP, SP and SGP models Note that: • DGP found best revenue solutions. Although with demands calculated from forecasting models, revenue decrease due to EVPI value. • With regard to computation time, the highest model is below four seconds. Therefore, we could conclude that the SGP model assures quite satisfactory results with low computing requirements, and hence it could be reasonably used to solve much greater problems. V. CONCLUSION In this paper, we have studied an inventory perishable problem under limited capacity, which is differentiated with price policies. First, we have considered a special case for the problem, which is modelled as deterministic programming. Then, stochastic programming has been used to solve the same case. The quality of the solutions improved, if models are compared. Computational results indicated that the SGP model finds solutions of very good quality in a reasonable computation time. REFERENCES [1] B. Smith, J. Leimkuhler and R. Darrow, “Yield Management at American Airlines”, Interfaces, Vol 22, No. 1 (January 1992), pp. 8-31. [2] S. Kimes, “A Strategic Approach to Yield Management”, in Yield Management: Strategies for the service industries, A. Ingold, U. McMahon-Beattie and I. Yeoman, Ed. Contiuum: London, 2000, pp. 3-14. [3] J. McGill and G. Van Ryzin, “Revenue Management: Research Overview and Prospects”, Transportation Science, Vol 33, No. 2 (May 1999), pp. 233- 256. [4] A. Lee, “Airline Reservations Forecasting: Probabilistic and Statistical Models of the Booking Process”, Massachusetts Institute of Technology, 1990, Ed. M.I.T. Libraries Theses Collection. [5] E. Williamson, “Airline Network seat inventory control: Methodologies and revenue impacts”, Mas- International Conference on Knowledge Engineering and Decision Support 378 sachusetts Institute of Technology, 1992, Ed. M.I.T. Libraries Theses Collection. [6] T. Svrcek, “Modeling Airline Group passenger Demand for Revenue Optimization”, Massachusetts Institute of Technology, 1991, Ed. M.I.T. Libraries Theses Collection. [7] P. Kall and S. Wallace, Stochastic Programming, 1994, John Wiley & Sons. [8] S. Boer, R. Freling and N. Piersma, “Mathematical programming for network revenue management revisited”, European Journal of Operational Research, Vol 137, (2002), pp. 72-92. International Conference on Knowledge Engineering and Decision Support 379 View publication statsView publication stats