INTRODUCTION

Revenue management (RM) involves the use of sophisticated procedures to balance supply and demand to maximise revenue and profit. RM has generated billions of dollars for many industries, including airlines, hotels, car rental firms, cruise lines, utility firms, railroads, retailers, tour operators, manufacturers and media companies (Smith et al., 1992; Cross, 1997).

Broadly speaking, the science of RM uses two techniques: pricing and capacity control.¹ The main goal of pricing techniques is to use price as a lever to increase revenue, while capacity control focuses on allocating resources to identify the best mix of products. In general, capacity control methods are effective when capacity is perishable and/or limited; otherwise, pricing methods are more successful.

In this paper, we focus on the capacity control problem. Capacity control can be viewed as a special class of the problem of matching demand to supply. In this view, supply is known and difficult to adjust. On the other hand, demand is highly uncertain due to a number of factors, such as consumption time, purchase time, price amount and quality of own and competing products.

Current capacity control models either consider each resource separately or treat the problem as a network of resources. The latter models are generally referred as network capacity control (NCC) models. Another key aspect of most capacity control models is the assumption that demand is independent of controls applied by the seller. That is, the customers who purchase at full price are separate from the ones who purchase at discount fares. However, the likelihood of customers buying at full fare increases when the discount fare is unavailable. In this paper, we investigate the NCC problem in the presence of this buy-up behaviour.

Capacity control is accomplished by either partitioned or nested allocation schemes. In the former scheme, capacity is partitioned among different fare classes, and a reservation is honoured for any fare product as long as the allocated capacity for the fare class is not exceeded. In a nested-seat-allocation system, fare products can be ordered in a strict hierarchy according to their revenue contributions, and a request for a fare product is always accepted if capacity is available for a lower fare product.

This paper proposes three stochastic programming (SP) formulations with buy-ups. The first model assumes that the company controls its capacity with partitioned booking limits, and customers can buy-up to any higher-valued fare product available. The second model also assumes partitioned booking limits; however, customers may only buy-up to the next fare class and leave the system if the next fare product is also unavailable. The third model considers theft nesting with the assumption that customers can buy-up to any higher-valued product, as in the first model.

In addition, each model is evaluated under four different simulation scenarios. In the first scenario, each model is executed once for the entire booking horizon, and customers are allowed to buy-up to any higher-fare class. The remaining simulation scenarios execute each model multiple times (for 20 equally spaced time periods) by assuming that demand arrivals follow a homogeneous Poisson process. As in the first scenario, the second scenario allows buy-ups to any higher fare class. However, the third scenario allows buy-ups to the next fare class only. The final scenario adopts the buy-up behaviour of the first scenario; nevertheless, customers are assumed to buy-down, that is, buy the lowest available fare at the time of each booking request. Furthermore, the simulated arrivals are controlled by nested booking limits for each scenario.

Although airline-specific terminology is used in our discussion, the proposed methodologies have potential utilisations in other service industries, such as the lodging, car rental, printing and publishing, delivery service, food service, broadcasting, entertainment, healthcare, cruise line, trucking, and railroads industries.

Current available optimisation procedures capture important components of NCC problems, although no one has considered an NCC problem with stochastic demand, partitioned or nested controls, and buy-ups simultaneously. The main contributions of this paper can be listed as follows:

1. Three new SP models that consider the customer buy-up behaviour are formulated for NCC problems.
2. The buy-up behaviour of customers is modelled in two different ways.
3. The arrival order is incorporated into the modelling framework using the order statistics property of Poisson processes.
4. Four different simulation scenarios are executed to quantify the expect revenue performance of the proposed models as compared to the expected revenues of deterministic linear programming (DLP) and randomised linear programming (RLP) formulations.

Earlier studies that are most relevant to our research are Higle (2007), Higle and Sen (2005), Chen and Homem-de-Mello (2004), van Ryzin and Vulcano (2004) and Jiang and Miglionico (2006).

The remainder of this paper is organised as follows. The next section gives a brief overview of the related literature. Then, the notation is introduced and new SP models are proposed. The subsequent section provides a solution procedure. The fifth section states the simulation methodology that is used in assessing the models. The penultimate section gives computational results. The final section contains a summary, conclusions of the work, and directions for further research.

REVIEW OF RELATED LITERATURE

In this section, we present an overview of existing methodologies on NCC and customer choice models. These methodologies include dynamic programming (DP) and approximation methods, such as DLP models, decomposition methods, SP approaches and customer choice models.

Early research in this area focuses on single-leg problems. Littlewood (1972) provides the optimal space allocation policy for a single-leg problem with two customer fares where the demand is stochastic. Later, this work is extended to multiple fare classes, and the threshold time property of the optimal policy is proven by utilising DP (Lee and Hersh, 1993). Similar to single-leg capacity control problem, the NCC problem can be formulated and solved as a DP model (eg, Talluri and van Ryzin, 2004a).

Although the DP model captures the exact nature of the problem by accepting or rejecting each demand arrival, the complexity of the problem grows exponentially with size. As a result, most of the problems encountered in practice are intractable. Hence, several methods are proposed to approximate a solution to the DP model for practical problems.

Approximation methods can be categorised into two main groups. The first group considers the entire network concurrently and relies on the deterministic and stochastic mathematical programming formulations to reduce the complexity of the problem. DLP is the most well-known and commonly used technique in practice (D'Sylva, 1982; Glover et al., 1982). This formulation produces partitioned booking limits, and the demand is approximated by its expected value. The dual variables corresponding to the capacity constraints are often utilised to implement bid-price controls. A major drawback of the DLP approach is that it utilises only first moment information, expected demand, to characterise demand.

To circumvent this problem, the probabilistic nonlinear programming (PNLP) approach is proposed (Wollmer, 1986). Although probability structure is explicitly formulated in PNLP, Williamson (1992) shows that DLP will generally outperform PNLP if the problem is optimised frequently. Talluri and van Ryzin (1999) propose an RLP model, which involves simulating a sequence of realisations for demand and solving the corresponding DLP models to generate optimal bid prices for each realisation. Then, the sample mean of the bid-prices is used as an approximation for the real bid-prices. In SP terminology, this is basically averaging over the so-called wait-and-see solutions. In theory, this approach can be further improved by using SP appropriately. For a discussion on comparison of wait-and-see solution and SP solution, we refer the reader to Birge and Louveaux (1997).

Another way of approximating the DP model is to decompose the network into multiple single-leg problems via methods like virtual nesting (Smith et al., 1992). Then, the problem can be solved by using leg-based inventory control methods (Belobaba, 1987b, 1989). Recent books by Talluri and van Ryzin (2004a) and Phillips (2005) provide excellent treatments of NCC problem and further literature review on the subject.

Lately, there have been considerable efforts to formulate the NCC problem as SP models. Some of these methods use gradients, which are generated via simulation. Bertsimas and de Boer (2001) propose a stochastic gradient procedure for discrete demand case, and van Ryzin and Vulcano (2003) provide a similar approach for continuous demand case. de Boer et al. (2002) propose a simple recourse formulation for the problem. Higle and Sen (2005) formulate the problem as a two-stage stochastic program with nested booking limits as decision variables. They provide an extensive simulation study and state that the advantages of the SP model decrease as the number of fare classes increases. Möller et al. (2004) propose an SP formulation based on scenario trees, which also take cancellations into account. Cooper and Homem-de-Mello (2003) develop a hybrid methodology that combines the concepts of SP and Markov decision processes. Chen and Homem-de-Mello (2004) propose a multi-stage SP formulation, which is hard to solve due to the lack of convexity properties. They propose an approximation scheme by solving simple recourse problems frequently. Higle (2007) proposes a two-stage formulation, where demand is observed at O&D pair level.

Most of the available models assume that demand is independent of capacity controls. However, customers can buy-up to a higher fare if the original fare product is unavailable, or they can buy-down if lower fare products are available.

Efforts to model customer behaviour can be categorised into two groups. The first consists of extensions to Littlewood's (1972) stochastic two fare class problem with a single flight leg (eg, Pfeifer (1989)). This is also discussed by Belobaba (1987a, 1987b, 1989), who proposes a modified version of EMSR approach. Belobaba and Weatherford (1996) develop another heuristic for formulating customer buy-up or buy-down behaviour. Andersson (1989, 1998) and Algers and Besser (2001) apply logit models to estimate buy-up and recapture behaviour for Scandinavian Airlines. Boyd and Kallesen (2004) discuss priceable and yieldable demand in a single-leg setting and argue that if customers are not properly segmented, revenue decreases as a result of buy-downs. Finally, Jiang and Miglionico (2006) study the buy-up behaviour in an NCC problem. However, unlike our approach, they modify DLP and RLP models to formulate the problem.

A second group of models uses consumer choice. Unlike classic yield management, which utilises demand information at the product level, consumer choice models provide the flexibility to choose from a set of products according to a probability distribution. Mahajan and van Ryzin (2001) apply logit models to analyse product substitutions and employ stochastic gradient methods to solve the problem. Talluri and van Ryzin (2004b) give a detailed analysis of a single-leg problem under a general customer choice model. Zhang and Cooper (2005) investigate customer choice among parallel flights using Markov decision processes.

Gallego et al. (2004) generalise the idea of the DLP model by including flexible products into the decision-making scheme and utilise a column generation approach to solve the problem. They also prove the asymptotic optimality of their proposed method. This idea is further analysed by van Ryzin and Liu (2004). They propose a decomposition-type heuristic for solving the problem. van Ryzin and Vulcano (2004) also incorporate stochastic aspects of the problem and develop a stochastic gradient method for computing virtual nesting controls. Vulcano et al. (2007) generalise the model defined by van Ryzin and Liu (2004) and allow more flexible customer segmentation.

As mentioned above, this paper focuses on three new SP formulations based on the customer's buy-up behaviour. We utilise special properties of these formulations to improve the solution efficiency. The proposed formulations are compared with DLP and RLP using simulation techniques. The results indicate that using SP and modelling customer choice explicitly yield a substantial increase in expected revenue.

MATHEMATICAL MODELS

Basic assumptions and notation

We consider an airline that operates a set of flight legs across its entire network. A non-stop flight at a specific departure time is usually referred as a flight leg. The set of flight legs is denoted by L. Each flight leg l has capacity c_l. The set of itineraries is denoted by I, and the set of itineraries using leg l is denoted by I(l). Each itinerary is characterised by its corresponding flight legs and serves to a specific O&D pair. The set of all O&D pairs in the entire network is denoted by M. We allow more than one itinerary for a given O&D pair and represent I_m as the set of itineraries corresponding to O&D pair m. We denote the O&D pair specified by itinerary i by _i. We define set J_m={1, 2, ..., |j_m|} to be the set of fare classes for each O&D pair mM. Without loss of generality, we assume that fare class 1 is the most valuable fare class, fare class 2 is the second most valuable fare class, etc.

Many available procedures track demand for each itinerary separately. For example, in a three-city network that involves flights A–B, B–C and A–C, there are four potential itineraries: A–B, B–C, A–C and A–B–C. In this work, demand is assumed to be tracked and forecasted at O&D-pair level; that is, each customer is assumed to request a booking based on a specific O&D pair and fare class. We also assume that customers are indifferent about the potential itineraries A–C and A–B–C.

In this work, the notation of random variables will include a tilde. The total stochastic demand for O&D pair m and fare class j is denoted by random variable _mj. We define the price for O&D pair m and fare class j as f_mj. The indifference assumption is not necessary for the main results of the paper and can be relaxed with minor modifications. It is provided here as it can be considered as an extension.

Although demand is observed at O&D pair level, the seat availability must be managed for each itinerary because each itinerary is composed of a specific set of flight legs. We use x_ij to denote the capacity allocated for itinerary i and fare class j. These allocations are then aggregated over all related itineraries to find the total availability for a given O&D pair. The aggregated availability for each O&D pair m and fare class j is denoted u_mj.

Furthermore, we assume that the company is risk neutral; that is, the expected revenue is maximised with respect to the demand forecast as of now, ignoring the future impact of imposing inventory control decisions. In addition, cancellations and no-shows are disregarded. We also assume that capacity and demand are continuous, floating-point numbers.

As mentioned above, the proposed SP models incorporate buy-ups into the decision-making framework. In this framework, if no seat is available for O&D pair m and fare class j, a customer may buy-up to fare class j-1 with probability p_mj. We consider two main buy-up assumptions in the proposed models: one with buy-up to the next fare level, another with buy-up to any higher-fare level.

Additional notation is given in detail when formulating corresponding models. We also summarise all notations in Appendix B for ease of reference.

DLP model

In this paper, we utilise DLP approximation of the NCC problem as a benchmark to evaluate the proposed SP models as it is the most commonly used approximation method. The DLP is formulated as the capacity allocation problem using the expected value of the demand vector in order to obtain partitioned booking limits.

The classical formulation of the DLP assumes that each customer requests a seat in a specific itinerary and fare class and leaves the system if the capacity is not available in that itinerary and fare class. Our DLP formulation assumes that each customer requests a seat for a specific O&D pair (not a specific itinerary) and fare class, and the customer is indifferent among different itineraries for that O&D pair. This indifference assumption is the same as assuming that the company has flexible fare products for each O&D pair and leads to the same formulation as in Gallego et al. (2004) and Higle (2007).

Let decision variable x_ij denote the partitioned booking limit for each O&D itinerary i and fare class j. Then, the DLP model is formulated as follows:

In this formulation, the objective function (1a) maximises expected revenue contributions. Constraints (1b) impose availability constraints and establish that, for each flight leg l, the total number of passenger assignments cannot exceed the available capacity. Constraints (1c) compute the total booking limit u_mj for each O&D pair m and fare class j by aggregating booking limits of the itineraries that serve customers requesting O&D pair m. Constraints (1d) state that the booking limit for each O&D pair m and fare class j must be bounded by the expected demand. Finally, constraints (1e) represent non-negativity of booking limits.

The DLP produces partitioned booking limits, which can be used to restrict the amount of demand to be accepted in each fare class. However, a more common practice is to utilise bid prices, which can be derived from the dual variables corresponding to the capacity constraints (1b). In practice, the DLP is frequently re-optimised to take into account the most current demand activity.

There are two major shortcomings of the DLP model. First, it uses only the expected value and disregards other distributional information on demand. Secondly, the DLP assumes that the denied customers leave the system if their O&D pair and fare class is unavailable. However, in practice, customers may purchase a more expensive fare class when their original request is denied. The following SP formulations address these two shortcomings.

Stochastic linear programming (SLP) models

We utilise the two-stage approach, frequently engaged to model uncertainty (Birge and Louveaux, 1997). This approach can be summarised as follows. In the first stage, the booking limits are generated by considering available capacity. In the second stage, the revenue is estimated for a specific demand vector given the booking limits.

First-stage model

The following first-stage model is utilised for all three SP formulations.

This formulation has the same structure as the DLP model with two key differences: It maximises a generic function h(u, ) instead of maximising a linear objective function. In addition, demand is taken into account in the objective function instead of constraints.

The generic definition of function h(u, ) provides a flexibility in formulating the revenue-generation scheme. The second-stage formulations exploit this flexibility in h(u, ) to formulate different business problems and assumptions, which will be given as SLP1, SLP2 and SLP3.

Second-stage model (SLP1): Buy-up to any higher fare class

The SLP1 model assumes that a customer requesting a seat for O&D pair m and fare class j may buy-up to any higher fare class in a sequential manner. Let p_mj denote the buy-up probability from fare class j to j-1 when fare class j is unavailable. The customer may continue to buy-up with the probability p_m(j-1) corresponding to her new class j-1. The SLP1 produces partitioned booking limits.

Let v_mj¹ be the satisfied demand and v_mj² denote the unsatisfied demand for O&D pair m and fare class j. Under the assumptions of SLP1, the satisfied demand, v_mj¹, includes customers who originally requested and/or bought up to fare class j and successfully booked. It is noted that a portion of the unsatisfied demand v_mj² is lost forever, but the remaining portion is re-captured and booked in a higher fare class as they buy-up.

In this formulation, constraints (3b) and (3c) assure that satisfied and unsatisfied demand for a given O&D pair m and fare class j must be equal to the demand for fare class j plus re-captured demand from the lower fare class j+1. In constraints (3c), |J_m| indicates the cardinality of set J_m. Constraints (3b) and (3c) allow that buy-ups continue until fare class 1 if demand cannot be allocated to lower fare classes. Constraints (3d) utilise the booking limits computed by the first stage and assure that the satisfied demand does not exceed booking limit for each O&D pair m and fare class j. We refer to the above model as SLP1, when considered together with the first-stage model (2).

Next, the structural relationship between the stochastic model SLP1 and its deterministic counterpart is explored to construct an upper bound on the optimal value of the stochastic model SLP1. If we replace the random demand in SLP1 with its expected value, we obtain the following deterministic linear program, which is referred as DLPB.

Theorem 1

Let z_SLP1^* and z_DLPB^* be the optimal values of SLP1 and DLPB, respectively. Then z_SLP1^*z_DLPB^*.

Proof

See Appendix A. 

Theorem 1 provides upper bound for SLP1. By using the concavity of the second-stage function h(), the lower bound on the optimal value z_SLP1^* could be derived. However, the proof is more involved, and the reader is referred to Birge and Louveaux (1997) for more details. Similar results can also be derived for SLP2 and SLP3 presented in the next two sections.

The formulation given in (4a), (4b), (4c), (4d), (4e), (4f), (4g) and (4h) is similar to the DLP formulation provided in Section 'DLP model', except for the fact that it incorporates customer buy-up behaviour. As in the extension of DLP to RLP, the demand in DLPB can be simulated sequentially to obtain the controls. This version of RLP including buy-ups is referred as RLPB in the remainder of this paper.

Second-stage model (SLP2): Buy-up to the next fare class only

In contrast to SLP1, the second formulation assumes that the denied customers can buy-up to the next fare class only and leave the system if there is still no seat available for the new fare class. Constraints (5b) ensure that the satisfied and unsatisfied demand must be equal to the demand for O&D pair m and fare class j. Customers, who choose to buy-up, compete for the capacity in constraints (5c). If demand is still unsatisfied after a single buy-up, it is captured in the dummy variable s_mj, and thus cannot buy-up any further. In SLP2, the decision variable v_mj¹ has a different meaning than v_mj¹ in SLP1 because it only represents the satisfied demand for the customers who originally demanded fare class j. Hence, we add the customers who bought-up to fare class j (p_m(j+1)v_m(j+1)²) and subtract the unsatisfied demand (s_mj) to find the total number of seats sold for fare class j. We refer the following model as SLP2, when considered together with the first-stage model.

Second-stage model SLP3: Buy-up to any higher fare class with theft nesting

Similar to SLP1, the third formulation assumes that customers can successively buy-up to any higher fare classes. However, it uses theft nesting controls instead of partitioned booking limits. The theft nesting requires that a booking in fare class j reduces allocations for class j and all lower-fare classes, namely, j+1, j+2, ..., J_m. Therefore,

can be treated as a booking limit for fare class j. The same conclusion is invalid for standard nesting because a booking in fare class j does not necessarily change the allocations for lower fare classes (see Talluri and van Ryzin, 2004a).

Decision variables, objective function (6a) and constraints (6b) and (6c) are similar to the corresponding decision variables and constraints given in formulation SLP1. If partitioned booking limits were used, u_mj would be the capacity allocated for fare class j. However, since SLP3 uses theft nesting controls, allocation to fare class j also reduces the availabilities of lower fare classes.

The right-hand side of constraints (6d) estimates the actual capacity used by fare class j, which can be identified as the percentage of u_mi sold to fare class j for a given demand .

If demand arrivals follow a homogeneous Poisson process, we can utilise the order statistics property of arrivals to estimate this percentage. The order statistics property indicates that arrivals can be generated using a uniform distribution when the demand for each fare class is given. The reader is referred to Kulkarni (1995) for a detailed explanation of order statistics property of Poisson processes.

Consequently, we estimate the percentage u_mi sold to fare class j as _mij=_mj/_kimk. It is noted that _mij is a random variable as it is a function of another random variable .

We refer to the following model as SLP3 when considered together with the first-stage model.

SOLUTION METHODOLOGY FOR PROPOSED SP MODELS

Section 'SLP models' exploits the two-stage nature of stochastic programs to incorporate uncertainty and buy-up behaviour. However, due to the computational complexity, solving the proposed SP models SLP1, SLP2 and SLP3 may require exceptionally high computer execution times for a large network of flights. In this section, we discuss solution methodologies that can be used to solve proposed SP models.

If the random demand vector has finite support; that is, there are only finite number of possible scenarios, we may write the problem as a large-scale equivalent linear program, where the first- and second-stage formulations are combined. However, such an approach is unappealing since the solution time of the linear program scales up cubically in terms of the number of scenarios.

To overcome this problem, the L-shaped method, developed by van Slyke and Wets (1969), is used. The L-shaped method is a cutting-plane algorithm that exploits the concavity of the objective function h(u, ) with respect to decision variable u. At each iteration, the algorithm generates cuts on the value of the objective function so that the difference between lower and upper bounds on the value of the objective function converge within a pre-specified optimality tolerance. For more information on the L-shaped method, we refer the reader to Birge and Louveaux (1997).

Figure 1 summarises the main steps utilised in the L-shaped method. The Initialisation Step sets an optimality tolerance limit , a very small number. In addition, the objective function of the first-stage model (ie, Master Problem) is replaced with decision variable , which is initialised as a free variable bounded from above by Theorem 1. The goal is to produce cuts on so that represents the optimal value of E(h(u, )). The Initialisation Step also defines the initial upper and lower bounds of the objective function based on Theorem 1.

Figure 1.

L-shaped method

Full figure and legend (53K)

Furthermore, this step utilises Monte Carlo sampling to create N second-stage problems from randomly generated demand samples. Next, the first-stage model is solved by maximising . In this step, optimal allocation u' and upper bound (UB) on the objective function are generated.

Then, for each second-stage problem generated in the Initialisation Step, values on the right-hand side are calculated using optimal allocation u'. Each subproblem is then solved to obtain optimal dual variables. In addition, lower bound (LB) is updated using the average of the objective function values of the second-stage models. If the difference between the upper and lower bounds is within optimality tolerance , then a single replication of the L-shaped method is completed after obtaining a set of optimal booking limits.

Otherwise, additional cuts are generated using the optimal values of dual variables from the Subproblem Step. Then, the function h(u, ) is approximated by using these cuts, and the process is repeated.

As mentioned above, the L-shaped method is applied along with Monte Carlo sampling, since the L-shaped method cannot be used when demand has infinite (possibly uncountable) support. Hence, we approximate the joint distribution of demand by drawing N sample demand vectors and use them in the L-shaped method to minimise the sample mean. This approach is completely probabilistic and depends on the random sample. In addition, it is proven that it yields asymptotically optimal controls as the sample size N increases. Besides, the rate at which the error converges to zero only depends on N; that is, independent of the dimension of the demand vector. Shapiro (2003) gives an excellent review of the use of Monte Carlo methods in stochastic optimisation.

The solution quality of an N-sample problem depends on the random sample. Therefore, the N-sample problem is replicated for S times to reduce this dependency. The final optimal controls for the SP are then estimated by averaging the optimal solutions to these S replications. When buy-up probability is 0 and N=1, this procedure reduces to the RLP algorithm developed by Talluri and van Ryzin (1999).

If N=1, the decision maker makes a myopic decision to optimise the system for that specific demand realisation. This is called the wait-and-see solution in the SP literature. However, if N1, the decision maker takes different realisations into account and optimises the expected profit, using more information on demand. Birge and Louveaux (1997) provide an excellent discussion on the superiority of the stochastic solution to the wait-and-see solution.

In practice, the controls are optimised multiple times (often daily) before flight departure by incorporating the most up-to-date demand information. Since fares are static, and the revenue is managed by controlling the availability of fare classes; each time we re-optimise, the distributions of demand and capacity change, and all other parameters remain the same.

The change in capacity is reflected in the second-stage model by the change in allocation vector. A careful examination of the second-stage problem shows that only the right-hand side vector of the LP needs to be modified for each re-optimisation. Hence, the dual feasible region does not change and the cuts in the L-shaped method are generated by using the extreme points of the dual feasible region for the second-stage problem. This leads to the following observation:

Observation 1

Let t₁<t₂<<T be the time points when the model is re-optimised, and T be the departure time. Assuming that the fares are static, the dual feasible region for the second-stage problem is the same for all re-optimisation points, thus the cuts generated at t_i can be used at time point t_j, j1.

Observation 1 reduces the number of major iterations performed by the L-shaped method, and thus improves the computation time requirements of the algorithm.

SIMULATION METHODOLOGY

The proposed SP models address some of the shortcomings of the DLP, but they are still stationary models. To test the performance of the models in a dynamic setting, a simulation methodology is utilised using a small hypothetical airline network with four cities and five flight legs.

Figure 2 illustrates a hypothetical airline network where the numbers on the arcs denote available capacities of corresponding flight legs. The network consists of six O&D pairs and ten itineraries. Furthermore, three fare classes (Business, Leisure-1 and Leisure-2) are offered for each O&D pair. Table 1 gives the corresponding remaining demand and fares for each O&D pair and fare class.

Figure 2.

Hypothetical airline network with five legs and six O&D pairs

Full figure and legend (8K)

Table 1 - Fares and forecasted remaining demand for sample.

Full table

Table 2 provides four simulation scenarios considered in this paper. In the first scenario, a single optimisation is executed to identify optimal booking limits at the beginning of the booking horizon. Demand arrivals are processed based on the assumption that customers may buy-up to any higher fare class regardless of the SP model under consideration. We permit buy-ups when demand arrivals are processed, although all models do not allow buy-ups.

Table 2 - Simulation scenarios.

Full table

In the second scenario, all models are optimised multiple times, and customers may buy-up to any higher fare class. More specifically, all models are executed at 20 equally spaced time periods (eg, days) within the booking horizon. Demand is assumed to follow a homogeneous Poisson process, which indicates that booking curves or profiles are linear from the beginning to the end of the booking horizon.

In the third scenario, SP models are also optimised multiple times, as in the second scenario, but customers are allowed to buy-up to the next fare class only.

Finally, the fourth scenario optimises SP models multiple times, but customers purchase the lowest available fare class at the time of the booking. If the original fare class is not the lowest fare, the corresponding buy-up probabilities are applied.

In addition, Table 3 summarises assumptions on buy-up behaviour, modelling controls and simulation controls. For example, the DLP model does not allow any buy-ups and produces partitioned booking limits. However, standard nesting is applied within a given O&D pair and fare class when processing the demand arrivals during the simulation. Similarly, SLP2 allows buy-ups to the next fare class only and produces partitioned booking limits. Again, we apply standard nesting during simulation. SLP3 allows buy-ups to any fare class and utilises theft nesting controls during both modelling and simulation.

Table 3 - Assumptions on buy-up behaviour and controls.

Full table

Each optimisation is executed for a given buy-up probability p. For example, a buy-up probability of 10 per cent indicates that on average 10 per cent of customers buy-up to the next fare class if their requested fare class is unavailable. If multiple buy-ups are allowed, it is assumed that customers continue to buy-up with the same probability. We test each model using p=0, 10, 20 and 30 per cent under the four simulation scenarios described in Table 2.

The simulation engine is used for each simulation scenario and optimisation model and works as given in Figure 3. The user inputs the number of time periods till departure (T), network structure, capacity, fares and remaining demand. In addition, time period t is initialised to 1, representing that the model will be solved for the first time period.

Figure 3.

Simulation flow diagram

Full figure and legend (32K)

The first optimisation scenario uses a single run, and thus T=1. Then, the NCC model is solved to obtain optimal booking limits. At the Initialisation Step, the random demand vectors used in RLPB, SLP1, SLP2 and SLP3 are generated from Poisson distributions whose expected value is provided in Table 1.

The procedure for obtaining booking limits depends on the model. Models DLP, DLPB and RLPB utilise a linear programming solver. The SP models SLP1, SLP2, and SLP3 utilise the L-shaped method provided in Figure 1, where S replications of N-sample problems are solved to obtain the corresponding set of optimal booking limits. Then, a demand arrival is randomly generated. If simulation time is greater than t and less than T, then we re-solve the NCC problem.

In this step, although the random demand vectors used in optimisation procedures are still generated from Poisson distributions, the expected demand in Table 1 are scaled by (T-t+1)/T. For example, the expected demand for Leisure-2 for Austin–Chicago O&D pair is 100 at the beginning of the booking horizon. Hence, the re-optimisation at t=6 assumes that the expected remaining demand is (20-6+1)/20 100=75.

Then, we decide whether to accept or reject the arriving customer. If the corresponding booking limit is not reached, accept the demand; else, check if the customer would buy-up based on the buy-up probability p. If the customer buys-up, we again check to see if the booking limits are reached for the new fare class. If the customer does not buy up, the booking request is denied. After that, we generate the next demand arrival and repeat the process.

As mentioned earlier, Monte Carlo sampling and L-shaped methods are used in the process of solving the SP models. For each model, 50 sample demand vectors are generated, and 100 replications of these 50-sample problems are solved. Next, the optimal booking limits are averaged and all non-integer booking limits are rounded to the closest integer. These booking limits are subsequently employed in the simulation. We avoided experimental bias by using independent random number streams to solve the SP models and to generate the actual arrival process.

NUMERICAL RESULTS

Optimisation models DLP, DLPB, RLPB, SLP1, SLP2 and SLP3 are executed using buy-up probabilities 0, 10, 20 and 30 per cent under four simulation scenarios given in Table 2. This section presents the findings for each simulation scenario.

Simulation scenario 1: Single optimisation and multiple buy-ups

In the first simulation scenario, each model is executed once to obtain the optimal booking limits for the entire booking horizon. Then, demand arrivals are randomly generated against the booking limits to estimate the expected revenue for each model. A customer request is fulfilled if the booking limit of the original fare class is not reached according to the simulation controls (see Table 3). Otherwise, buy-up probability p is applied to capture additional revenues from potential buy-ups. In this scenario, multiple buy-ups are allowed for each model when processing demand arrivals.

Figure 4 shows the expected increase in revenue by using each model relative to the revenue obtained from DLP. Corresponding numerical values are also given in Appendix C. When the buy-up probability is 0, SLP3 performs the best with a revenue ratio of 1.01 with respect to DLP. As buy-up probability increases, SLP1 performs better achieving 10 per cent higher revenue than DLP at buy-up probability of 0.3. The increase in revenue indicates that significant opportunities exist if the customer's buy-up behaviour is considered by the optimisation process.

Figure 4.

Expected ratio of revenue for each model relative to revenue from DLP under simulation scenario 1

Full figure and legend (25K)

Figure 5 shows the percentage of replications for which a given method outperforms other models; that is, obtains the highest revenue. When buy-up probability is 0, SLP3 performs better 80 per cent of the time. However, when buy-up probability is 0.3, SLP1 performs better 40 per cent of the time. When buy-up probability p=0, SLP3 with theft nesting performs best, as it has better protections for higher fare classes. As buy-up probabilities increase, SLP 1 performs best, as standard nesting captures some of the lower-level demand with more buy-ups. These results are consistent with the results given in Figure 4.

Figure 5.

Per cent of replications each model performs best under simulation scenario 1

Full figure and legend (39K)

Simulation scenario 2: Multiple optimisations and multiple buy-ups

The results of the first simulation scenario show that the SP approach outperforms DLP when the optimisation is executed once for the entire booking horizon. However, if booking limits are updated multiple times (20 times in our case), the performance of DLP increases significantly. This is intuitive and consistent with the results of previous studies (eg, Williamson, 1992). In the second scenario, the optimisation process is executed at 20 equally spaced time periods, and booking limits are revised and then imposed on the demand arrivals on the subsequent time period.

Figure 6 shows the expected increase in revenue from each model relative to the revenue from the DLP. Corresponding numerical values are also given in Appendix C. Figure 7 shows the percentage of replications for which a given method outperforms other models. Unlike Figure 4, Figure 6 shows that SLP3 does not have an advantage over other methods when optimised frequently. In this case, SLP1 outperforms the other methods, particularly when buy-up probability increases. When buy-up probability p is 0, DLPB outperforms other methods in 55 per cent of replications. However, the expected revenues are relatively close to each other. As buy-up probability increases, relative revenue improvements from SP models increase. For example, when the buy-up probability is 0.3, SLP1 outperforms other methods more than 60 per cent of the time and yields a revenue increase of over 10 per cent compared to the revenue obtained from DLP.

Figure 6.

Expected ratio of revenue from each model relative to revenue from DLP under simulation scenario 2

Full figure and legend (26K)

Figure 7.

Per cent of replications each model performs best under simulation scenario 2

Full figure and legend (39K)

Simulation scenario 3: Multiple optimisations and single buy-up

Similar to the second simulation scenario, the third simulation scenario executes the models 20 times, but customers are allowed to buy-up to the next fare class only when the booking limit of the original fare class is reached.

Figure 8 shows the expected increase in revenue from each model relative to the revenue from DLP, and Figure 9 shows the percentage of replications for which a given model outperforms other models. Figure 8 shows that all methods have similar performances over DLP for low buy-up probabilities. However, the performance of SP models increases as buy-up probability increases. Interestingly, SLP1 and DLP outperform SLP 2 for low buy-up probabilities, but SLP 2 outperforms all others when buy-up probability is 0.3. The revenue ratios used in Figure 8 are also given in Appendix C.

Figure 8.

Expected ratio of revenue from each model relative to revenue from DLP under simulation scenario 3

Full figure and legend (25K)

Figure 9.

Per cent of replications each model performs best under simulation scenario 3

Full figure and legend (37K)

Simulation scenario 4: Multiple optimisations and customers buy the lowest fare

The simulation scenarios above assumed that customers always want to buy their original fair class, and then buy-up when their original class is unavailable. However, customers tend to buy the lowest available fare. The final scenario simulates this situation. It is noted that this situation is known as delusion in RM literature (eg, Cooper et al., 2005).

Although we have not incorporated buy-downs into the models, we simulate the demand arrival process so that customers always buy the available lowest fare. In this scenario, buy-ups are still allowed when the original fare class and/or any lower fare classes are unavailable. Again, we assume multiple optimisations for 20 time periods.

Figure 10 shows the expected increase in revenue from each model relative to the revenue from DLP. The numerical values used to construct Figure 10 are also given in Appendix C. Figure 11 shows the percentage of replications for which a given method outperforms other models. As in other scenarios, the value of stochastic solution increases as buy-up probability increases. Because the SP models incorporate the variation in demand, they tend to protect more seats for higher fares, and thus produce smaller booking limits for lower fares. This leads to higher revenue gains from SP models as it allows less delusion.

Figure 10.

Expected ratio of revenue from each model relative to revenue from DLP under simulation scenario 4

Full figure and legend (24K)

Figure 11.

Per cent of replications each model performs best under simulation scenario 4

Full figure and legend (39K)

SUMMARY, CONCLUSIONS AND DIRECTIONS FOR FUTURE WORK

This paper proposes three new SP formulations for NCC problems based on different sets of assumptions. The first two formulations use partitioned booking limits, and the third formulation uses theft nesting.

Four simulation scenarios are considered to evaluate the performance of each model using different assumptions on buy-up behaviour and booking controls. The results indicate that SP formulations outperform both the deterministic and randomised linear programs by a significant margin. In addition, the stochastic models produce relatively higher revenue when customer buy-ups are allowed.

The proposed formulations can be further evaluated based on a range of customer buy-up assumptions. For example, each model is tested for a fixed buy-up probability p. It would be interesting to test the models using a distribution of buy-up probabilities. In addition, when multiple optimisations are executed before the day of departure, demand could be assumed to follow a non-homogenous Poisson process, and the performance of each model could be evaluated. In addition, the probabilistic structure presented in this paper can include overbooking decisions, which could be a topic of further research. Another key extension includes consideration of group arrivals. Models can also be tested against a larger network of flights, where both revenue and computational performances can be assessed.

Notes

¹ Capacity control is also referred to as inventory control and demand rationing.

References

1. Algers, S. and Besser, M. (2001) 'Modelling choice of flight and booking class: a study using stated preference and revealed preference data', International Journal of Services Technology and Management, 2, 28–45. | Article |
2. Andersson, S. E. (1989) 'Operational planning in airline business– can science improve efficiency? Experience form sas', European Journal of Operational Research, 43, 3–12. | Article |
3. Andersson, S. E. (1998) 'Passenger choice analysis for seat capacity control: a pilot project in Scandinavian airlines', International Transaction in Operations Research, 5, 471–486. | Article |
4. Belobaba, P. P. (1987a) 'Airline yield management: an overview of seat inventory control', Transportation Science, 21, 63–73. | ISI |
5. Belobaba, P. P. (1987b) 'Air Travel Demand and Airline Seat Inventory Management', PhD thesis, Flight Transportation Laboratory, MIT, Cambridge, MA.
6. Belobaba, P. P. (1989) 'Application of probabilistic decision model to airline seat inventory control', Operations Research, 37, 183–197. | ISI |
7. Belobaba, P. P. and Weatherford, L. R. (1996) 'Comparing decision rules that incorporate customer diversion in perishable asset revenue management situations', Decision Sciences, 27, 343–363.
8. Bertsimas, D. J. and de Boer, S. (2001) 'A Stochastic Booking Limit Policy for Airline Network Revenue Management', Technical Report, Operations Research Center, MIT, Cambridge, MA.
9. Birge, J. R. and Louveaux, F. (1997) Introduction to Stochastic Programming, Springer-Verlag, New York.
10. Boyd, E. A. and Kallesen, R. (2004) 'The science of revenue management when passengers purchase the lowest available fare', Journal of Revenue and Pricing Management, 3, 171–177. | Article |
11. Chen, L. and Homem-de-Mello, T. (2004) 'Multi-Stage Stochastic Programming Models for Airline Revenue Management', Technical Report 04-012, Northwestern University, Evanston, IL.
12. Cooper, W. L. and Homem-de-Mello, T. (2003) 'A Class of Hybrid Methods for Revenue Management', Technical Report 03-015, Northwestern University, Evanston, IL.
13. Cooper, W. L., Homem-de-Mello, T. and Kleywegt, A. J. (2005) 'Model of the spiral-down effect in revenue management', Operations Research, Submitted.
14. Cross, R. G. (1997) Revenue Management, Broadway, New York, NY.
15. de Boer, S., Freling, R. and Piersma, N. (2002) 'Stochastic programming for multiple-leg network revenue management', European Journal of Operational Research, 137, 72–92. | Article |
16. D'Sylva, E. (1982) 'O&D Seat Assignment to Maximize Expected revenue', Technical Report, Boeing Commercial Airplane Company.
17. Gallego, G., Iyengar, G., Phillips, R. and Dubey, A. (2004) 'Managing Flexible Products on a Network', Technical Report TR-2004-01, CORC.
18. Glover, F., Glover, R., Lorenzo, J. and McMillan, c. (1982) 'The passenger-mix problem in the scheduled airlines', Interfaces, 12, 73–80. | ISI |
19. Higle, J. L. (2007) 'Bid-price control with origin–destination demand: a stochastic programming approach', Journal of Revenue and Pricing Management, 5, 291–304. | Article |
20. Higle, J. L. and Sen, S. (2005) 'A stochastic programming model for network resource utilization in the presence of multiclass demand uncertainty', in: Wallace, S. W. and Ziemba, W. T. (eds) Applications of Stochastic Programming, MPS-SIAM Series on Optimization, SIAM, Philadelphia, PA, 299–313.
21. Jiang, H. and Miglionico, G. (2006) 'Airline revenue management with buy-up', Working Paper.
22. Kulkarni, V. G. (1995) Modeling and Analysis of Stochastic Systems, Chapman & Hall, London.
23. Lee, T. and Hersh, M. (1993) 'A model for dynamic airline seat inventory control with multiple seat bookings', Transportation Science, 27, 1252–1256.
24. Littlewood, K. (1972) 'Forecasting and control of passenger bookings', 12th AGIFORS Symposium Proceedings, Nathanya, Israel, 95–128.
25. Mahajan, S. and van Ryzin, G. J. (2001) 'Stocking retail assortments under dynamic customer substitution', Operations Research, 49, 334–351. | Article |
26. Möller, A., Römisch, W. and Weber, K. (2004) 'A new approach to O&D revenue management based on scenario trees', Journal of Revenue and Pricing Management, 3, 265–276. | Article |
27. Pfeifer, P. E. (1989) 'The airline discount-fare allocation problem', Decision Sciences, 10, (20), 149–157. | Article |
28. Phillips, R. L. (2005) Pricing and Revenue Optimization, Stanford University Press, Stanford, CA.
29. Shapiro, A. (2003) 'Monte Carlo sampling methods', in: Ruszczyski, A. and Shapiro, A. (eds) Stochastic Programming , Handbooks in Operations Research and Management Science, Elsevier, Amsterdam.
30. Smith, B. C., Leimkuhler, J. F. and Darrow, R. M. (1992) 'Yield management at American airlines', Interfaces, 22, 8–31. | ISI |
31. Talluri, K. T. and van Ryzin, G. J. (1999) 'A randomized linear programming method for computing bid prices', Transportation Science, 33, 207–216. | ISI |
32. Talluri, K. T. and van Ryzin, G. J. (2004a) The Theory and Practice of Revenue Management, Kluwer Academic Publishers, Dordrecht, MA.
33. Talluri, K. T. and van Ryzin, G. J. (2004b) 'Revenue management under a general discrete choice model on consumer behavior', Management Science, 50, 15–33. | Article | ISI |
34. van Ryzin, G. J. and Liu, Q. (2004) 'On the Choice Based Linear Programming Model for Network Revenue Management', Technical Report DRO-2004-04, Columbia Business School.
35. van Ryzin, G. J. and Vulcano, G. (2003) 'Simulation-Based Optimization of Virtual Nesting Controls for Network Revenue Management', Technical Report DRO-2003-01, Columbia Business School.
36. van Ryzin, G. J. and Vulcano, G. (2004) 'Computing Virtual Nesting Controls for Network Revenue Management Under Customer Choice Behavior', Technical Report DRO-2004-09, Columbia Business School.
37. van Slyke, R. M. and Wets, R. J. -B. (1969) 'L-shaped linear programs with applications to optimal control and stochastic programming', SIAM Journal of Applied Mathematics, 17, 638–663. | Article |
38. Vulcano, G., Méndez-Díaz, I. and Miranda Bront, J. (2007) 'A column generation algorithm for choice-based network revenue management', Working Paper.
39. Williamson, E. L. (1992) 'Airline Network Seat Inventory Control: Methodologies and Revenue Impacts', PhD thesis, Flight Transportation Laboratory, MIT, Cambridge, MA.
40. Wollmer, R. D. (1986) 'A Hub-and-Spoke Seat Management Model', Technical Report, Douglas Aircraft Company, McDonnell Douglas Corporation.
41. Zhang, D. and Cooper, W. L. (2005) 'Revenue management for parallel flights with customer-choice behavior', Operations Research, 53, 415–431. | Article | ISI |

Appendices

Appendix A

Proof of Theorem 1 To prove that z_SLP1z_DLPB, we show that h(u, ) given in (3a), (3b), (3c), (3d) and (3e) is concave in . For this purpose, we take the dual of (3a), (3b), (3c), (3d) and (3e). To simplify the notation the feasible set of the dual problem is denoted by . Letting and be the dual variables corresponding to the constraints (3d) and (3c), (3b) respectively, we write

Hence for (0, 1),

which proves the concavity of h(u, ). Let (x^*, u^*) be an optimal solution of SLP1,

The first inequality above follows from Jensen's inequality and the second inequality from feasibility of (x^*, u^*) for the deterministic problem. 

Appendix B

See Table B1.

Table B1 - Table of notation.

Full table

Appendix C

See Table C1, C2, C3 and C4.

Table C1 - Results for simulation scenario 1 (Ratio w.r.t. DLP).

Full table

Table C2 - Results for simulation scenario 2 (Ratio w.r.t. DLP).

Full table

Table C3 - Results for simulation scenario 3 (Ratio w.r.t. DLP).

Full table

Table C4 - Results for simulation scenario 4 (Ratio w.r.t. DLP).

Full table

Acknowledgements

The authors would like to thank Dr John J. Hasenbein and Dr David P. Morton of The University of Texas at Austin for their support and invaluable discussions. We would like to also thank the anonymous referees for their helpful suggestions.