Question1,2

Network Revenue Management: Independent Demands c©

Guillermo Gallego

Spring 12

Abstract

We present a continuous time formulation of the network revenue management model with independent demands. The objective is to maximize expected revenues from an initial set of resources that cannot be replenished during the sales horizon. We present the Hamilton Jacobi Bellman equation that characterizes the optimal value function. We use affine functions in a dynamic programming approximation to obtain an upper bound on the value function and a bid-price heuristic that admits fares with values at least as large as the sum of the bid prices of the resources consumed. We argue that the bid-price heuristic can perform poorly for products with fares that are exactly equal to the sum of the bid-prices, particularly if demand for such products arrive early during the sales horizon. We recommend a refinement of the bid-price heuristic that randomly admits fares that are equal to the sum of bid-prices, which can be shown to be asymptotically optimal. We also discuss refinements that incorporate demand randomness ignored by bid-price heuristics based on the affine approximation.

1 Introduction: Independent Demand Case

Consider a network with several resources that can be combined in different ways to produce different products. In the context of an airline, the resources are the flight legs that are combined to form itineraries or routes from an origin to a destination. In hotel applications, the resources are the room nights and an itinerary may correspond to a single or multiple night stay. An origin-destination fare (ODF) represents an itinerary and a fare. Accordingly, there may be several fares corresponding to an itinerary, with lower fares often being more restricted in terms of the time of purchase, length of stay, or including few ancillary services such as advanced seat selection, luggage handling, mileage accrual and meals.

We will assume that itineraries and fares are given and that demands are independent conditioned on the given fares. More precisely, we will assume that an arriving customer has a particular ODF in mind and will buy that ODF if available and will not make a purchase otherwise. Under this model a customer interested in a non-restricted fare for a given itinerary will not change his mind and purchase a lower priced but more restricted fare. Alternatively,

1

a customer interested in a low fare product will not buy up if the desired fare is unavailable. The independent demand assumption, while restrictive, works well when fares are well differ- entiated and customers can turn to a competitor if they fail to find the fare they want. The independent demand model preforms poorly if fares are not well differentiated or alternative providers are not available. Indeed, when fares differ only in price it makes sense to purchase the one with the lowest price. Moreover, when alternative low fares are not available, some customers may buy up to more expensive but less restricted fares. In such situations we recommend abandoning the independent demand model in favor of a choice model where cus- tomer choices depend on the available fares. The next chapter treats the dependent demand case through the use of choice models.

2 Formulations

Suppose that there are m resources in the network and let c ∈Zm denote the vector of initial capacities. We will assume that resources cannot be replenished during the sales horizon. We will measure time backwards, so t will represent the time-to-go. Initially t = T and at the date of departure t = 0. For any time-to-go t we will let (t,x) represent the state of the system where x represents the vector of remaining inventories. The initial state is (T,c). We will now develop the necessary notation to write a continuous time dynamic program for the maximum expected revenue, say V (t,x), that can be extracted from state (t,x).

We will assume that customers arrive according to a Poisson or compound Poisson process with time varying arrival rates. Expositionally, it helps to introduce the main ideas for the Poisson case and later take care of the changes needed to deal with the compound Poisson case. We will let λtkj denote the arrival rate at time t of ODF kj for customers interested in fare pkj,j ∈{1, . . . ,nk} of itinerary k.

Let Ak be the vector of resources utilized by itinerary k. Then Ak is an m-dimensional vector of zeros and ones with a one for each resource consumed by itinerary k. Consider now a time increment δt that is small enough so that we we can think of λtkjδt as the probability that an arrival occurs at time t for ODF kj. Then,

V (t,x) = K∑ k=1

nk∑ j=1

λtkjδt max{V (t−δt,x),pkj+V (t−δt,x−Ak)}+(1− K∑ k=1

nk∑ j=1

λtkjδt)V (t−δt,x)+o(δt)

where o(δt) is a quantity that goes to zero faster than δt. Rearranging terms and taking limits we obtain the partial differential equation

∂V (t,x)

∂t =

K∑ k=1

nk∑ j=1

λtkj[pkj − ∆kV (t,x)]+ (1)

with boundary conditions V (t, 0) = V (0,x) = 0 for all x ≥ 0. Here ∆kV (t,x) = V (t,x) − V (t,x − Ak) if x ≥ Ak and ∆kV (t,k) = ∞ otherwise. This continuous time formulation

2

indicates that the marginal value of time is equal to the net revenue in excess of the marginal value of capacity.

It is clearly optimal to accept ODF kj if pkj ≥ ∆kV (t,x). This gives rise to a nested by fare structure. Indeed, if fares are ordered so that pk1 ≥ pk2 ≥ . . . ≥ pknk . Then, if fare pkj is accepted then so are all fares pki with i ≤ j and if fare j is reqjected then so are all fares with i > j.

It is conceptually useful to think of λtk = ∑nk j=1 λtkj as the arrival rate of requests for

itinerary k and the requests for specific fares λtkj = λtkqtkj as thinned Poisson processes. This is equivalent to having random fare Ptk at time t for itinerary k where Ptk takes value pkj with probability qtkj. Writing (1) in terms of random fares yields the equivalent formulation

∂V (t,x)

∂t =

K∑ k=1

λtkE[Ptk − ∆kV (t,x)]+. (2)

Formulation (2) makes explicit the arrival rate for each itinerary and the fact that distribution of fares for an itinerary may change over time to reflect time preferences or fare restrictions. Formulation (2) is actually more general than the motivation that led to it as it is valid for any random fares Ptk with finite means. Viewing Ptk as a general random variable, not necessarily restricted to the set of offered fares {pk1, . . . ,pknk}, may be helpful to deal with net fares that may be different depending on the distribution channel costs. However, most of these benefits can be captured by a enlarging, if necessary, the set of fares {pk1,pk2, . . . ,pknk} to allow to deal with commission netting and channel effects.

While formulation (2) is rich in detail, it is sometimes convenient to work with a more streamlined formulation that aggregates ODFs into a single index n =

∑K k=1 nk. Abusing

notation slightly, the single index formulation results in

∂V (t,x)

∂t =

n∑ j=1

λtj(pj − ∆jV (t,x))+ (3)

where in this formulation λtj and pj denote respectively the arrival rate and the fare of ODF j. Notice that in this formulation there may be multiple identical columns corresponding to different fare classes for the same itinerary. This formulation has the virtue of simplicity and generality at the cost of abstractness as it distances the model a bit from one of its potential origins. It simplicity allows us to more easily treat the compound Poisson case, to discuss the nested by fare structure of optimal solutions and randomness in the arrival rates. After we discuss these extensions we will go back to formulation (1), that at the cost of additional notation, keeps the distinction among the fares for different itineraries.

2.1 Compound Poisson Process

The network DP is written under the implicit assumption that arriving requests for ODF j are for a single unit. If demand for an ODF j is a compound Poisson process with arrival rate λtj and demand size Zj with q

k j = P(Zj = k), then we can model this by using columns of

3

the form Akj = kAj with corresponding fare p k j and arrival rate λ

k tj = λtjq

k j for all k such that

qkj > 0. Notice that the total fare p k j for a size k request for ODF j need not be equal to kpj,

thus allowing for economies or diseconomies of scale in group pricing. Under this formulation, a size k request for ODF j is accepted if and only if pkj ≥ ∆kjV (t,x) = V (t,x)−V (t,x−Akj ) = V (t,x) − V (t − kAj). This allow us to treat ODF of each size as a different request in the single index model.

2.2 Doubly Stochastic Poisson Process

If the arrival rates themselves are random for each t, say λitj with probability θ i j, then the HJB

(3) is of the same form with λtj = ∑ i λ

i tjθ

i.

3 LP Based Upper Bound on V (T,c)

We now return to formulation (1) with the goal of obtaining an upper bound on the optimal expected revenue V (T,c). We will use the perfect foresight idea introduced in Chapter 1 to obtain an upper bound on revenue for the single resource problem. Let Dkj be the aggregate demand for ODF kj over the horizon [0,T]. Then Dkj is Poisson with parameter Λkj =∫T 0 λskids. Consider the linear program

V̄ (T,c) = max K∑ k=1

nk∑ j=1

pkjykj (4)

s.t. K∑ k=1

Ak

nk∑ j=1

ykj ≤ c

0 ≤ ykj ≤ Λkj ∀ k,j.

This Linear Program is know as the deterministic network LP (DNLP) and also as the fluid limit LP. We will now show that this linear program is an upper bound on the value function V (T,c).

Theorem 1 V (T,c) ≤ V̄ (T,c).

Proof: Consider the revenue from the optimal dynamic policy, that accepts a request for ODF kj at state (t,x) if pkj ≥ ∆kV (t,x), for a specific realization of demands Dkj,j = 1, . . . ,nk,k = 1, . . . ,K. This revenue is at most equal to the revenue from the perfect foresight model that decides how many units from each ODF to accept after seeing the realization of demand.

V (T,c|D) = max K∑ k=1

nk∑ j=1

pkjykj

4

s.t. K∑ k=1

Ak

nk∑ j=1

ykj ≤ c

0 ≤ ykj ≤ Dkj ∀ k,j.

It follows that V (T,c) ≤ EV (T,c|D). Since V (T,c|D) is concave in D, Jensen’s inequality implies that V (T,c) ≤ EV (T,c|D) ≤ V (T,c|Λ) = V̄ (T,c) where Λ = E[D] is the vector of expected demands.

The DLP is more typically encountered in the single index incarnation in matrix notation:

V̄ (T,c) = max p′y (5)

subject to Ay ≤ c

0 ≤ y ≤ Λ,

where y = (y1, . . . ,yn) and Λ = (Λ1, . . . , Λn).

Both the primal and the dual are feasible and bounded so they have an optimal solu- tion. By strong duality they both result in the same value for the objective function and all complementary slackness conditions apply. The dual problem to (4) is given by

V̄ (T,c) = min z′c + u′Λ (6)

s.t. z′Aj + uj ≥ pj ∀j

z,uj ≥ 0 ∀ j.

At optimality, the dual variable zi is the marginal value of capacity of resource i, while the dual variables uj is the marginal value of demand for ODF j. By complementary slackness, zi > 0 implies that the capacity constraint for resource i is tight, and uj > 0 implies that all the demand of ODF j is used.

Example 1 Consider a network with two connecting flights and assume that two fares are available for each individual flight as well as for the connecting flight. Using the single index model we have 6 ODFs with incident matrix

A = (

1 1 0 0 1 1 0 0 1 1 1 1

) .

The fare vector and arrival rates are as follows:

p = ( 150, 100, 120, 80, 250, 170 )

5

λt = ( 0.06, 0.00, 0.04, 0.00, 0.06, 0.00 ) 1 ≤ t ≤ 500 λt = ( 0.00, 0.12, 0.00, 0.16, 0.00, 0.08 ) 501 ≤ t ≤ 1000

with capacity vector c = (90, 90). Notice that the arrival rates are such that low fare demands arrive before high fare demands. The vector of ΛTj =

∫T 0 λtjdt is given by

ΛT = ( 30, 60, 20, 80, 30, 40 ) .

The solution to (5) is given by

ȳ = ( 30, 30, 20, 40, 30, 0 )

and the solution to the primal problem (6) is given by z̄ = (100, 80). The optimal value function is $20,600.

Heuristics for the stochastic system can be constructed both in terms of the solutions to the primal or the dual problem. In the next section we emphasize heuristics based on the primal problem. Heuristics based on the DLP require n values instead of m << n required by the dual. However, heuristics based on the DLP have the potential of performing well if implemented correctly, particularly if DLP is resolved at reading dates T = tN > .. . > t1 > 0. This is particularly true when new forecasts are available at reading dates. Resolving the DLP has good asymptotic properties, see Maglaras and Meisnner [6] in the context of a single resource. However, resolving may hurt rather than help performances in some instances, see Cooper [2] for details, particularly towards the end of the horizon when the fluid approximation implied by the DLP suffers the most from ignoring randomness.

4 Bid-Price and PAC Heuristics

Any vector z ∈ <m+ can be used to describe a bid-price heuristic admission control policy for the stochastic network revenue management problem. The heuristic works as follows: accept request for fare pj in state (t,x) if only if pj ≥ z′Aj and Aj ≤ x for all t > 1 (a request for product j at t = 1 is accepted as long as Aj ≤ x). In words, accept a request if its fare is equals or exceeds the sum of bid prices for the resources consumed and there is available capacity. A bid-price vector that is commonly used is the solution to linear program (6), although other bid-prices are often used as explained later. A bid-price heuristic has the advantage of using only m numbers, one for each resource.

Let F = {j : pj ≥ z′Aj} and R = {j : pj < z′Aj}. Then all ODFs belong to either the set F or the set R. The bid price heuristic accepts requests for ODFs in F, provided there is enough capacity, and rejects all requests for ODFs in R. The solution to the linear program (6) almost always has a non-empty set P = {j : pj = z′Aj}⊂F consists of ODFs whose fares are equal to the sum of the bid-prices. Let F = {j : pj > z̄′Aj}. Then the set of ODFs can be partitioned into the three sets F,P and R with F = F ∪P .

Let y be the solution to the DLP (5). Consider now a probabilistic admission control (PAC)

6

heuristic, that admits a request for ODF j with probability ỹj = yj/ΛTj. By complementary slackness, R = {j : yj = 0}, P = {j : 0 < yj < ΛTj} and F = {j : yj = ΛTj}. This implies that the acceptance probabilities are ỹj = 0 for j ∈ R, ỹj ∈ (0, 1) for j ∈ P and ỹj = 1 for j ∈ F. Notice that the data requirements for the PAC is the solution to the DLP with involves n >> m numbers. If P = ∅, then the PAC and bid-price heuristics coincide. However, if P 6= ∅, then the PAC heuristic has a more refined method of dealing with ODFs in P . This is good news when the solution to the DLP has many ODFs in P , particularly when request for ODFs in P arrive before ODFs in F as is common in practice. The following example illustrates this situation.

Example 2 Consider Example 1 and notice that the six ODFs are partitioned as follows: F = {1, 3, 5}, P = {2, 4} and R = {6}. Notice also that fares in P arrive before fares in F . The performance of the bid-price heuristic was estimated through simulation resulting in approximate expected revenues of $17,732, estimated by averaging the revenues of 100,000 simulated instances. The PAC heuristic, has ỹj = 0.5 for j ∈ P , so the PAC, admits ODFs in P with probability 50%. This improves the expected revenues, estimated by simulation, from $17,732 to $19,386.

Under the assumption that the random fares Ptk in formulation (2) are continuous random variables that are uniformly bounded, Talluri and van Ryzin [8] show that the bid-price heuristic based on the solution of program (6) is asymptotically optimal. The asymptotic result is for a sequence of problem instances where the demand rates and capacity are scaled up by a factor b > 1. More precisely, if V b(T,c) is the optimal expected revenue for a system with arrival rates bλtk and capacity bc, and V

b z̄ (T,c) is the expected revenue based on the

solution z̄ to (6), Talluri and van Ryzin [8] show that

V bz̄ (T,c)

V b(T,c) → 1 as b →∞.

The assumption that Ptk is continuous guarantees that set of partially accepted fares P is empty. However, this is rarely the case in practice. The asymptotic optimality of the bid- prices heuristic is unfortunately destroyed if the continuity assumption of the random fares Ptk is relaxed. It is easy to see what goes wrong by thinking of a single resource problem with two fares p1 > p2, with aggregate demands Λ1 = (1 − �)c and Λ2 such that Λ1 + Λ2 > c. Then z = p2 and the bid-price heuristic accepts all requests until capacity is exhausted. If arrivals are low-to-high and Λ2 >> c then the entire capacity will be consumed by low-fare customers. One may try to correct things by using a bid-price heuristic that accepts only fares in set F = {1} but then things go wrong if Λ1 = �c as most of the capacity would get spoiled. Notice that neither version of the heuristic (accepting F ∪P or just F) improves as demand and capacity are scaled by b > 1. As a result, bid-price heuristics are not, in general, asymptotically optimal. In practice, P 6= ∅ and demand for the marginal fares in P tend to arrive before demand for fares in F . Thus, the bid-price heuristic risks being too generous in accepting requests for fares in P at the cost of cannibalizing capacity that would be better used by fares in F.

Our next result states that the asymptotic optimality is preserved by the PAC even if the

7

set P 6= ∅. The proof can be found in the Appendix. An independent proof of a similar result can be found in Reiman and Wang [12].

Theorem 2 The PAC heuristic is asymptotically optimal as capacity and demand rates are scaled up.

4.1 Refinements of Bid-Price and PAC Heuristics

In practice, bid price heuristics perform better if the DLP is resolved frequently during the horizon, e.g., at reading dates when forecasts may also be updated. This helps because cor- rections can be made before too much of the demand is cannibalized by fares in P . Resolving the DLP has good asymptotic properties, see Maglaras and Meissner [6], in the context of a single resource. However, resolving may hurt rather than help performances in some in- stances, see Cooper [2] for details, particularly towards the end of the horizon when the fluid approximation implied by the DLP suffers the most from ignoring randomness. Nevertheless, over the entire horizon, it seems that the benefits from resolving can be substantial and result in a bounded optimality gap as shown by Jasin and Kumar [7].

Heuristics can also benefit from refinements that make them more sensitive to demand randomness. Talluri and van Ryzin [9] suggest solving the DLP problem many times with simulated, rather than average, demands and then averaging the bid prices of the generated solutions. This idea tries to estimate the gradient of EV (T,c|D) instead of the gradient of V̄ (T,c) = V (T,c|E[D]). Likewise, one can obtain average admission probabilities for the PAC heuristic. Topaloglu [10] shows that randomizing the DLP preserves the asymptotic optimality properties in Taluri and van Rizin [8].

Another refinement proposed in the literature is to solve a version of the DLP (5) that yields time-dependent admission probabilities and time dependent bid-prices. This idea emerged from the use of approximate dynamic programming with affine functions for the discrete time version of (3) as proposed by Adelman [1] and later refined by Tong and Topaloglu [11]. Recall that the discrete time approximation of (3) yields a good approximation as long as time is rescaled so that

∑n j=1 λtj << 1 for every t = 1, . . . ,T . With this rescaling, we limit our

presentation of this body of work to a linear program that is a natural extension of (4), where for each time-to-go t = 1, . . . ,T , the variables ytj, represent the expected sales of product j at time t. Starting with inventory xT = c, the inventory evolves according to the equation xt−1 = xt − Ayt. To ensure feasibility, we require xt ≥ 0 and yt ≤ λt for all t = 1, . . . ,T . Tong and Topaloglu [11] show that there are m×n additional constraints for each t that come from the ADP formulation, and can be written succinctly as A diag(yt) ≤ xtλ′t. Constraint ij corresponds to resource i and product j. It states that Aijyjt ≤ xitλjt. For the airline case Aij is either zero or one. If Aij = 0 then the constraint is vacuous. On the other hand, if Aij = 1 then the constraint implies that yjt ≤ λjtxit. This constraint is only more binding than yjt ≤ λjt, coupled with xt−1 ≥ 0, when there are resources that are consumed by product j with 0 < xti ≤ 1, which happens only towards the end of the horizon when t is small.

8

This leads to the DLP-t formulation (where the t stands for time-varying controls):

Ṽ (T,c) = max T∑ t=1

p′yt (7)

subject to xT = c

xt −xt−1 −Ayt = 0 ∀ t = 1, . . . ,T yt ≤ λt ∀ t = 1, . . . ,T A diag(yt) ≤ xtλ′t ∀ t = 1, . . . ,T yt ≥ 0,xt ≥ 0 ∀ t = 1, . . . ,T

Formulation (7) is due to Tong and Topaloglu [11], and it is actually a tighter upper bound than the NDLP. To see this, notice that if yt, t = 1, . . . ,T is an optimal solution to (7), then y =

∑T t=1 λtyt is a feasible solution to (4), with the same objective value. This

shows that Ṽ (T,c) ≤ V̄ (T,c). Moreover, V (T,c) ≤ Ṽ (T,c), since Ṽ (T,c) is obtained through approximate dynamic programming, as shown by Tong and Topaloglu [11]. The problem in Example 1 was solved using the above procedure resulting in Ṽ (T,c) = $20, 510.

Vossen and Zhang [14] proposes a clever disaggregation idea to speed up the solution of (7). The key is to aggregate the constraints beyond period s. Let yt be, as before, the expected sales over periods t = 1, . . . ,s, and let y be the aggregate sale over periods s+ 1, . . . ,T . Notice that the demand over those periods is equal to λ = ΛT − Λs. Let

Ṽs(T,c) = max s∑ t=1

p′yt + p ′y (8)

subject to x = c

x−xs −Ay = 0 xt −xt−1 −Ayt = 0 ∀ t = 1, . . . ,s y ≤ λ yt ≤ λt ∀ t = 1, . . . ,s A diag(yt) ≤ xtλ′t ∀ t = 1, . . . ,s yt ≥ 0,xt ≥ 0,y ≥ 0 ∀ t = 1, . . . ,T

Clearly the case s = T reduces to the DLP-t as 0 ≤ y ≤ λ = 0 implies that xT = c. Since Ṽs(T,c) is a relaxation of Ṽ (T,c), it follows that Ṽs(T,c) ≥ Ṽ (T,c). Let y together with yt, 1 ≤ t ≤ s be an optimal solution to Ṽs(T,c). We now expand the solution over the full horizon by setting yit = 0 for all s < t ≤ T if λi = 0 and yit = yiλit/λi otherwise. Since the objective value of Ṽ (T,c) coincides with Ṽs(T,c), we know that the solution is optimal as long as it is feasible. Thus the idea is to solve Ṽs(T,c) for small values of s and test for feasibility for the expanded solution. If the solution is feasible, the procedure stops and otherwise the problem is solved again with s ← s + 1. The problem in Example 1 was solved using the above procedure yielding an optimal solution at s = 10, so Ṽ10(T,c) = Ṽ (T,c) = $20, 510. Formulation (8) can be made even more compact by replacing the first three constraints with

9

A( ∑s t=1 yt + y) ≤ c, and writing the sixth constraint as A diag(yt) ≤ (c−A(

∑s u=t+1 yu + y))λ

′ t,

as suggested by Vossen and Zhang [14].

The solution to (7) divides the set of itineraries into three subsets Ft = {j : yjt = λjt}, Pt = {j : 0 < yjt < λjt} and Rt = {j : yjt = 0}, and this can be viewed as a time dependent version of the PAC heuristic, where a request for itinerary j at time t is accepted with probability ỹjt = yjt/λjt if λjt > 0 and with probability zero otherwise. The dual, zt, of the capacity constraint xt − xt−1 − Ayt = 0, produces a time dependent bid-price vector. Under this heuristic, itinerary j is accepted at state (t,x) if pj ≥ z′t−1Aj and x ≥ Aj.

Example 3 Table 4.1 provides simulation estimates of the expected revenues of the refine- ments suggested in this Section. In particular, we resolve both the DLP and the DLP-t, 1, 4 and 10 times (evenly spaced during the horizon) for the data of Example 1. We also provide estimates of the randomized DLP suggested in [9] under the heading DLP-r. The simulation estimates are based on 100,000 repetitions of the heuristic. The bid-price heuristic improves as we move to more frequent resolves, actually overtaking the performance of the PAC heuristic. This is not unusual as the bid-price heuristic tends to gradually tighten capacity for fares in P . The DLP-t did not provide a significant increase in profits except for the PAC heuristic with ten resolves. The randomized versions of the bid-price heuristic did well for 1 and 4 resolves, but poorly for ten resolves. This observation is consistent with other reports; see de Boer et al. [3] and Williamson [13].

Control 1 4 10 Bid-Price DLP $17,732 $18,519 $19,582 PAC DLP $19,386 $19,438 $19,554 Bid-Price DLP-r $17,736 $19,372 $19,448 PAC DLP-r $18,867 $19,257 $19,429 Bid-Price DLP-t $17,733 $18,325 $19,583 PAC DLP-t $19,337 $19,457 $ 19,569

Table 1: Performance of Bid-Price and PAC heuristics for NDLP and NDLPt

In Example 3 the DLP-t refinement was only marginally better than the DLP. However, extensive computational experiments in Tong and Topaloglu [11] show that the DLP-t can be beneficial compared to DLP, especially if the DLP is not resolved frequently.

5 Heuristics that Take Randomness into Account

In addition to bid-price heuristics, researchers and practitioners have also devised heuris- tics that incorporate randomness. Here we described two such heuristics. If the number of itineraries is not overwhelmingly large, one can try to use the EMSR-b heuristic or a similar heuristic for each itinerary to find protection levels for higher fares relative to lower fares. If the number of itineraries is large, an alternative is to aggregate ODFs into buckets for each resource and to use EMSR-b or a similar heuristic for each resource. We will now explain these two heuristics in detail.

10

5.1 Managing Itineraries

If the number of itineraries K is not too large, or at least the number of itineraries with significant demand is not large, then we can try to improve performance by using a combination of capacity allocation and single-resource heuristics. More specifically, let ȳk =

∑nk j=1 ȳkj be

the total capacity that the DLP allocates to itinerary k and consider the problem of allocating that capacity among fares, pk1 > pk2 > .. . > pknk with Poisson demands ΛTk1, ΛTk2, . . . , ΛTknk assuming low-to-high arrivals. The output will be protection levels and nested booking limits for the different fares. The heuristic allows bookings of itinerary k at fare pkj at state (t,x) if x ≥ Ak and it is within the nested booking limits. If the fare is accepted the sale is recorded and counted against the nested booking limits.

Example 4 For Example 2, we have three itineraries. Itinerary 1 consumes one unit of resource 1 and is allocated 60 units of capacity for fares p11 = 150 and p12 = 100. The expected demands for these two fares over the entire horizon are 30 and 60 respectively. An EMSR-b analysis shows that we should protect 28 units of capacity for fare p11, resulting in nested booking limits 60 and 32 = 60-28, respectively, for fares p11 and p12. Itinerary 2 consumes one unit of resource 2 and is allocated 60 units of capacity for fares p21 = 120 and p22 = 80. The expected demand for these two fares over the entire horizon are 20 and 80 respectively. An EMSR-b analysis shows that we should protect 18 units of capacity for fare p21, resulting in nested booking limits 60 and 42 = 60-18, respectively, for fare p21 and p22. Finally, itinerary 3 consumes one unit of each resource and is allocated 30 units of capacity for fares p31 = 250 and p32 = 170. The expected demands for these fares are 30 and 40. An EMSR-b analysis shows that we should protect 27 units for fare p31 resulting in nested booking limits 30 and 3= 30-27, respectively, for fares p31 and p32. The expected revenue was estimated, through simulation, to be $19,658 or 1.4% better than the PAC heuristic applied once at the beginning of the horizon.

5.2 Managing Resources

We will use the single index convention to describe the main ideas. Let Ij = {i : Aij > 0} be the set of resources utilized by ODF j. The net contribution of ODF j to resource i is defined by subtracting the value of the capacity used by ODF j on all other resources consumed by ODF j. For any vector of bid prices z ≥ 0, let pij(z) = pj −

∑ l 6=i Aljzl if

i ∈ Ij and pij(z) = 0 otherwise. For each resource i = 1, . . . ,m we can now solve a single resource revenue management problem with fares pij(z) and arrival rates λij = λj for all j ∈ Ji = {j : Aij > 0}. Notice that we no longer assume that the fares will arrive low-to-high, but a robust heuristic is to compute protection levels as if the arrivals are low-to-high and then use standard, rather than theft nesting. The low-to-high protection levels can be computed using dynamic programming or a heuristic such as EMSR-b. When a request for ODF j arrives at state (t,x), the request is accepted if the net fare is accepted for each resource i ∈ Ij. The problem with a direct implementation of this approach is that there may be too many different itineraries mapped to resources. Some of these itineraries will have very similar net contributions and some will have very small demands. A natural idea is to aggregate the

11

itineraries into buckets of similar net contributions and aggregate the demands within each bucket. The exercise results in a more manageable single resource allocation problem. The idea of aggregating ODFs into buckets was developed by the Operations Research group at American Airlines and is known as Displacement Adjusted Virtual Nesting (DAVN). This method, used in conjunction with z = z̄ combines ideas of bid-prices, to compute net fare contributions, and ideas of single leg controls. Not surprisingly, the method performs quite well.

Example 5 Consider the data of Example 2. Suppose that three buckets are defined such that bucket 1 contains all net fares greater than $120, bucket 2 all fares between $60 and $120 and bucket 3 all fares below $60. The itineraries that utilize resource 1, under the single index model, are 1,2,5 and 6 and the net fares for resource 1 are: p11(z̄) = 150,p12(z̄) = 100,p15(z̄) = 170 = 250 − 80,p16(z̄) = 170 − 80 = 90. Accordingly fare 1 and 5 belongs to bucket 1, with corresponding expected demands 30 and 30. Fares 2 and 6 belong to bucket 2 with corresponding expected demands 60 and 40. We can aggregate fares 1 and 5 of bucket 1 into a single weighted average fare of 160 with aggregate demand 60. Similarly, for bucket 2 we can aggregate fares 2 and 6 into a single weighted average fare of 96 with aggregate demand 100. An EMSR-b calculation reveals that it is optimal to protect 58 units of capacity to bucket 1 and thereby authorize up to 32 units of capacity to book under bucket 2.

We can repeat the procedure for resource 2 and obtain net fares p23(z̄) = 120, p24(z̄) = 80, p25(z̄) = 250 − 100 = 150 and p26(z̄) = 170 − 100 = 70, with corresponding demands 20, 80, 30 and 40. Clearly fares 3 and 5 map into bucket 1 while fares 4 and 6 map into bucket 2. We can aggregate fares 3 and 5 of bucket 1 into a single weighted average fare of 138 with aggregate demand 50. Similarly , for bucket 2 we can aggregate fares 4 and 6 into a single weighted average fare of 76.67 with aggregate demand 120. An EMSR-b calculation reveals that it is optimal to protect 48 units of capacity to bucket 1 and thereby authorize up to 42 units of capacity to book under bucket 2. The expected revenues, estimated via simulation, are $19,785 or 2.0% higher than the PAC heuristic applied once at the beginning of the horizon.

6 Appendix

Proof of Theorems 1 and 2. Proof: We start by analyzing the performance of the bid price heuristic z̄, we will now construct upper and lower bounds on Vz̄(T,c). Notice that

Γz(T,c) = Rz(T) + z ′(c−Dz(T)) (9)

where

Rz(T) = K∑ k=1

nk∑ j=1

ΛTkjpkjδ(pkj −z′Ak)

is the expected revenue from an uncapacitated system that admits requests for ODFs kj with pkj ≥ z′Ak,

Dz(T) = K∑ k=1

Ak

nk∑ j=1

ΛTkjδ(pkj −z′Ak)

12

is the expected demand for the resources under the same admission control rule, and δ(·) is the heavyside function that is one if and only if the argument is non-negative. We will now argue that the second term of Γz̄(T,c) in equation (9) is non-positive. Clearly the terms with z̄i = 0 do not contribute, so it is enough to show that ci ≤ Dz̄(T)i when z̄i > 0, but this follows because by complementary slackness ci =

∑K k=1 Aik

∑nk j=1 ȳkj for such i and

ȳkj ≤ ΛTkjδ(pk−z̄′Ak), again by complementary slackness. The important conclusion to draw from this analysis is that V (T,c) ≤ V̄ (T,c) ≤ Rz̄(T).

To construct a lower bound on Vz(T,c) it helps to imagine that management is willing to charge itself an overbooking cost, say θi for each unit of resource i that is overbooked. If we use an arbitrary bid price vector z ≥ 0 as an admission control rule without filtering requests for lack of capacity the expected revenue, net of overbooking costs, is given by

Γz,θ(c,T) = Rz(T) −θ′E(Nz(T) − c)+

where Nz(T) is a Poisson vector with intensity Dz(T). Let θ̄ be a vector with components

θ̄i = max{pkj : Aki > 0} i = 1, . . . ,m.

Clearly θ̄i is the maximum revenue that can accrue from the sale of any ODF that consumes resource i, but this amount will be charged for each unit of i that is consumed in excess of capacity ci resulting in the series of inequalities

Rz̄(T) − θ̄′E(Nz̄(T) − c)+ ≤ Vz̄(T,c) ≤ V (T,c) ≤ V̄ (T,c) ≤ Rz̄(T), (10)

that directly imply V bz̄ (T,c)

V b(T,c) ≥ 1 −

θ̄′E(Nbz̄ (T) − c)+

Rbz̄(T) (11)

where the superscript b represents a system with demands bλtk and capacity bc scaled up by a factor b > 1.

Under the assumption that the Ptks in formulation (2) are continuous random variables that are uniformly bounded, Talluri and van Ryzin [8] use similar arguments and a bound on partial expectations to show that the right hand side of (11) is of the form 1−O(1/

√ b). Taking

the limit as b → ∞ shows that the ratio of V bz̄ (T,c) to V b(T,c) goes to one. The conclusion drawn is that under the stated conditions bid-price heuristics are asymptotically optimal. The

bound on partial expectations, see Gallego [4], is E(Z−z)+ ≤ 0.5( √ σ2 + (z −µ)2−(z−µ)) and

holds for all random variables Z with mean µ and variance σ2. The continuity assumption was used by Talluri and van Ryzin to show, via the Karush-Kuhn Tucker conditions, that Dz̄(T) ≤ c. As we have seen, the opposite inequality holds for critical resources (z̄i > 0) when the distribution of Ptks are discrete. Under the PAC heuristic, expected admitted demands DPAC(T) =

∑K k=1 Ak

∑nk j=1 ȳkj ≤ c and consequently on RPAC(T) = V̄ (T,c). Using the bound

on partial expectations we see that

E(NbPAC(T) − c) + i ≤ 0.5

√ b √ DPAC(T)i

for each i. The result then follows from ERbPAC(T) = bERPAC(T).

13

References

[1] Adelman, D. (2007), Dynamic bid-prices in revenue management, Operations Research 55(4), 647661.

[2] Cooper, W. (2002). Asymptotic behavior of an allocation policy for revenue management. Oper. Res. 50, 720-727.

[3] de Boer, S. V., R. Freling, N. Piersma (2002). “Mathematical programming for network revenue management revisited,” Eur. J. Oper. Res, 137, 72-92.

[4] Gallego, G. (1992). A min-max distribution free procedure for the (Q,r) inventory model. Oper. Res. Letters, 11, 55-60.

[5] Kunnumkal, S. and H. Topaloglu (2010). Computing Time-Dependent Bid Prices in Net- work Revenue Management Problems. Transportation Science, 44, 38-62.

[6] Maglaras, C. and Meissner J. (2006). Dynamic Pricing Strategies fro Multiproduct Revenue Management Problems. MSOM, 8, 2, 136-148.

Columbia University.

[7] Jasin, S. and S. Kumar (2010) A Re-solving Heuristic with Bounded Revenue Loss for Network Revenue Management with Customer Choice. Working paper, Stanford University.

[8] Talluri, K, and G. van Ryzin (1998). An Analysis of Bid-Price Controls for Network Revenue Management. Management Science, 44, 11, 1577-1593.

[9] Talluri, K and G. van Ryzin (1999) “A Randomized Linear Programming Method for Computing Network Bid Prices.” Transportation Science, 33, 207-216.

[10] Topaloglu, H. (2007) “On the asymptotic optimality of the randomized linear program for network revenue management.” Technical report, School of IEOR, Cornell University, Ithaca, NY, 2007

[11] Tong, C. and Topaloglu, H. (2011) “On Approximate Linear Programming Approaches for Network Revenue Management Problems.” Working paper, Columbia University.

[12] Reiman, M. and Wang, Q. (2007) “An Asymptotically Optimal Policy for a Quantity- Based Network Revenue Management Problem.” Working paper, Alcatel-Lucent Bell Labs.

[13] Williamson, E. L. (1992) “Airline network seat inventory control: Methodologies and revenue impacts,” Ph.D. thesis, Flight Transportation Laboratory, Massachusetts Institute of Technology, Cambridge, MA.

[14] Vossen, T., and Zhang, D. 2012. “A Dynamic Disaggregation Approach to Approximate Linear Programs for Network Revenue Management.” Working paper, Leads School of Busi- ness, University of Colorado at Boulder.

[15] Zhang, D. and D. Adelman (2009). An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice. Transportation Science, 381-394.

14