In this paper, we develop a revenue management model to jointly make the capacity allocation and overbooking decisions over an airline network. Our approach begins with the dynamic programming formulation of the capacity allocation and overbooking problem and uses an approximation strategy to decompose the dynamic programming formulation by the flight legs. This decomposition idea opens up the possibility of obtaining approximate solutions by concentrating on one flight leg at a time, but the capacity allocation and overbooking problem that takes place over a single flight leg still turns out to be intractable. We use a state aggregation approach to obtain high quality solutions to the single leg problem. Overall, our model constructs separable approximations to the value functions, which can be used to make the capacity allocation and overbooking decisions for the whole airline network. Computational experiments indicate that our model performs significantly better than a variety of benchmark strategies from the literature. Capacity allocation and overbooking are two main ingredients of network revenue management. In particular, capacity allocation deals with the question of which itineraries to keep open for purchase and which itineraries to close as the remaining capacities on the flight legs are depleted over time with the customer purchases. Overbooking deals with the question of to what extent the sales should exceed the physically available capacity on the flight legs, given that not everyone with a reservation ends up showing up at the departure time. The capacity allocation and overbooking decisions are inherently connected. What fare classes to make available for purchase depends on how many seats in excess of the physically available capacity the airline is willing to sell. On the other hand, how much to overbook depends on what itineraries the airline keeps open and the probability that a customer who purchases a reservation for one of the open itineraries shows up at the departure time. In this paper, we propose a revenue management model that makes the joint capacity allocation and overbooking decisions over an airline network. Our approach formulates the problem as a dynamic program and uses an approximation strategy to decompose the dynamic programming formulation by the flight legs. This decomposition idea opens up the possibility of obtaining approximate solutions by concentrating on one flight leg at a time, though the capacity allocation and overbooking problem that takes place over a single flight leg still happens to be intractable. In particular, the state variable in the dynamic programming formulation of the single leg problem involves a large number of dimensions in practical applications. We overcome this difficulty by using state aggregation to obtain high quality solutions to the single leg capacity allocation and overbooking problem. Ultimately, our model provides separable approximations to the value functions, which can be used to construct a capacity allocation and overbooking policy for the whole airline network. Our work in this paper draws on two streams of literature. The first stream of literature is the work on dynamic programming decomposition methods in network revenue management. Dynamic programming decomposition methods date back to Belobaba (1987) and they are approximate methods aimed at decomposing the network revenue management problem by the flight legs. The basic idea is to associate a displacement adjusted fare with each itinerary over each flight leg, which is different from the actual fare that the airline charges. The displacement adjusted fares immediately allow us to solve a sequence of single leg revenue management problems. In the single leg revenue management problem that takes place over a particular flight leg, we only concentrate on the remaining capacity on this flight leg and assume that the fares associated with the itineraries are equal to the displacement adjusted fares over this flight leg. Once we have solved the single leg problem over each flight leg, we add up the value functions obtained for different flight legs to obtain separable approximations to the value functions. In this paper, we use a similar idea to decompose the capacity allocation and overbooking problem. The important distinction of our paper is that we explicitly deal with overbooking, whereas the earlier decomposition methods work exclusively under the assumption that overbooking is not possible and all reservations show up at the departure time. Our extension to overbooking is nontrivial and has important practical implications as overbooking plays a major role in airline operations. The second stream of literature that we draw on is the work on solving the capacity allocation and overbooking problem over a single flight leg. This stream of literature becomes especially useful 2 when we try to solve the single leg capacity allocation and overbooking problems after decomposing the original problem. As mentioned above, the single leg capacity allocation and overbooking problem is intractable, as its dynamic programming formulation involves a high dimensional state variable. To be able to solve this problem, we build on the approach proposed by Subramanian et al. (1999) . In particular, we assume that the proportions of the reservations that we have for different itineraries are fixed and known. This allows us to keep track of only the total number of reservations, rather than the number of reservations for each itinerary, in our dynamic programming formulation. In this case, the state variable in the dynamic programming formulation of the single leg problem collapses to a scalar and the dynamic programming formulation becomes tractable. In this paper, we make the following research contributions. 1) We develop a model to make the capacity allocation and overbooking decisions over an airline network. The idea behind our model is to decompose the problem by the flight legs and to solve a sequence of single leg problems. 2) We show that our approach provides an upper bound on the optimal total expected profit as long as we can solve the single leg problems accurately. 3) However, noting that the capacity allocation and overbooking problem over a single flight leg is still intractable, we show how to obtain approximate solutions to the single leg problems in a tractable manner. 4) Computational experiments indicate that our model performs significantly better than many of the existing models in the literature. The rest of the paper is organized as follows. In Section 1, we review the other literature that is related to our work. In Section 2, we give a dynamic programming formulation for the capacity allocation and overbooking problem over an airline network. In Section 3, we give a simple deterministic linear program that can be used to develop control policies. In Section 4, we describe our model by using the deterministic linear program as a starting point. In Section 5, we present our computational experiments. In Section 6, we provide concluding remarks. Despite the fact that there is substantial literature on capacity allocation over an airline network, the interaction between capacity allocation and overbooking is not thoroughly studied. Early models focus on the single leg version of the problem. Beckmann (1958) , Thompson (1961) and Coughlan (1999) develop single leg capacity allocation and overbooking models under the assumption that the demands from different fare classes are static random variables. These models ignore the temporal dynamics of the demand process and their goal is to decide how many seats to allocate to different fare classes. Later models by Chatwin (1992) , Chatwin (1999) and Subramanian et al. (1999) also consider the single leg problem, but they try to capture the dynamics of the demand process more accurately. Subramanian et al. (1999) note the intractability of the dynamic programming formulation of the single leg problem and propose the approximation strategy that we build on in this paper. It is important to contrast their observation with the single leg capacity allocation problem without overbooking. If overbooking is not allowed, then the dynamic programming formulation of the capacity allocation problem involves a scalar state variable and can easily be solved. Therefore, the possibility of overbooking, by itself, brings nontrivial challenges even for the single leg case. Karaesmen and van Ryzin (2004b) describe an 3 overbooking model for multiple flight legs that operate between the same origin destination pair and can serve as substitutes of each other. There are a few papers that consider the overbooking decisions over an airline network. A popular method to make the capacity allocation decisions in network revenue management problems is to solve a deterministic linear program. This linear program is built under the assumption that the itinerary requests are known in advance and they take on their expected values. There is a constraint associated with each flight leg in the linear program and the right sides of these constraints are the leg capacities. Therefore, the optimal values of the dual variables associated with these constraints are used to estimate the opportunity cost of a seat on different flights legs. In this case, one can construct a capacity control policy, where the fare from an itinerary request is compared with the total opportunity cost of the capacities that would be consumed by this itinerary request. If the fare exceeds the total opportunity cost, then the itinerary request is accepted. There are many variants of the linear programming idea and Section 3.3 in Talluri and van Ryzin (2004) describes these variants. We do not go into the details of these variants, as most of them deal only with capacity allocation decisions. However, Bertsimas and Popescu (2003) show how to build a deterministic linear program to deal with overbooking and no shows. We use a variant of their deterministic linear program as a benchmark strategy in our computational experiments. Karaesmen and van Ryzin (2004a) develop a capacity allocation and overbooking model, where they compute booking limits by using the optimal objective value of the deterministic linear program as an estimate of the total expected revenue from the itinerary requests. Gallego and van Ryzin (1997) provide theoretical support for the deterministic linear program by showing that the control policy obtained from a variant of the deterministic linear program is asymptotically optimal as the leg capacities and the expected number of itinerary requests increase linearly at the same rate. Kleywegt (2001) constructs a pricing and overbooking model in continuous time. The demand process that he uses is deterministic and he utilizes Lagrangian duality to solve the model. The literature on decomposition of network revenue management problems is also related to our paper. Williamson (1992) is one of the first to decompose the network revenue management problem by the flight legs. Her goal is to apply the expected marginal seat revenue heuristic of Belobaba (1987) on each flight leg individually to construct value function approximations. Section 3.4.4 in Talluri and van Ryzin (2004) describes a more refined variant of her approach in the sense that this variant does not assume that the demand from different fare classes arrive over nonoverlapping time intervals. Liu and van Ryzin (2008) and Bront et al. (2008) show how to extend decomposition methods to address the customer choice behavior among the different itineraries that are available for purchase. Topaloglu (2006) shows that decomposition methods can be visualized as an application of Lagrangian relaxation to the dynamic programming formulation of the network revenue management problem. Kunnumkal and Topaloglu (2007) show that it is possible to extend the observations of Topaloglu (2006) to address the customer choice behavior. There is some recent work on decomposing the capacity allocation and overbooking problem over an airline network. Erdelyi and Topaloglu (2009) use separable functions to approximate the value functions in the dynamic programming formulation of the capacity allocation and overbooking problem. In this respect, their paper is connected to our work. However, their approximations are separable by the itineraries and the number of scalar functions they keep is equal 4 to the number of possible itineraries. In contrast, our approximations are separable by the flight legs and the number of scalar functions we keep is equal to the number of flight legs. The number of flight legs is generally smaller than the number of itineraries. Furthermore, they use simulation to construct their scalar functions, whereas we solve small dynamic programs to construct our value function approximations. We use their model as a benchmark strategy. There are recent approaches for the capacity allocation problem over an airline network. Adelman (2007) uses linear value function approximations for the capacity allocation problem and he chooses the slopes and intercepts of the value function approximations by solving a linear program that represents the dynamic programming formulation of the problem. Zhang and Adelman (2006) extend this approach to deal with the customer choice behavior. They also show that decomposition methods can provide upper bounds on the optimal total expected revenue. Meissner and Strauss (2008) refine the approach proposed by Adelman (2007) by using piecewise linear value function approximations. An important advantage of the recent approaches is that they provide upper bounds on the optimal total expected revenue. However, the recent approaches do not address the interaction between capacity allocation and overbooking and the goal of our paper is to fill this gap. We consider a set of flight legs over an airline network that can be used to serve the itinerary requests arriving randomly over time. At each time period, an itinerary request arrives and we need to decide whether to accept or reject this itinerary request. An accepted itinerary request becomes a reservation, whereas a rejected itinerary request simply leaves the system. At the departure time of the flight legs, a certain portion of reservations shows up and we need to decide which of these reservations should be allowed boarding. The objective is to maximize total expected profit defined as the difference between the expected revenue obtained by accepting itinerary requests and the expected penalty cost incurred by denying boarding to reservations. The set of flight legs is L and the set of itineraries is J . We note that a flight leg is referred to as a resource and an itinerary is referred to as a product in some settings. The problem takes place over the finite planning horizon {τ, . . . , 0}. The itinerary requests arrive over time periods T = {τ, . . . , 1} and the flights depart at time period 0. The probability that there is a request for itinerary j at time period t is p jt . Accepting a request for itinerary j generates a revenue of f j and this reservation shows up at the departure time with probability q j . If a reservation for itinerary j shows up at the departure time and it is denied boarding, then we incur deny penalty cost of θ j . If we allow boarding to a reservation for itinerary j, then we consume a ij units of capacity on flight leg i. The capacity on flight leg i is c i . We assume that the arrivals of the itinerary requests at different time periods and the show up decisions of different reservations at the departure time are independent. We also assume that the reservations are not canceled over time periods {τ, . . . , 1} and we do not give refunds to the no shows, but these assumptions are for brevity and one can make extensions to address cancellations and refunds. We let x jt denote the total number of reservations for itinerary j at the beginning of time period t so that x t = {x jt : j ∈ J } captures the state of the reservations. Assuming that the number 5 of reservations for itinerary j at the beginning of time period 0 is x j0 , we use S j (x j0 ) to denote the number of reservations for itinerary j that show up at the departure time. Given the assumption that the show up decisions of different reservations are independent, S j (x j0 ) has a binomial distribution with parameters (x j0 , q j ). If we use S(x 0 ) = {S j (x j0 ) : j ∈ J } to denote the state of the reservations that show up at the departure time, then we can compute the penalty cost associated with the denied reservations by solving the problem where w j is the number of reservations for itinerary j that we deny boarding. The objective function of the problem above corresponds to the penalty costs associated with the denied reservations. Constraints (2) ensure that the reservations that we allow boarding do not exceed the leg capacities, whereas constraints (3) ensure that the numbers of denied reservations do not exceed the numbers of reservations that show up at the departure time. It is important to observe that problem (1)- (4) assumes that we can jointly decide which reservations should be denied boarding throughout the network and this can be an optimistic assumption. Letting e j be the |J | dimensional unit vector with a one in the element corresponding to j, we can find the optimal policy by computing the value functions through the optimality equation with the boundary condition that V 0 (x 0 ) = −E{Γ(S(x 0 ))}. In this case, if the state of the reservations at the beginning of time period t is given by x t , then it is optimal to accept a request for itinerary j at time period t whenever Unfortunately, even for modest sized applications, the state vector x t involves hundreds of dimensions rendering exact solution to the optimality equation in (5) computationally intractable. In next section, we begin by describing an approximate solution method that involves solving a deterministic linear program. Following this, we build on the deterministic linear program to develop a more sophisticated approximate solution method. A standard solution method for the network revenue management problem described in the previous section involves solving a deterministic linear program. This linear program is formulated under the assumption that the arrivals of the itinerary requests and the show up decisions of the reservations take on their expected values. In particular, if we let z j be the number of requests for itinerary j that we 6 plan to accept over the planning horizon and w j be the number of reservations that we plan to deny boarding, then this linear program can be formulated as In the problem above, we assume that if we accept z j requests for itinerary j, then q j z j reservations for itinerary j show up at the departure time. Constraints (8) ensure that the numbers of reservations that we allow boarding do not exceed the leg capacities. Constraints (9) ensure that the numbers of itinerary requests that we accept do not exceed the expected numbers of itinerary requests. Constraints (10) ensure that the numbers of denied reservations do not exceed the expected numbers of reservations that show up at the departure time. The deterministic linear programming formulation for the network revenue management problem is widely known under the assumption that overbooking is not possible and all reservations show up at the departure time; see Talluri and van Ryzin (1998). Problem (7)- (11) extends this formulation to handle overbooking and no shows. Although this extension is quite intuitive, to our knowledge, Bertsimas and Popescu (2003) is the only reference to this extension. One use of problem (7)- (11) is that its dual solution can be used to construct a policy to accept or reject the itinerary requests. Letting {λ * i : i ∈ L} be optimal values of the dual variables associated with constraints (8) in problem (7)-(11), the idea is to use λ * i to estimate the opportunity cost of a unit of capacity on flight leg i. In this case, if the revenue from an itinerary request exceeds the total expected opportunity cost of the capacities consumed by this itinerary request or if the revenue from an itinerary request exceeds the expected penalty cost, then we accept the itinerary request. In other words, if we have then we accept a request for itinerary j. The two arguments of the min{·, ·} operator above capture two effects. If the total expected opportunity cost of the capacities consumed by a request for itinerary j is small enough that we have f j ≥ q j i∈L a ij λ * i , then we accept a request for itinerary j. Furthermore, if we have f j ≥ q j θ j , then we can generate revenue, in expectation, simply by accepting a request for itinerary j and denying boarding to this reservation at the departure time. We refer to the decision rule in (12) as the DLP policy, standing for deterministic linear program. This decision rule is also used by Bertsimas and Popescu (2003) . One other use of problem (7)- (11) is that its optimal objective value provides an upper bound on the optimal total expected profit. In other words, letting z LP be the optimal objective value of problem (7)-(11) and0 be the |J | dimensional vector of zeros, it is possible to show that V τ (0) ≤ z LP . For 7 future reference, we state this result as a proposition below. The proof of this proposition can be found in Erdelyi and Topaloglu (2009) . The upper bound in Proposition 1 can be useful when assessing the optimality gap of a suboptimal decision rule such as the DLP policy in (12). There are several shortcomings of the deterministic linear program. It only uses the total expected numbers of the itinerary requests, ignoring the probability distributions and the temporal dynamics of the arrivals of the itinerary requests. Furthermore, it assumes that the numbers of reservations that show up at the departure time take on their expected values. In this section, we build on the deterministic linear program to develop a solution method that captures the temporal dynamics of the itinerary requests somewhat more accurately. The starting point for our approach is a duality argument on the deterministic linear program to decompose the network revenue management problem into a sequence of single leg revenue management problems. We begin letting {λ * i : i ∈ L} be the optimal values of the dual variables associated with constraints (8) in problem (7)-(11). We choose an arbitrary flight leg i and relax constraints (8) in problem (7)-(11) for all other flight legs by associating the dual multipliers {λ * l : l ∈ L \ {i}}. In this case, linear programming duality implies that problem (7)-(11) has the same optimal objective value as the problem We note that the problem above includes the capacity constraint only for flight leg i. For notational brevity, we let Λ Omitting the constant term l∈L\{i} λ * l c l , we write the problem above as subject to (9), (10), (11), 8 in which case, the optimal objective value of problem (14)- (16)  The decision variables z j and w j do not appear in constraint (15) whenever itinerary j does not use the capacity on flight leg i. This observation allows us to decompose problem (14)-(16) into two problems, one of which involves the itineraries that use the capacity on flight leg i and the other one involves the remaining itineraries. To this end, we let J i = {j ∈ J : a ij > 0} so that J i is the set of itineraries that use the capacity on flight leg i. In this case, it is easy to see that the optimal objective value of problem (14)- (16) is equal to the sum of the optimal objective values of the problem subject to which involves only the decision variables {z j : j ∈ J i } and {w j : j ∈ J i }, and the problem which involves only the decision variables {z j : j ∈ J \ J i } and {w j : j ∈ J \ J i }. It turns out that the optimal objective value of problem (22)- (25) can easily be obtained by mere inspection. In particular, we show in Appendix A that the optimal objective value of problem (22)- (25) is equal to . Therefore, summing up the discussion so far in this section, if we let z i LP be the optimal objective value of problem (17)- (21), then we have Comparing problem (17)- (21) with problem (7)- (11), we can observe that problem (17)- (21) is the deterministic linear program corresponding to a single leg revenue management problem that takes place over flight leg i. In this single leg revenue management problem, only the requests for the itineraries in the set J i are considered. If we accept a request for itinerary j, then we generate a revenue of F i j . If we deny boarding to a reservation for itinerary j, then we incur a penalty cost of Θ i j . Noting that the optimal objective value of problem (17)- (21) is denoted by z i LP , Proposition 1 implies that z i LP provides an upper bound on the optimal total expected profit for the single leg revenue management problem that takes place over flight leg i. On the other hand, we can compute the optimal total expected profit for the above described single leg revenue management problem taking place over flight leg i by solving the corresponding dynamic program. To this end, we introduce some new notation. We let R i (·) be the operator that restricts the components of a |J | dimensional vector to those that correspond to the elements of J i . For example, we have R i (x t ) = {x jt : j ∈ J i } and R i (S(x 0 )) = {S j (x j0 ) : j ∈ J i }. In this case, the optimality equation for the single leg revenue management problem that takes place over flight leg i reads (27) with the boundary condition that Here, Γ i (·) accounts for the penalty cost of denied boarding at the departure time in the single leg revenue management problem that takes place over flight leg i and it is given by subject to We recall that z i LP provides an upper bound on the optimal total expected profit for the single leg revenue management problem that takes place over flight leg i. This optimal total expected profit is given by V i τ (R i (0)) so that we obtain V i τ (R i (0)) ≤ z i LP . The next proposition shows the relationship between the solutions to the optimality equations in (5) and (27). Its proof is in Appendix B. Using Proposition 2 with t = τ and x t =0, the discussion just before this proposition implies that where the last equality follows from (26). Therefore, we can obtain an upper bound on the optimal total expected profit by solving the optimality equation in (27) and this upper bound is tighter than the one provided by the optimal objective value of problem (7)- (11). Nevertheless, the state variable in 10 the optimality equation in (27) has still |J i | dimensions, which can be quite large for many practical applications. Before we describe one method to approximate the solution to this optimality equation, we take a quick detour in the next section and describe how we can use the upper bound in Proposition 2 to construct a policy to accept or reject the itinerary requests. Proposition 2 suggests approximating V t (x t ) with the upper bound given by the expression on the right side of (32). In particular, usingṼ i t (x t ) to denote the expression on the right side of (32), we can replace V t−1 (x t ) − V t−1 (x t + e j ) in the decision rule in (6) withṼ i t−1 (x t ) −Ṽ i t−1 (x t + e j ) and follow this decision rule to accept or reject the itinerary requests. One ambiguous aspect of this approach is that the choice of flight leg i is arbitrary and the performance of the proposed decision rule can depend on the choice of this flight leg. We work around this ambiguity by computing {Ṽ i t (·) : t ∈ T } for all i ∈ L so that we can use the average i∈LṼ i t (x t )/|L| as an approximation to V t (x t ). Noting thatṼ i t (x t ) ≥ V t (x t ) for all i ∈ L, we still have the upper bound that i∈LṼ i t (x t )/|L| ≥ V t (x t ). Thus, we propose approximating V t−1 (x t ) − V t−1 (x t + e j ) on the right side of (6) by i∈LṼ i t−1 (x t )/|L| − i∈LṼ i t−1 (x t + e j )/|L|. The definition ofṼ i t (x t ) in (32) implies that Therefore, letting 1(·) be the indicator function, if the state of the reservations at time period t is given by x t , then we accept a request for itinerary j whenever we have One possible way to look at the decision rule in (33) is that each flight leg contributes one term to the expression on the right side. If flight leg i is used by itinerary j, then this flight leg contributes the term If, on the other hand, flight leg i is not used by itinerary j, then this flight leg contributes the term min{q j l∈L a lj λ * l , q j θ j }. The important observation is that the term min{q j l∈L a lj λ * l , q j θ j } is identical to the right side of the DLP policy in (12). Therefore, the flight legs that are not used by itinerary j do not provide any additional information over what is already provided by the deterministic linear program. Furthermore, the number of flight legs that are not used by itinerary j is likely to be substantially larger than the number of flight legs that are used by itinerary j, which implies that the right side of the expression above is likely to be dominated by the term min{q j l∈L a lj λ * l , q j θ j }. Thus, one conjectures that the decision rule in (33) performs very much like the DLP policy. A small set of computational experiments confirmed this conjecture. To overcome this shortcoming, instead of averaging over all flight legs and using i∈LṼ i t (x t )/|L| as an approximation to V t (x t ), we average only over the flight legs that are used by a particular itinerary. In particular, we let L j = {i ∈ L : a ij > 0} so that L j is the set of flight legs that are used by itinerary j. In this case, whenever we need to make a decision for itinerary j, we use i∈L jṼ i t (x t )/|L j | as an approximation to V t (x t ). We note that we still have the upper bound that i∈L jṼ i t (x t )/|L j | ≥ V t (x t ). Thus, if the state of the reservations at time period t is given by x t , then we accept a request for itinerary j whenever we have The state variable in the optimality equation in (27) has |J i | dimensions. Theoretically, this is an improvement in comparison to the optimality equation in (5), which involves a state variable with |J | dimensions. Practically, however, this improvement is irrelevant as |J i | is on the order of hundreds or thousands even for modest applications. Therefore, it is still quite difficult to compute the value functions {V i t (·) : t ∈ T } and to use the decision rule in (34). In the next section, we give one method to approximate the value functions {V i t (·) : t ∈ T }, which seems to work particularly well for our application context. In this section, we consider the single leg revenue management problem that takes place over flight leg i whose dynamic programming formulation is given in (27). Our goal is to approximate the value functions {V i t (·) : t ∈ T } by using simple scalar functions. We observe that the optimality equation in (27) has to keep track of the "identities" of the reservations so that the penalty cost given by the optimal objective value of problem (28)-(31) can be computed properly. On the other hand, if we assume that knowing the total number of reservations is adequate to compute the penalty cost, then the state variable in the optimality equation in (27) collapses to a scalar. Our approximation builds on this observation and it is based on approximating the expected penalty cost at the departure time by using only the total number of reservations. We begin by introducing some new notation. We use A i (·) to denote the operator that adds up the components of a |J | dimensional vector corresponding to the elements of the set J i . For example, we have A i (x t ) = j∈J i x jt and A i (x t ) is the total number of reservations at the beginning of time period t for the itineraries that use flight leg i. Our approximation is based on the assumption that if we have a total of A i (x 0 ) reservations at the beginning of time period 0 for the itineraries that use flight leg i, then a fixed portion, say α i j , of these reservations are for itinerary j. In this case, recalling that the random variable S j (·) captures the number of reservations for itinerary j that show up at the departure time and defining the vectors we can approximate the penalty cost at the departure time by Γ i (S i (α i A i (x 0 ))). In this expression, the vector α i A i (x 0 ) approximates the numbers of reservations that we have at the beginning of time period 0, whereas the vector S i (α i A i (x 0 )) gives the numbers of reservations that show up at the departure time. The function Γ i (·) is given by the optimal objective value of problem (28)- (31) and it computes the penalty cost for the single leg revenue management problem that takes place over flight leg i. This approximation to the penalty cost at the departure 12 time, in turn, allows us to approximate the solution to the optimality equation in (27) by using the solution to the optimality equation (35) with the boundary condition that We note that the optimality equation above involves a scalar state variable and it can be solved quite efficiently. There are three issues that need to be resolved to be able to find a numerical solution to the optimality equation in (35). The first issue is related to the choice of α i j . We use the DLP policy in (12) for this purpose. In particular, we simulate the trajectory of the DLP policy under M itinerary request realizations. Letting {x m jt : j ∈ J , t ∈ T } be the state trajectory in the mth itinerary request realization, we let In practice, it is common to use the DLP policy to come up with an average probability that a reservation shows up at the departure time. Our choice of α i j closely follows this approach. The second issue arises due to the fact that the argument of S j (·) in the vector ) is a binomially distributed random variable with parameters (x j0 , q j ), but a binomially distributed random variable with a fractional trial parameter is ill-defined. We overcome this issue by always visualizing S j (x j0 ) as a mixture of two binomially distributed random variables. In particular, letting · be the round down function, with probability x j0 + 1 − x j0 , S j (x j0 ) is equal to a binomially distributed random variable with parameters ( x j0 , q j ), and with probability x j0 − x j0 , S j (x j0 ) is equal to a binomially distributed random variable with parameters ( x j0 + 1, q j ). With this convention, if x j0 is integer, then S j (x j0 ) continues to be binomially distributed with parameters (x j0 , q j ). If, however, x j0 is fractional, then S j (x j0 ) is not necessarily binomially distributed, but its expected value continues to be ( Finally, the third issue becomes apparent when we note that the boundary condition of the optimality equation in (35) requires computing the expectation ). There is no closed form expression for this expectation and we simply approximate it through Monte Carlo samples. Once we agree on the resolution of the three issues described above, we can obtain {v i t (·) : i ∈ L, t ∈ T } through the optimality equation in (35) and use {v i t (·) : i ∈ L, t ∈ T } as approximations to {V i t (·) : i ∈ L, t ∈ T } in the decision rule in (34). In particular, if the state of the reservations at the beginning of time period t is given by x t , then we accept a request for itinerary j whenever we have We refer to this decision rule as DPD policy, standing for dynamic programming decomposition. 13 In this section, we compare the performances of the decision rules in (12) and (36), along with other benchmark strategies. We begin by describing the experimental setup and the benchmark strategies. Following this, we present our computational results. We consider an airline network that consists of a hub and N spokes. This is a key network structure that frequently arises in practice. There are two flight legs associated with each spoke. One of these is from the hub to the spoke, whereas the other one is from the spoke to the hub. The airline offers a high fare and a low fare itinerary associated with each origin destination pair. Therefore, the number of flight legs is 2N and the number of itineraries is 2N (N + 1) . The fare associated with a high fare itinerary is κ times the fare associated with the corresponding low fare itinerary. The penalty cost of denying boarding to a reservation for itinerary j is given by θ j = δ f j + σ max{f : ∈ J }, where δ and σ are two parameters that we change. The probability that a reservation shows up at the departure time is q and it does not depend on the itinerary. Noting that the total expected demand for the capacity on flight leg i is given by q t∈T j∈J a ij p jt , we measure the tightness of the leg capacities by We label our test problems by (N, κ, δ, σ, q, ρ) and use N ∈ {4, 8}, κ ∈ {4, 8}, (δ, σ) ∈ {(4, 0), (8, 0), (1, 1)}, q ∈ {0.90, 0.95} and ρ ∈ {1.2, 1.6}. This provides 48 test problems for our experimental setup. In all of our test problems, we have τ = 240. The online supplement provides the data files for all of our test problems. We describe the format of the data files in Appendix C. It is worthwhile to note that the interaction between κ and (δ, σ) creates interesting situations. For example, when we have κ = 8 and (δ, σ) = (4, 0), if the revenue associated with a low fare itinerary is f , then the penalty cost associated with this itinerary is 4f and the revenue associated with the corresponding high fare itinerary is 8f . In this case, if we have a request for the high fare itinerary and a flight leg in this itinerary is already overbooked with a reservation for the low fare itinerary, then we can still accept the high fare itinerary request and deny boarding to the low fare reservation to make a net profit of 8f − 4f . This corresponds to the case where a high fare itinerary trivially preempts the corresponding low fare itinerary. On the other hand, when we have κ = 4 and (δ, σ) = (1, 1), such preemptions do not occur. We also note that the test problems with (δ, σ) = (1, 1) tend to have higher penalty costs than the test problems with (δ, σ) = (8, 0), which, in turn, tend to have higher penalty costs than the test problems with (δ, σ) = (4, 0). We compare the performances of the following seven benchmark strategies. This benchmark strategy corresponds to the DPD policy given by (36). We use M = 100 when computing {α i j : i ∈ L, j ∈ J }. We estimate all 14 expectations through 1,000 Monte Carlo samples. With these settings, the 95% confidence interval for the expectation of α i j has precision ∓4.1% on the average, whereas the 95% confidence interval for the expected penalty cost incurred at the departure time has precision ∓1.8% on the average. This benchmark strategy corresponds to the DLP policy in (12). The basic variant of this strategy simply solves problem (7)- (11) to obtain the optimal values of the dual variables associated with constraints (8) and uses these dual variable to implement the DLP policy. We use a reoptimized variant of this strategy, where we divide the planning horizon into K equal segments and resolve an updated version of problem (7)- (11) for each segment. In particular, given that the state of the reservations at the beginning of the kth segment is x τ (K−k+1)/K , we replace the right hand side of constraints (8) with {c i − j∈J a ij q j x j,τ (K−k+1)/K : i ∈ L}, the right hand side of constraints (9) with { τ (K−k+1)/K t=1 p jt : j ∈ J } and the right hand side of constraints (10) with {q j x j,τ (K−k+1)/K : j ∈ J }, and solve this modified version of problem (7)- (11). Letting {λ * i : i ∈ L} be the optimal values of the dual variables associated with constraints (8), we use these updated values in the decision rule in (12) until we resolve problem (7)- (11) at the beginning of the next segment. We use K = 20 in our computational experiments. Finite differences in the deterministic linear program (FDD) Given that the state of the reservations at the beginning of time period t is x t , FDD approximates the optimal total expected profit over the time periods {t, . . . , 0} by using the optimal objective value of the problem Thus, letting L t (x t ) be the optimal objective value of the problem above, FDD uses L t (x t ) as an approximation to V t (x t ). In this case, we can make the decisions by replacing {V t (·) : t ∈ T } in the decision rule in (6) with {L t (·) : t ∈ T }. This approach is proposed in Bertsimas and Popescu (2003) . Similar to DLP, we use a reoptimized version of FDD, where we divide the planning horizon into K equal segments and retune the decision rule at the beginning of each segment. Given that the state of the reservations at the beginning of the kth segment is Following the decision rule in (6), if we have then we always accept a request for itinerary j until we reach the beginning of the next segment and retune the decision rule. We use K = 20. Virtual capacities based on a naive computation (VCN) In this benchmark strategy, the airline sets virtual capacities on the flight legs by assuming that the no shows take on their expected values. Following this, the airline makes the capacity allocation decisions under the assumption that all of the reservations show up, but the capacities on the flight legs are equal to the virtual capacities. In other words, noting that a reservation shows up at the departure time with probability q, the airline sets the virtual capacity on flight leg i as u i = c i /q and solves a version of the deterministic linear program in (7)- (11), which can be stated as Letting {λ * i : i ∈ L} be the optimal values of the dual variables associated with the first set of constraints above, VCN uses the DLP policy in (12). Similar to DLP and FDD, we use a reoptimized version of VCN with 20 reoptimizations. Virtual capacities based on an economic model (VCE) One criticism for VCN is that it chooses the virtual capacities under the assumption that the no shows take on their expected values. However, depending on the tradeoffs between the fares, penalty costs and show up probabilities, we may want to be more or less aggressive than what the expected values of the no shows suggest. The goal of VCE is to make up for this shortcoming. VCE is proposed in Karaesmen and van Ryzin (2004a) and it is based on the following three assumptions. First, the revenue that we make from one unit of capacity on a flight leg is known. We let r i be the revenue that we make from one unit of capacity on flight leg i. Second, if a reservation uses the capacities on multiple flight legs, then we can allow boarding to this reservation on one flight leg, while denying boarding to the same reservation on another flight leg. Furthermore, the penalty cost of denying boarding to a reservation on a flight leg is known. We let g i be the penalty cost of denying boarding to a reservation on flight leg i. Third, if the airline sets the virtual capacity on flight leg i as u i , then it sells exactly u i reservations on flight leg i. By the third assumption, if we set the virtual capacity on flight leg i as u i , then we sell u i reservations on flight leg i, in which case, the first assumption implies that we generate a revenue of r i u i . On the other hand, if we let B i (u i ) be a binomially distributed random variable with parameters (u i , q), then the number of reservations that show up at the departure time is given by B i (u i ) and the second assumption implies that the expected penalty cost that we incur on flight leg i is g i E{max{B i (u i )−c i , 0}}. Therefore, VCE solves the problem max u i r i u i − g i E{max{B i (u i ) − c i , 0}} to set the virtual capacity on flight leg i. Once the virtual capacities have been set, VCE proceeds in the same way as VCN. Karaesmen and van Ryzin (2004a) suggest several choices for r i and g i . Following their work, we let R j = f j / l∈L a lj and G j = θ j / l∈L a lj for all j ∈ J to evenly distribute the revenue and penalty cost associated with an itinerary over the flight legs that it uses. In this case, we try choosing r i as 16 Using all combinations of these choices, we have nine different choices for r i and g i . We test the performances of all of these nine choices for all of our test problems, but for brevity, only report the results corresponding to the best choice. For different test problems, the best choice for r i and g i can be different. Similar to VCN, we use a reoptimized version of VCE with 20 reoptimizations. Virtual capacities joint with capacity allocation decisions (VCJ) Both VCN and VCE use the assumption that we can set the virtual capacities first, and then, come up with a policy to accept or reject the itinerary requests. In contrast, VCJ uses the penalty cost g i E{max{B i (u i ) − c i , 0}} in problem (37)- (40) to jointly set the virtual capacities and come up with a policy to accept or reject the itinerary requests. In particular, VCJ solves the problem where we use interpolations of the function E{max{B i (u i ) − c i , 0}} to be able to compute it at a fractional u i . Letting {λ * i : i ∈ L} be the optimal values of the dual variables associated with the first set of constraints above, VCJ uses the DLP policy in (12). This approach is proposed in Karaesmen and van Ryzin (2004a) . Similar to VCE, we try three different choices for g i and report the results corresponding to the best choice. We use a reoptimized version of VCJ with 20 reoptimizations. This benchmark strategy is developed by Erdelyi and Topaloglu (2009) . The fundamental observation behind SPC is that if the penalty cost of denying boarding to the reservations were given by a separable function of the form Γ(S(x 0 )) = j∈J γ j (S j (x j0 )), then the optimality equation in (5) would decompose by the itineraries. To exploit this observation, SPC approximates Γ(S(x 0 )) in problem (1)-(4) with a separable function of the form j∈J γ j (S j (x j0 )) and solves the optimality equation in (5) with the approximate boundary condition that V 0 (x 0 ) = −E{ j∈J γ j (S j (x j0 ))}. The value functions {V t (·) : t ∈ T } obtained in this fashion are used to construct a policy to accept or reject the itinerary requests. SPC uses a simulation based method to construct the separable approximation j∈J γ j (S j (x j0 )) to the penalty cost. Roughly speaking, we simulate the DLP policy in (12) to have a general idea about the numbers of reservations that show up at the departure time. Following this, we compute the slopes of Γ(·) at these numbers of reservations along different directions and use these slopes to construct the scalar functions {γ j (·) : j ∈ J }. An exact description of this benchmark strategy is beyond the scope of our paper and we refer the reader to Erdelyi and Topaloglu (2009) for the details. Similar to the other benchmark strategies, we retune the separable approximation five times over the planning horizon. It turns out that retuning SPC more than five times does not provide any additional benefit. 17 Our main computational results are summarized in Tables 1 and 2 . In particular, these two tables respectively show the results for the test problems with four and eight spokes. The first column in Tables 1 and 2 gives the characteristics of the test problem. The second column gives the upper bound on the optimal total expected profit provided by the optimal objective value of problem (7)-(11). The next seven columns give the total expected profits obtained by DPD, DLP, FDD, VCN, VCE, VCJ and SPC. These total expected profits are estimated by simulating the performances of the different policies under 50 itinerary request trajectories. We use common itinerary request trajectories when simulating the performances of the different policies. The tenth column gives the percent gap between the total expected profits obtained by DPD and DLP. This column also includes a " " whenever DPD performs significantly better than DLP and a " " whenever there is no statistically significant performance gap between the two methods at 95% level. The last five columns do the same thing as the tenth column, but they compare the performance of DPD with FDD, VCN, VCE, VCJ and SPC. The results indicate that DPD performs substantially better than all of the benchmark strategies that use a linear programming formulation. Among the linear programming based benchmark strategies, FDD performs the best and it is followed by VCJ, DLP, VCE and VCN. The superiority of FDD over DLP is also observed by Bertsimas and Popescu (2003) . The performance gaps between DPD and DLP, FDD, VCN, VCE and VCJ are statistically significant for all of the test problems. The average performance gaps between DPD and DLP, FDD, VCN, VCE and VCJ are respectively 4.09, 2.85 6.82, 4.76 and 2.82 for the test problems with four spokes. The same gaps increase to 5. 39, 2.87, 8.18, 6.08 and 3.53 for the test problems with eight spokes. Among the three benchmark strategies that use virtual capacities, VCJ performs better than VCN and VCE. It is interesting to note that VCJ performs better than DLP as well. There are test problems where VCN performs better than DLP, despite the fact that VCN is essentially an ad hoc modification of DLP that does not carefully address the possibility of no shows. However, the performance of VCN is not robust as indicated by the test problems with (δ, σ) = (4, 0). There is not a clear distinction between DLP and VCE, but there are test problems where VCE can perform substantially worse than DLP. The performance gap between DPD and SPC is on the order of half a percent to a percent. We emphasize that a percent revenue difference is still considered significant in the revenue management setting. On a majority of the test problems, DPD performs better than SPC and in the remaining test problems, there does not exist a statistically significant gap between the two benchmark strategies. Similar to DPD, SPC performs noticeably better than all of the benchmark strategies that use a linear programming formulation. Therefore, DPD and SPC, by working with the dynamic programming formulation of the capacity allocation and overbooking problem, provide significant improvements over using a deterministic linear programming formulation, which ignores the temporal dynamics of the arrivals of the itinerary requests. It is possible to observe a few trends in the performance gaps. In particular, the performance gaps between DPD and the linear programming based benchmark strategies tend to increase as the fare difference between the high fare and low fare itineraries, penalty costs and overall tightness of the 18 leg capacities increase. For test problems with large fare differences, large penalty costs and tight leg capacities, the "regret" associated with making an "incorrect" decision is relatively large. For example, when the fare difference between the high fare and low fare itineraries is large, accepting a request for a low fare itinerary "incorrectly" may preclude accepting a request for a high fare itinerary later in the planning horizon and the revenue forgone in this case can be quite large. Similarly, when the penalty costs are large, it is costly to deny boarding to a reservation that was accepted "by mistake." When the leg capacities are tight, it is important to make the itinerary acceptance decisions more "carefully," as it is not possible to accommodate all itinerary requests. Thus, it is encouraging that a careful stochastic model pays off and DPD performs significantly better than the linear programming based benchmark strategies as the fare differences, penalty costs and tightness of the leg capacities increase. To display some of these trends, Table 3 shows the performance gaps between DPD and the other benchmark strategies averaged over a number of test problems with a particular characteristic. For example, the second column shows the performance gaps averaged over the test problems with four spokes. The trends that we mention can be observed from this table. Table 4 shows the CPU seconds required to compute one set of value function approximations for DPD and SPC. All of the computational experiments are run on a Pentium IV desktop PC with 2.4 GHz CPU and 1 GB RAM. Since the number of spokes appears to be the primary factor affecting the computation times, we give the average CPU seconds over different test problems. The two rows in Table 4 show the CPU seconds for DPD and SPC. The second and third columns respectively correspond to the test problems with four and eight spokes. The CPU seconds for DPD includes the operations required to estimate {α i j : i ∈ L, j ∈ J } and to compute {v i t (·) : i ∈ L, t ∈ T }. The results indicate that DPD takes significantly less time than SPC and scales more favorably. Considering its performance, DPD appears to be preferable to SPC. DLP, FDD, VCN, VCE and VCJ take at most a few seconds to reoptimize their decision rules. Despite this extra computational burden, the computational requirement for DPD is still reasonable. Given the substantial improvements that it provides over the other benchmark strategies, DPD appears to be a viable choice. In this paper, we developed a network revenue management model to jointly make the capacity allocation and overbooking decisions over an airline network. Our approach is based on decomposing the network revenue management problem into a sequence of single leg revenue management problems and exploiting the observation that if the proportions of the reservations at the departure time were known, then the dynamic programming formulation of the single leg revenue management problems would involve only a scalar state variable. Using these observations, we constructed tractable approximations to the value functions. Computational experiments demonstrated that the resulting policies perform significantly better than the benchmark strategies. 19
REF work with the same dynamic programming formulation and propose a dynamic programming decomposition approach to decompose the network problem into a number of single flight leg problems.
A Dynamic Programming Decomposition Method for Making Overbooking Decisions Over an Airline Network
INFORMS J. Comput.
INFORMS J. Comput.
Computer Science Mathematics