INTRODUCTION

In today’s competitive business market, many companies have focused on developing their business practices in order to sustain their profitability in an uncertain market. The ability to increase revenue through effectively managed customer relationships can help companies overcome the uncertain nature of demand. However, in hospitality organizations, where revenue management (RM) is widely practiced, applying both customer relationship management (CRM) and RM practices may lead to some difficulties. This effect arises because of different objectives, time horizons, performance indicators and managerial insights of these two business strategies. In this article, we develop a practical approach to consider these strategies in an integrated structure to balance different objectives in order to create sustainable profitability over the long-term horizon.

RM versus CRM

RM is defined as the application of information systems and pricing strategies to allocate the right capacity to the right customer at the right price at the right time (Kimes and Wirtz, 2003). First developed by the US airlines industry, RM is used to find optimal inventory allocation and price setting for perishable assets so as to maximize revenue within the planning horizon (McGill and van Ryzin, 1999). Following the remarkable success of RM practices in the airline industry (Chatwin, 1998; Lieberman, 2003), it was soon adopted by other capacity-constrained industries such as hotels, air cargos, cruise lines, restaurants and other industries with the following characteristics: perishable inventory, restricted capacity, volatile demand, micro-segmented markets, availability of advanced reservation and low variable to fixed cost ratio (Wirtz et al, 2003). Especially in the hotel industry, RM is known as standard operating procedure and there is adequate evidence that indicates the success of applying RM techniques in the hotel RM environment (Cross, 1997; Jones, 2000).

On the other hand, by understanding the importance of customers in making long-term profit, hotels have increasingly deployed customer relationship strategies in an endeavor to increase customer loyalty and maximize long-term profit (Noone and Kimes, 2003). CRM focuses on the management of profitable customer relationships in order to identify and retain the most profitable customers and improve the profitability of less profitable customers (Ryals et al, 2000). Studies within this area have been constructed based on the links between customer retention, customer profitability and customer lifetime value (CLV), which have encouraged companies to consider their customer as a ‘valuable asset’. Hence, the longer a company keeps its customers, the more profit it can gain from them (Kutner and Cripps, 1997; Gupta and Lehmann, 2003).

Despite the success of RM in maximizing revenue in the short term, concerns regarding its effects on customer relationships have been cited by many authors (Kimes and Wirtz, 2003; Shoemaker, 2003; Wirtz et al, 2003). RM may have both positive and negative impacts on key account relationships (Wang and Bowie, 2009). Although RM can significantly help the process of identifying the profile and value of key accounts, it may cause some potential customer conflict such as customer perceptions of unfairness and mistrust (McMahon-Beattie et al, 2002; Wang, 2012).

Furthermore, practice of RM and CRM shows some managerial conflicts. From the revenue managers’ viewpoint, maximizing day-to-day revenue generated by effectively perishable capacity allocation is the highest priority, whereas the goal of CRM is to increase the volume of business through long-term customer relationships. They also have different performance indicators; the efficiency of RM is measured by revenue per available room on a daily basis, whereas that of CRM is assessed by revenue per available customer over a longer period of time (Wang, 2012) or CLV (Shoemaker and Lewis, 1999). CLV can be defined as ‘the sum of cumulative cash flows of a customer over his or her lifetime with the company’ (Kumar et al, 2004). Several methods have been proposed for the calculation of CLV such as Recency, Frequency, Monetary Value Share-of-Wallet and Past Customer Value (Berger and Nasr, 1998; Aaker et al, 2003; Kumar and Reinartz, 2005).

Importance of RM and CRM integration

Having mentionedthe differences in RM and CRM objectives, however, it is strongly suggested that RM and CRM should be considered as complimentary business strategies, and the importance of integration of these two strategies has been noted by a number of studies (Belobaba, 2002; Lieberman, 2002; Noone and Kimes, 2003; Milla and Shoemaker, 2008; Wang and Bowie, 2009). It is suggested that revenue managers should consider some of the CRM factors such as customer profitability and CLV in their decision making. The managerial conflicts can be considerably reduced by increasing mutual understanding between RM and CRM managers (Wang and Bowie, 2009).

In particular, Noone and Kimes (2003) have dedicated their work to the integration of RM and CRM in the context of hotels. They have suggested using CLV as a measure of ranking customers in order to identify the value of different customer groups based on their lifetime profitability. Thus, the hotel customers were segmented into four groups based on the two factors of customer profitability and customer lifetime, and appropriate RM strategies were suggested for each group. According to their study, the customers with high lifetime and high profitability were known as ‘true loyal customers’ and RM strategies such as life-time value-based pricing and room availability guarantee (RAG) were proposed for this group of customers. In the current study an approach is developed to apply RM techniques by considering some CRM policies.

Hotel RM tools

Dividing them into pricing and non-pricing tools, Ivanov and Zhechev (2012) reviewed and classified the literature on RM techniques in the context of the hotel and hospitality industry. According to their classification, hotel inventory management is a non-pricing tool including four different categories: capacity management, overbooking, length of stay control and RAG.

Capacity control and overbooking are two basic components of RM. Capacity control decides which product requests should be accepted during booking periods. Since not all reservations necessarily show up, to reduce the risk of being faced with a number of empty units of capacity, the capacity is oversold. Clearly these two decisions are completely interrelated (Karaesmen and van Ryzin, 2004). The majority of studies in the field of hotel capacity control are dedicated to single-night stay only, though according to Weatherford (1995) taking the length of stay into account can increase revenue by as much as 2.94 per cent. However, considering multi-night stay may result in more complexity for solving the problem and put the problem into the category of network revenue management (NRM) problems. RAG is also a policy that is offered by some hotels as part of their loyalty programs. This policy will prevent the migration of oyal customers to competitors due to lack of inventory availability (Noone and Kimes, 2003). To the best of our knowledge, there is no study in which these four policies are considered jointly in a dynamic environment. In the current article, a structure is proposed to consider all four policies mentioned in an integrated manner.

The capacity control literature is quite extensive per se. (see Talluri and van Ryzin, 2004). Because of the interaction of capacity control and overbooking, joint models of capacity control and overbooking have received attention in recent years, especially in the airline industry (Chatwin, 1999; Subramanian et al, 1999). Bertsimas and Popescu (2003) extended the joint problem for a general network. They also presented a new algorithm based on deterministic linear programming (LP) to approximate a solution for dynamic programming. Erdelyi and Topaloglu (2009) formulated a capacity allocation and overbooking model over an airline network and dedicated their attempts to decompose the problem by itineraries using a separable approximation. Erdelyi and Topaloglu (2010) also decomposed the same problem based on a single-leg problem.

In this article, an NRM model with CRM consideration is developed to make capacity control and overbooking decisions simultaneously. CRM strategies include loyalty programs to persuade loyal customers to continue their loyalty behavior toward the hotel. In this regard, room availability is guaranteed for loyal customers. That is, instead of booking some weeks before the staying dates, loyal customers are permitted to make a reservation just a few hours before their stay. The rates offered to loyal customers are also lower than the normal rates to persuade them to make more purchases in future, especially in low-demand seasons. The joint capacity control and overbooking problem is formulated within the framework of stochastic dynamic programming.

We have mainly constructed our work based on the Erdelyi and Topaluglu formulation by adopting a deterministic LP for the problem with loyalty programs. We develop a deterministic LP to obtain approximate solutions for dynamic programming. The LP model is also designed to encompass loyalty programs. We investigate whether this LP provides an upper bound on the optimal solution of the dynamic programming model. Moreover, algorithms originally developed by Talluri and van Ryzin (1998) and that of Bertsimas and Popescu (2003) are merged to our deterministic LP to provide two approximation methods for estimating solutions for the main dynamic programming model.

Guaranteeing room availability for loyal customers while offering them lower prices is a persuasive act expected to decrease net revenue in the short term, particularly in high-demand seasons. Therefore, we need to investigate whether implementing these loyalty programs has the capability to increase net revenue in the long term. Accordingly, we design a structure to examine the effect of implementing loyalty programs on loyal customers’ future purchases in low-demand seasons. Considering a long-term horizon, the net revenue that is expected to decrease should be compensated by the increases in net revenue due to increase in loyal customers’ purchases in low-demand seasons.

Spending on customer acquisition and CLV is currently an active area of research in CRM, while it is a relatively new one in RM. The difference between CLV and willingness to spend has been brought to light by Pfeifer and Ovchinnikov (2011). It is argued that as an attempt to prevent double counting, only direct cash flows should be summed up when calculating CLV. This multifaceted area of research has also been focused on by analytical case-based models. For instance, Ovchinnikov et al (2014) discusses the trade-off between the cost of retaining old customers and that of acquiring new ones. This article focuses on analyzing a case in which the integration of RM and CRM is required for balancing the firm’s investment in different customer types. Ovchinnikov et al (2014) also investigate managerial biases by designing a behavioral experiment that leads to introducing a substitute concept for CLV.

RM problems in which promotions and discounts are offered to the customer necessitate customer behavior modeling. For example, Ovchinnikov and Milner (2012) develop two different types of customer learning models to be deployed in analyzing a problem in which customers expect end-of-period deals at discount. In this article, as the market is segmented into two well-defined customer types, the strategic behavior of customers will not change the price they pay (for a more comprehensive review of customer behavior modeling, Shen and Su, 2007, is suggested). In contrast to the research studies mentioned, there is another paper that almost perfectly matches the case we are to study. Liu (2007) discusses the long-term impact of loyalty programs on customer purchase behavior. The researcher argues that loyalty programs increase not only purchase frequency, but also transaction size. Moreover, the author concludes that there is a positive impact of loyalty programs on customers’ loyalty life cycle as well as their profitability.

Application perspectives

RM is known as a standard operating procedure that hotels use to maximize their day-to-day revenue. On the other hand, the role of customers in creating sustained profitability in competitive market should not be neglected. As mentioned above, from both the managerial (internal) and customer (external) point of view, there are some conflicts between RM and CRM practices. Although hotel managers emphasize maximizing revenue on a daily basis, account managers believe that opportunistic techniques of RM may destroy customer relationships and lead to perceptions of unfairness. This effect may result in decrease in long-term profitability. Therefore, it is worthwhile to consider these strategies as a complementary business plan in order to create a balance between CRM and RM goals. Especially on high-demand days, considering the value of customers during the booking process is a critical decision. This integration demands mutual understanding between the managers and can lead to sustained profitability in the long term. Thus, in this study the focus is mainly on the integration of CRM business strategies in the context of hotel RM.

In this article the following contributions are presented: (i) A dynamic model integrating RM and CRM is developed to make decisions on capacity allocation and overbooking simultaneously for the NRM problem. Loyalty programs are also considered in the dynamic programming model. The loyalty programs ensure that room availability is guaranteed for loyal customers based on the loyal CLV and incentive rates offered to them. (ii) Limiting the booking process to the periods before the planning horizon is a common assumption in the literature. In contrast, in this article the booking process begins a number of weeks before the planning horizon and will be continued up to the end of the last night. Accordingly, loyal customers are allowed to make reservations whenever they like within the decision periods. (iii) A deterministic LP is developed based on the problem formulation in which RAG for loyal customers is considered. It is proved that this LP provides an upper bound on the dynamic programming optimal solution. (iv) Two efficient approximation methods based on the deterministic LP are presented to estimate the optimal solution. The computational results are also provided and compared in terms of time and quality of solutions. (v) An analytical structure is designed to investigate whether implementing loyalty programs is capable of increasing revenue in the long term. We divide an annual horizon into the high-demand seasons and low-demand ones to study how implementing these programs may affect loyal customer purchases in low-demand seasons. Then we investigate a trade-off between decrease in short-term revenue and potential increase in long-term revenue due to more purchases in low-demand seasons in order to examine whether loyalty programs are economically justifiable in the long term. The effect of different parameters on the cost-effectiveness of the loyalty programs is also studied.

The remainder of the article is organized as follows. In the next section, we define the problem and present a dynamic programming formulation for the joint overbooking and capacity control problem over a hotel network considering RAG for loyal customers. In the section after that a deterministic LP is developed for the problem in which the loyalty program is considered. Then we present a proof that shows that this linear program provides an upper bound on the dynamic programming optimal solution. In the subsequent section, two approximation methods based on the deterministic LP are presented. In the following section computational experiments are presented. The analytical structure is proposed to study the cost-effectiveness of loyalty programs in the next section. Finally, in the penultimate and final sections we present an analytical discussion and summarize the conclusions of the study, respectively.

PROBLEM STATEMENT

Consider a hotel with c identical rooms. The requests for booking arrive randomly during the booking horizon. The objective is to decide about capacity allocation and overbooking decisions for a high-demand season in order to maximize total profit. Without loss of generality, hotel customers are divided in two major groups of occasional and loyal passengers. The first group of customers purchase occasionally. Because of their distinctive willingness to pay, they can be categorized into different booking classes. The hotel charges each class a predefined price regarding its members’ willingness to pay. Loyal customers are the hotel’s most profitable ones who purchase frequently and generate a significant portion of the hotel’s annual income.

A product is defined by three characteristics: check-in date, check-out date and booking/loyalty class. We assume n products can be defined during the m-nights horizon and J denotes the set of all products. We index each product by j and each night by i. The consumption matrix is given by A=[a ij ] where a ij =1 if the product j consumes ith night capacity, and a ij =0 otherwise.

The price that the hotel charges for product j is f j . Every time a request for product j arrives, we need to decide whether to accept or reject it. An accepted request becomes a reservation and generates revenue f j . We need to allocate the capacity through the booking process in order to maximize the total expected revenue generated by accepted requests.

Overbooking

Each reservation for product j shows up at the beginning of its check-in day with a probability of q j . Ji stands for the set of products that their check-ins are at the beginning of day i, x j represents the total number of accepted requests for product j(j∈Ji), and Sj(x j ) denotes the number of customers related to product j who show up at the beginning of day i. Given the assumption that show-up decisions of different reservations are independent, Sj(x j ) has binomial distribution with the parameters (x j , q j ).

When a reservation does not show up, his allocated room may remain empty. In order to reduce the risk of empty rooms at a high-demand horizon, the hotel management may oversell the capacity. That is, the hotel may accept more reservations than the actual capacity. If the number of reservations who show up exceeds the remaining capacity, we need to decide which reservation should be denied and which one should be accommodated. If a reservation for product j shows up while the hotel denies giving service, then a denied reservation penalty cost of θ j will be incurred to the objective function. This penalty may include the cost of late booking for a similar product at a comparable hotel and transportation cost. Obviously, the penalty θ j is always greater than f j .

Booking horizon

We are planning for a high-demand horizon, which contains m nights. The booking process begins a number of time periods before the first staying night and continues up to the end of (m−1)th night. The product requests arrive during the time periods T to 1, which is indexed by t and counted backwards. The probability that there is a request for product j at time period t is p jt . At most one request can arrive during each period. Thus, the condition p0t+∑j=1np jt =1 should be satisfied, in which p0t is the probability that no request arrives at period t. According to Figure 1, there are τ periods during each staying night. In addition, there are T′ periods before the beginning of planning (staying) horizon. During these T′ periods, requests for all products can be received. Clearly, during the periods that overlap with the staying horizon, only requests for those products whose check-in dates have not already reached are possible.

Figure 1
figure 1

The booking periods before and during the staying horizon.

Full size image

Loyalty programs

As previously mentioned, loyal customers generate a large proportion of annual revenue. As an attempt to maintain their profitability, the hotel should plan based on CRM principles. Accordingly, the hotel adapts loyalty programs to encourage loyal customers to continue their purchase behavior. We assume that the hotel has established loyalty programs and used a specific measurement to identify the loyal customers. For example, in some cases customers who stay more than 70 nights in each year are known as loyal customers and special advantages are given to this group of customers. In order to consider these programs, incentive discount rate and RAG for loyal customers are adopted.

Incentive discount rate is the rate that loyal customers should pay and is less than the lowest booking class rate for a similar product. Indeed, loyal customers pay η times the lowest class price (η<1) for similar room-nights.

The RAG ensures that when a loyal customer requests a specific product, the hotel has to accept this booking request. This guarantee is a more challenging problem in the high-demand periods. During these periods, demand is usually higher than the hotel capacity, and most of the customers book their products several weeks earlier than their arrival time. In such cases, RAG forces hotel management to keep some rooms empty in order to give service to loyal customers. Especially in our problem, these customers pay less than others and this can lead to reduced revenues in short-term horizons. On the other hand, loyal customers have higher expectations because of their purchase behavior, and if the hotel does not meet their expectations, it may end up losing them. This effect may result in a significant reduction in long-term revenue. Therefore, the hotel management should create a balance between these two types of losses in an effort to maximize long-term revenue.

To apply this guarantee in the model, we suppose that if the hotel rejects a loyal customer request, the customer’s loyalty behavior may not continue, and the hotel may lose the customer’s profitability. Therefore, a substantial penalty will be incurred to the maximization problem objective function. The amount of this penalty is equal to the expected revenue the hotel could have earned if the customer were to have continued his purchase behavior. Given that the loyal customer’s lifetime value during his remaining lifetime is calculated using the methods available in the literature and is denoted by LV, to approximate this penalty, we consider three scenarios as follows:

  1. a)

    If a loyal customer request is rejected, the hotel will lose the customer forever with the probability of μ 1. The current remaining lifetime value will be denoted by LV 1, and is equal to 0.

  2. b)

    If a loyal customer request is rejected, the loyal customer purchase behavior will be reduced in terms of volume and frequency of purchase with the probability of μ 2. The current remaining lifetime value will be denoted by LV 2(LV 2<LV).

  3. c)

    If a loyal customer request is rejected by the hotel, his purchase behavior and remaining lifetime value will not change.

Thus, the expected value of loyalty cost is shown by β and can be calculated as follows:

We define the loyalty cost vector as Λ=[λ j ]. This penalty cost is related to the products for loyal customers, and therefore λ j is defined by the following statement:

This penalty is a virtual cost in the high-demand horizon because it is not paid directly in the short term and is concerned with probable revenue loss in the future. However, because of the loyal customers’ importance to the hotel’s profitability, this virtual penalty is taken into account during the booking process.

Model formulation

As mentioned earlier, a model is developed to control and allocate the capacity while considering overbooking policies as well as the loyalty programs. The objective is to maximize total expected net revenue, defined as the difference between the expected revenue obtained by accepting product requests and the expected penalty costs incurred either by denying reservations or rejecting the loyal customers’ requests. To do this, we use a model similar to what Erdelyi and Topaloglu (2009) have suggested for the joint problem in airline networks. Since there are differences between airline and hotel networks, we need to adjust the model to the hotel environment. In addition to their work, the loyalty programs are considered in our model.

For this purpose, we develop a stochastic dynamic programming model to allocate the hotel’s capacity to different classes. We also make overbooking decisions through a mathematical programming model. The expected value of this mathematical programming is considered as the boundary condition of dynamic programming. Accordingly, these two types of decisions are made simultaneously by the model.

The state variable vector is denoted by x t ={x jt : j=1, 2, …, n} and defined as the total number of reservations for product j at the beginning of time period t. The decision stages are the booking periods {T, T−1, …, 2, 1}. Two types of decisions should be made: (i) which booking request should be accepted and recorded as a reservation during the booking process and (ii)which showed-up reservations should be denied if the number of reservations who show up exceeds the remaining capacity. We use S(x)={Sj(x j ): j=1, 2, …, n} to denote the state of the reservations who show up at their corresponding check-in dates at the end of the booking horizon. Given that S(x) reservations show up at the end of the booking horizon, we can compute the penalty cost associated with the denied reservations by solving the following problem stated in (3)–(6):

where y j is the number of denied reservations for product j. The objective function of the problem minimizes the penalty cost associated with denying the reservations. Constraints denoted as (4) are the capacity constraints that ensure that the number of customers who are allowed to stay at the hotel does not exceed the capacity. Constraints (5) state that the numbers of denied reservations for product j do not exceed the numbers of reservations that show up to receive their service. Given that e j is a jth unit n-dimensional vector (that is, an n-dimensional vector of zero added to a one in its jth element), we can find the optimal policy by computing the value functions through the optimality equation as follows in (7).

The boundary condition u0(x0)=−E[V(S(x0))] takes the expected denied reservations penalties into account. Every time a request for product j arrives, two different cases should be compared. If the state of the system at the beginning of time period t is given by x t , two terms should be compared; whenever the request is accepted, revenue f j is obtained and the reservation state changes to x t +e j . In contrast, when the request is rejected while the customer is loyal, we incur the loyalty penalty cost of λ j . Accordingly, it is optimal to accept a request for product j at time period t whenever

The right side of inequality (8) demonstrates the opportunity cost, a well-known term in RM literature. The problem stated in (7) suffers from the curse of dimensionality due to the large state variable, which makes it computationally intractable. In this case, computation of opportunity cost for optimal acceptance policy (8) is too difficult.

In the next section, we develop a deterministic LP for the joint problem considering loyalty programs and prove that this LP provides an upper bound on the optimal solution of equation (7). Then, we develop two decision rules for opportunity cost approximation based on the deterministic LP. Two algorithms for obtaining an efficient solution for approximating the total net revenue based on these two decision rules are constructed.

DETRMINISTIC LINEAR PROGRAMMING

A standard solution method for the aforementioned NRM problem is to solve a deterministic LP. We suppose that the product requests arrivals and the show-up decisions take on their expected value in the LP model. Letting z j denote the number of requests for product j that we plan to accept during the booking periods and y j the number of reservations that we need to deny, the deterministic LP can be formulated as follows in (9)–(13):

The first term in the objective function (9) is the expected revenue obtained by accepting requests, and the second term is the expected penalty cost of denying requests. The expected number of requests for product j during the periods {T, T−1, …, 1} is ∑1Tp jt . If we accept z j requests for product j, then (∑t=1TP jt −z j ) requests are rejected for product j on average. Therefore, the third term indicates the expected virtual penalty λ j (∑t=1TP jt −z j ) for product j, if product j is related to a loyal customer.

If z j requests are accepted for product j, then q j z j indicates the number of reservations for product j who show up to stay at the hotel on their corresponding check-in dates. Constraints (10) ensure that the total number of reservations allowed to stay on a specific night does not exceed the capacity. Constraints (11) ensure that the total accepted check-ins do not violate the expected numbers of the product j requests. Constraints (12) ensure that the numbers of denied reservations do not exceed the number of reservations who show up.

The deterministic LP formulation for the NRM problem is widely known in the literature when overbooking is not allowed (see Williamson, 1992; Talluri and van Ryzin, 1998). Bertsimas and Popescu (2003) and Erdelyi and Topaloglu (2009, 2010) extend this formulation to handle overbooking. We have extended their formulation to consider the loyalty programs in order to guarantee room availability for loyal customers.

An upper bound for dynamic programming solution

The models (9)–(13) can be applied for two main uses. First, the optimal objective value of problems (9)–(13) provides an upper bound on the optimal total expected profit. In other words, if Z LP * denote the optimal objective value of this problem, and is the optimal value function at the beginning of the booking horizon, and is the n-dimensional vector of zeros, which implies that no request is already accepted at the beginning of the planning horizon, then we have This result is the same whether overbooking is not possible, as in Talluri and van Ryzin (1998), or possible, as in Erdelyi and Topaloglu (2009). We extend this result for our problem and provide a formal proof in the next proposition.

Proposition:

  • We have

Proof:

  • Let Z j * denote the total number of requests for product j that are accepted during the booking periods under the optimal policy, and Y j * be the total number of denied reservations for product j according to the optimal policy. We also assume that s j *(k) is an indicator that takes value 1 if the kth accepted booking for product j shows up at the service time and takes value 0 otherwise. The total number of customers who show up under the optimal policy for product j is equal to . Conditioning on z j * we have what follows in (14):

    If D j denotes the total number of booking requests arriving for product j during the booking periods, the optimal solutions Z j * and Y j * should satisfy the following constraints (15)–(17):

    Inequality (15) expresses that the total number of accepted reservations under the optimal policy does not exceed the hotel’s capacity. According to inequality (16), the total number of accepted bookings for product j does not violate the total number of requests for product j. The other fact that should be mentioned is that the total number of denied reservations cannot exceed the total show-ups for product j, which is denoted in (17). Taking the expectation value from both sides of all three inequalities in (15)–(17) and replacing E(D j )=∑t=1Tp jt we have:

    According to (18)–(20), we can observe that the expected value of solutions Z j * and Y j * under the optimal policy satisfies the deterministic LP constraints (10)–(12) so that E(Z j *) and E(Y j *) are feasible solutions for deterministic LPs (9)–(13).

    On the other hand, the total net revenue under the optimal policy is the differences between revenues obtained through the booking process and the penalty costs incurred by denying reservations and rejecting loyal customers. In other words, the total net revenue is equal to

    Taking expectation value from (21) we have:

    The statement (22) is the objective function of (9)–(13) that the variables z j and y j take the values of E(Z j *) and E(Y j *), respectively. Given the fact that the number of accepted requests and the number of denied reservations cannot take negative values, it is easy to see that the solution (E(Z j *), E(Y j *)) is feasible for problems (9)–(13). As each feasible solution for (9)–(13) is less than or equal to the optimal solution of problems (9)–(13), it follows that:

     □.

LP-BASED APPROXIMATION METHODS

The second purpose served by the LP model in (9)–(13) is that this model is applied to develop two efficient LP-based acceptance policies to solve dynamic programming. On the basis of these policies the RM practitioner can decide whether to accept or reject the requests during the booking process.

Adopted deterministic linear program dual-based policy (ADLP)

The first decision rule is constructed based on the optimal values of dual variables. Letting 〈μ i *: i=1, 2, …, m〉 be the optimal values of the dual variable associated with capacity constraints (10), we can use μ i * to estimate the opportunity cost of a unit of capacity on ith night. If the revenue f j plus virtual loyalty penalty λ j exceeds the total expected opportunity cost of the room-nights occupied by product j, or if f j +λ j exceeds the expected penalty cost q j θ j , then product j’s request is accepted. In other words, if what follows in (23) holds for product j, then it should be accepted.

The left side of decision rule (23) is called the virtual value for product j. The virtual value takes the higher value of loyal customers into account by adding loyalty penalty cost to revenue f j . The inequality (23) captures two cases by which the hotel can in expectation obtain revenue. In other words, if the virtual value for product j is greater than the total expected opportunity cost of the room-nights occupied by product j, revenue can be captured by accepting the request for product j.

Furthermore, if f j ⩾q j θ j holds true, then in expectation, revenue can simply be generated by accepting a request for product j and denying the reservation at the service time. Erdelyi and Topaloglu (2009, 2010) used such a decision rule, whose left side only includes f j instead of the virtual value. With the new models developed, we extend their decision rule by considering the higher value of loyal customers during the booking process.

Because of the dynamic nature of the problem, it is better to divide the planning horizon into equal segments and re-optimize problems (9)–(13) using updated information at the beginning of each segment. To do this, we update the state of reservation every τ periods (at the periods T, T−τ, T−2τ, … up to the end of the planning horizon). Given that the state of the reservations at the beginning of lth segment (at the period t=T−lτ) is x t =xT−lτ, we use the model introduced in (24)–(28) to calculate the optimal value of dual variables associated with the capacity constraints in (25) for each day; then the decision rule in (23) can be used to decide whether to accept or reject product j’s requests.

Adopted finite differences in the deterministic linear program policy (AFDD)

Given that the state of the reservations at the beginning of period t is x t , and LP*(x t ) denote the optimal solution of problems (24)–(28) when the state variable keeping track of reservation is x t , AFDD approximates the opportunity cost by the following statement:

In other words, this approach, which is proposed by Bertsimas and Popescu (2003), uses LP*(x t ) as an approximation of value function u t (x t ). Similar to DLP, we solve problems (24)–(28) at the beginning of every τ periods by updated information. Therefore, it must be decided whether to accept or reject the request for product j according to the decision rule (30) and use this decision rule during these τ periods.

After the adoption of these two decision rules, we use simulation to approximate the total expected profit. For this purpose, given that the probabilities (p jt , j=1, …, n) are known, we sample product requests at each period t using these probabilities in such a way that the condition p0t+∑j=1np jt =1 is satisfied.Whenever a request arrives, we use decision rules (23) and (30) to decide whether to accept or reject this request. Whenever a request is accepted, the state variable x t is updated. We use updated x t to reconstruct the decision rules based on problems (24)–(28) and we continue this procedure up to the end of the booking horizon. We simulate the trajectories of both algorithms under R different demand requests realization. Averaging the iterations solutions, we can approximate the total expected net revenue. To obtain better solutions, the two decision rules are updated a couple of times by re-optimizing problems (24)–(28). In order to compare the performance of algorithms in a more accurate base, the various policies are simulated simultaneously on the same demand realizations.

COMPUTATIONAL EXPERIMENTS

In this section, we present the computational results that evaluate and show the performance of the two aforementioned algorithms for the hotel NRM problem. This section begins by defining the test problems’ characteristics and setting up the parameters and then presents the analytical computational results.

Test problem frameworks

A hotel network with c identical rooms is considered in an m-nights high-demand horizon. We can introduce at most m(m+1)/2 different lengths of stay for each class of customers. We assume that the number of all possible products is n. The room rate charged for product j is given by f j =ηl j (d+h) where η is the discount factor, which is equal to 1 for occasional customers and less than 1 for loyal customers, and l j is the length of stay of product j. d is the price of a room-night on non-holiday nights and h is the additive factor for holiday nights.

The penalty cost of rejecting loyal customers’ requests, discussed in the section ‘Problem statement’, is defined by λ j and takes the value of β. The penalty cost of denying a reservation is also obtained by θ j =(1+ɛ)f j +λ j , where ɛ is the overbooking cost coefficient. Another important factor we need to define is related to the demand. This factor should also be able to show the degree of capacity tightness. Regarding this, we introduce the capacity tightness factor given by (31) where the numerator indicates the total expected demand that show up to get their services. The capacity tightness shows the average ratio of expected demand to the total available capacity.

Our test problems are labeled by (m, n, c, ρ, q). We define three different horizons for the test problems: a 2-night horizon with 6 products, a 3-night one with 12 products and a 7-night horizon with 36 products. We also have c∈{20, 25}, ρ∈{1, 1.5, 2} and q∈{0.9, 0.95}. Assuming LV and LV2 are equal to US$20 000 and 10 000, respectively, and μ1=0.1, μ2=0.2, we can obtain β=$4000. We consider η=0.8 for loyal customers and η=1 for others. We also have h=100, d=50 and ɛ=0.4. By changing the parameters c, q and ρ and the horizons duration, 36 different test problems can be defined.

The number of booking periods before the beginning of the staying horizon is T′=80 and the number of periods within each staying night is τ=20. For example, for the 7-night horizon instances, we have T=80+(7−1) × 20=200 decision periods. The solutions are estimated by simulating the performances of the ADLP and AFDD policies under R=100 product request trajectories. Common product request trajectories are used when simulating the performances of both policies. We re-optimize the decision rules every 10 periods to increase the quality of solutions. We use a 2.53 GHz Intel core i3 CPU with 2 GB RAM to run our computational experiments. All of the computations are performed in MATLAB R2012b using the cplexlp toolbox.

Computational results

The main computational results are summarized in Table 1. The objective is to analyze the impact of implementing loyalty programs on the total expected net revenue that the hotel may obtain within a short-term horizon. In this regard, the test problems have been approximated under different policies either when the RAG is implemented or when it is not. Another objective is to evaluate the performance of the ADLP and AFDD algorithms in terms of quality of approximation and running time.

Table 1 Computational results for different policies when RAG is possible or not possible
Full size table

The second column in Table 1 gives the characteristics of the test problems. The next three columns present, respectively, the upper bound on the total expected profit, the approximate solutions of ADLP and those of AFDD, under the assumption that RAG is performed. Columns 6–8 show these values when RAG is not performed.

The values in columns related to ADLP and AFDD policies are estimated by taking the average of values obtained by simulating the problem under R=100 product request trajectories. Comparing the upper bound values and approximate solutions of ADLP and AFDD in Columns 3, 4 and 5 with the next three columns, we can observe that implementing RAG results in a significant decrease in total expected profit. Table 2 shows the amounts and percentages of decrease in total expected net revenue for different policies. In particular, life-time value-based penalties for rejecting loyal customers lead to a decrease in the expected values of the net revenue bound of ADLP and that of AFDD, respectively, by as much as 6.3, 9.9 and 8.7 per cent on average, which are considerable proportions of net revenue in the short-term horizon.

Table 2 The average decrease due to loyalty programs in different policies
Full size table

For example, in the 7-night test problems, the decrease in net revenue is equal to $1684 on average in the AFDD method. However, if a loyal customer request is rejected in this 7-night horizon because of lack of capacity, the customer may be attracted to a competitor, which implies a loss equal to $20 000 in the long term.

The computational results in Table 1 indicate that AFDD values are in most cases greater than those of ADLP, which implies the superiority of AFDD in terms of quality of solutions as an indicator of performance. Especially the quality of the ADLP solutions decreases substantially in the test problems in which capacity constraints are not active. For example, in test problems number (7)–(12) in which the probability of showing up decreases to q=0.9, the algorithm collapses. Such a substantial decrease in performance is a result of ADLP acceptance rule dependency on the dual variables. One should not forget that dual variables take effect from changes in constraints activity. However, in the test problems in which capacity constraints are binding, ADLP performs better, and in some cases the ADLP solutions even exceed the AFDD. The relative performance of these algorithms is compared in Table 3.

Table 3 The comparison of performance of AFDD and ADLP based on the average performance gap (AFDD-ADLP)
Full size table

Table 3 shows the average performance gap between AFDD and ADLP and its dependenc on the different parameters mentioned. We can observe that the greatest gap between AFDD and ADLP occurs when the probability of show-up is decreased to q=0.9 and the capacity tightness factor is equal to 1. In both cases the ratio of expected demand to the available capacity is small and the capacity constraints are inactive. Therefore, dual variable is not an appropriate measure to build a decision rule, which in turn results in a decrease in performance of ADLP. In terms of running time, AFDD also performs better than ADLP. The average running times for the test problems are illustrated in Table 4.

Table 4 The comparison of running time for AFDD and ADLP (in CPU seconds)
Full size table

LOYALTY PROGRAM COST-EFFECTIVENESS IN AN EXTENDED PLANNING HORIZON

The current models are only capable of calculating the decrease in the short-term revenue. It is worth mentioning that short-term decrease in revenue cannot be an indicator of loyalty program cost-effectiveness. We need to investigate whether loyalty programs have the capability to compensate short-term losses. Considering a longer horizon for analyzing the effects of loyalty programs on the expected net revenue of a hotel, short-term losses might be justified by the increase in loyal customers’ inclination toward making more purchases in the future. Having a mathematical formula in hand for the influence of discount rate and RAG to the prospect of future purchases, the long-term expected revenue of the hotel can be calculated for different scenarios of discount rate and RAG to design the most appropriate loyalty program.

Let us start by dividing the year into high-demand seasons and low-demand ones based on historical demand information. Low-demand seasons are those in which the booking reservations are usually all accepted as the average of demand is lower than the hotel’s capacity. In contrast, some of the booking requests are rejected within high-demand seasons as the hotel does not have enough capacity to accommodate them all. According to occupancy rate statistics (Statista, 2014), hotels usually experience a higher number of demands during approximately 13 weeks in a year. The high-demand seasons consist of independent high-demand weeks; that is to say, their demands are assumed to be independent.

Moreover, it is necessary to model loyal customers’ behavior in the low-demand seasons. As mentioned in the introduction, studies report a positive impact of loyalty programs on customers’ purchase frequency and transaction size (Liu, 2007). We consider both impacts on average loyal customer arrivals in low-demand seasons and call this the discount-RAG response function. In other words, the stimulation of demand due to persuasive policies of loyalty programs will result in a gradual increase in monthly request arrivals from loyal customers. The discount-RAG response function is the structure deployed to explain this phenomenon after being estimated based on historical customer behavior data. According to experimental customer behavior studies, a hotel can simply identify incremental customer purchase for different discount rate and RAG scenarios. For instance, marketing analysis is capable of estimating the outcome of different promotion programs such as giving fixed discounts to a defined segment of customers, in terms of increase in average customer arrivals on a monthly basis.

We consider the number of loyal customers making purchases in low-demand seasons to be the parameter shaping the discount-RAG response function, denoted as N(d, RAG), in which d represents the discount rate. The discount-RAG response function is a non-decreasing function of the discount rate and RAG, as giving discounts and guaranteeing room availability stimulate loyal customers’ tendency toward making more reservations in the future. Although one may find different factors shaping customers’ inclination toward future purchase, we simply take discount rate and RAG, as the main factors of the loyalty program mentioned, to be the controlling parameters for designing loyalty programs. A loyal customer is assumed to pay an average amount of F(d) each time he stays at the hotel in the low-demand seasons. It seems self-explanatory that F(d) is a non-increasing function of the discount rate.

The definition of analytical example continues by defining Stimulated expected Net Revenue (SNR) to calculate the expected net revenue earned through the purchases made by loyal customers during a low-demand season. The term stimulated is used as the loyalty program aims to stimulate loyal customers’ future reservations that contribute to expected net revenue. Considering N(d, RAG), representing the number of loyal customers making purchases of F(d) during a low-demand season, SNR would be defined in (32):

Since we plan to predict the hotel’s long-term cash flow in different scenarios to compare the expected net revenue, the analytical method should consider time value of money. Considering an annual horizon, the comparison criterion would be Present value of Annual expected Net Revenue (PANR), which embodies expected net revenue in high-demand seasons based on the AFDD algorithm, which is shown to perform better, as well as expected net revenue in low-demand seasons projected by the stimulated purchases of loyal customers. As the behavior of occasional customers does not take effect from loyalty programs, their contribution to the expected net revenue in low-demand seasons has not been considered, in order to make the comparison as simple as possible.

As mentioned earlier, the time value of money is to be considered for obtaining PANR in different scenarios. The term Minimum Attractive Rate of Return (MARR) is adopted here, which demonstrates the lowest investment interest rate that the decision maker can have without taking any risks (Smith, 1973).

Finally, the comparison criterion that features a prospective approach to calculating expected net revenue can be defined by (33), in which n′ denotes the time period index, which takes its value from two different sets, High for high-demand periods and Low for low-demand ones. As mentioned earlier, PANR combines two types of net revenue, NR obtained from AFDD and SNR introduced in (32).

It seems quite obvious that as the capacity tightness, the indicator of a season being low-demand or high-demand, is dependent on factors such as weather conditions, the high demand seasons are different from one place to another. Here we base our analysis on having 13 weeks of high demand in June, July and August, which is also in accordance with peaks of occupancy rate diagrams for hotels in Europe and the United States (Statista, 2014).

According to historical customer behavior information, the relation between loyalty program factors and average number of loyal customer arrivals in low-demand seasons can be estimated by a simple mathematical equation. Here the discount-RAG response function, N(d, RAG), is considered to be a non-decreasing function of loyalty program factors in terms of a second-degree polynomial function as stated in (34). Figure 2 shows the outcome of different loyalty programs with discount rates up to 40 per cent in terms of average number of loyal customer arrivals in low-demand seasons.

Figure 2
figure 2

Average number of loyal customer arrivals in low-demand seasons according to different loyalty program factor values.

Full size image

As giving discounts without guaranteeing room availability prioritizes the acceptance of occasional customers during high-demand seasons in the capacity allocation model, the function introduced for RAG=0 is only used in one state of loyalty program factors where no discount is offered.

As shown in Figure 2, a 5 per cent discount will result in a prospect of 18 loyal customer arrivals in each low-demand season, while 14 requests are received on average in every low-demand season when giving no discount but guaranteeing room availability.

Moreover, F(d) is assumed to be the average amount of purchase equal to $450 modified by the discount rate as stated in (35).

As the cash flows and seasons are set up monthly, MARR should be defined in the same order. Monthly MARR is considered to be 0.01 for the hotel in question, which results in 12.68 per cent annual interest without any risks on the investment. The level of demand tightness for high-demand seasons is another influential factor, which is considered to be equal to 1 based on its equation introduced in (31).

PANR(d, RAG) is calculated for different values of loyalty program factors. The results are reported in Table 5 based on the equations introduced in (32)–(35).

Table 5 present value of expected net revenues of seasons throughout a year
Full size table

As shown in Table 5, NR decreases by increasing the discount rate from the bottom of the table to the top. In contrast, SNR(d, RAG) increases by the discount rate from d=0 to d=0.25 and then it decreases for more values of the discount rate beyond 0.25. The peaks of each term are shown with a gray highlight. The reason for this behavior is that SNR(d, RAG) is the multiplication of N(d, RAG) and F(d). As mentioned earlier, the discount-RAG response function increases and F(d) decreases to the discount rate. As the comparison criterion has an annual viewpoint, the most appropriate discount rate to be implemented for maximizing expected net revenue is lodged somewhere between the peak on NR and that of SNR(d, RAG) on 0.15, while availability of rooms is guaranteed for loyal customers. On the basis of the values of PANR(d, RAG) in Table 5, such a loyalty program can increase expected net revenue from $315 722$ to 326 590, which accounts for a substantial improvement equal to 3.44 per cent.

Equally relevant to the issue of appropriate loyalty program factor values are the questions of sensitive parameters. Here we have set the MARR and tightness to certain values (MARR=0.01 and tightness=1), while these two can be different from one case to another. The analysis is replicated for combination of three values for MARR and two for tightness. The appropriate loyalty program factors for the different values of parameters in question are identified by the same type of analysis shown in Table 5. As shown in Table 6, varying MARR and tightness will result in changes of not only expected net revenue improvement, but also appropriate loyalty program factor values.

Table 6 The effects of MARR and tightness on loyalty programs
Full size table

Interpretation of Table 6 can guide RM practitioners toward important issues in designing a loyalty program. First, PANR decreases by increasing MARR. Although it seems quite obvious that increasing MARR always lessens the present value, the expected increase in net revenue, which positively impacts on program cost-effectiveness, changes the same way as loss of revenue does. In other words, benefits and costs both grow smaller by increasing MARR, which leads to almost the same results, as shown in the last column of Table 6. This issue is, however, predictable as time value of money reduces both losses of revenue and revenue increase. Therefore, appropriate values of loyalty program factors are almost independent of MARR.

The impact of tightness is delineated in Table 6. Cases in which tightness is equal to 1.5 do not have appropriate loyalty programs. In other words, the need for loyalty programs is obviated as the losses of revenue in high-demand seasons could not be compensated by additional revenue gained by stimulating the demand in low-demand seasons.

In addition to the points discussed above, there are other elements that can substantially affect the cost-effectiveness of loyalty programs and their appropriate values of factors. One may argue that the analysis performed is highly dependent on the discount-RAG response function representing the relation between loyalty program factors and average number of loyal customer arrivals in low-demand seasons (N(d, RAG)). This is indeed true; it is significant how many future purchases an incremental discount can stimulate. For example, a hotel may increase its monthly average of loyal customer arrivals from 14 to 18 by guaranteeing room availability and a 5 per cent discount (similar to the case discussed), while loyal customers of another hotel are so eager for loyalty privileges that the monthly average of loyal customer arrivals increases from 14 to 20 when they are offered the same. Certainly the latter would have a different discount-RAG response function, which in turn might drastically change the cost-effectiveness of loyalty programs as well as their appropriate values of factors.

DISCUSSION

The computational results indicate that implementing RAG may lead to a large decrease in short-term profit. This effect is due to the higher weight allocated to loyal customers who pay less than other customers for the same products. Even if loyal customers pay as much as others do for similar products, we can expect a decrease in net revenue because the availability guarantee forces the managers to keep some rooms empty to give service to loyal customers who may book late. One may thus conclude that there is a negative impact of CRM programs on short-term revenue.

On the other hand, from a long-term point of view, losing some true loyal customers because of lack of available capacity may lead to a larger decrease in profits because loyal customers generate noticeable revenue annually by paying frequently for the hotel products not only in the high-demand seasons, but also in the seasons in which demand does not exceed hotel capacity. One should keep in mind that loyal customers have higher expectations and are sensitive to being rejected or receiving substandard services, which may lead to mistrust. The current effect implies the negative impact of RM practices on customer relationships in the long term.

Some of the loyalty program incentives, such as RAG, decrease revenue only in high-demand seasons. It should be noted that there are limited high-demand seasons within a year and the losses incurred by implementing these kinds of loyalty programs are insignificant in comparison to the annual net revenue. In contrast, giving discounts to loyal customers for every single day of the calendar decreases revenue in all seasons. Thus, it is important to study the effect of different levels of discount on the frequency and volume of loyal customers’ purchases. Giving a significant discount while loyal customers’ future purchase frequency and transaction size is insensitive toward discounts can lead to a notable decrease in net revenue. One may argue that the hotel may offers discount rates only for the low-demand seasons. However, such behavior may be interpreted as opportunistic by loyal customers and weaken their trust.

Although from the hotel manager’s point of view maximizing revenue on a daily basis is important, managers should not neglect the impact of customers’ trust and satisfaction on long-term profitability. In particular, customers who show their trust by asking for service frequently should be treated with more care because of their higher expectations. Therefore, it is worthwhile to consider their value at the time of decision making.

Accordingly, selecting a loyalty program should be based on a trade-off between long-term additional net revenue obtained by retaining loyal customers and increasing their tendency to purchase more frequently in low-demand seasons and the losses of revenue discussed. On the basis of the number of high-demand periods and the amount of decrease in each of these periods from an annual perspective, the qualifying measurement of being a loyal customer should be defined in respect to long-term increase in hotel revenue. This issue demands a comprehensive investigation based on the historical behavior of different customer groups.

We have constructed an approach to consider the value of customers in RM decisions. Although the model was formulated in a short-term high-demand season, we considered the value of customers as a long-term measurement in making decisions. The analytical structure proposed in the previous section enables hotel RM practitioners to make their decisions on a more accurate basis whereby the value of customers, their satisfaction and their long-term relationship are regarded, as well as the hotel’s annual expected revenue. As mentioned earlier, the different parameters such as loyal customers’ sensitivity toward levels of discount rate and RAG, the number of high-demand seasons within a year, the total number of loyal customers, and MARR, can effect hotel managers’ decisions on the values of loyalty program factors. It should be noted that the success of such an integration between RM and CRM strategies demands profound mutual understanding between hotel operations managers and account managers.

CONCLUSION

In this article, a hotel NRM model considering loyalty programs is developed to make the capacity control and overbooking decisions simultaneously. Without loss of generality, we assume that hotel customers are divided into two major groups: loyal and occasional customers. Loyal customers are the most profitable customers who make purchases frequently and generate a significant proportion of annual revenue. These customers are identified by a loyalty measurement called CLV. The loyalty program includes policies such as offering rooms at a discount and guaranteeing room availability.

A stochastic dynamic programming model is formulated for the capacity control and overbooking decisions, whereby room availability is guaranteed based on the remaining lifetime value of loyal customers. Because of the curse of dimensionality due to the large state variable, the dynamic programming model is computationally intractable. Thus, two approximation methods are constructed based on deterministic LP. The main problem is tackled by two different LP-based approaches: ADLP and AFDD. The results show that the AFDD algorithm performs significantly better than the ADLP. This effect is due to the dependency of ADLP on factors and parameters such as optimal value of dual variables, capacity tightness and show-up rates. The computational results indicate that implementing loyalty programs may result in a decrease in short-term profit. However, the cost of rejecting a loyal customer due to the lack of capacity can be even more damaging for the hotel’s revenue.

However, short-term loss of revenue is not the appropriate decision criterion for loyalty program cost-effectiveness as it only considers a short planning horizon, which neglects the long-term effects of such programs on net revenue. We need to balance these types of losses in order to make a sustained profit in the long term. Therefore, it is important to select loyalty measurement in such a way that the additional net revenue obtained by retaining loyal customer in the long term exceeds the total decrease in short-term revenue. On the basis of an analytical model including the discount-RAG response function in terms of average loyal customer arrivals in low-demand seasons, loyalty programs can compensate their short-term decrease in net revenue by stimulating loyal customers’ tendency toward making more reservations in low-demand seasons. Moreover, different loyalty programs are compared for a particular problem, which shows the capacity of tailored loyalty programs to increase expected net revenue by up to 3.5 per cent. In contrast, there are cases in which loyalty programs cannot be cost-effective as low-demand additional revenue will not make up for losses of revenue in high-demand seasons. In regard to sensitive parameters other than discount-RAG response function, cost-effectiveness is most sensitive to the level of tightness while it does not change significantly with modifying MARR.

There are several directions for future studies. In this article we considered only one group of loyal customers and assumed that all of these customers have similar purchase behavior. One can categorize different groups of customers based on different lifetime values with different levels of loyalty programs associated with each group. For instance, the first level may book until the beginning of the staying date, whereas the second level may book at most 48 hours before the staying date and so forth. Furthermore, a case-based feasibility study could be conducted based on the proposed analytical methods of this study to examine the effect of implementing loyalty programs in long-term. This will surely help senior managers to make decisions about integration of RM and CRM on a more accurate basis.