The principle of optimality

The principle of optimality lies at the heart of dynamic programming. It basically says that if a policy is optimal for the original problem above then it must be optimal fo any subproblem of this same original problem.

We define the reward-to-go for policy \(\mu\) at time \(t\) by

\[V_t^{\mu}(x)=\mathbb E[g_{T+1}(x(T+1)+\overset{T}{\underset{s=t}{\Sigma}}g_s(x(s),\mu(s),w(s))| x(t)=x].\]

\(\mathbf{Therem}\): If policy \(\mu^*=\{\mu_1^*,\mu_2^*,...,\mu_T^*\}\) is an optimal policy for the dynamic program define above, then truncated policy \(\{\mu_t^*,\mu_{t+1}^*,...,\mu_T^*\}\) is optimal for the t-subproblem. That is,

\[V_t^{\mu^*}(x)=\underset{\mu\in \mathbb M}{Sup} \quad V_t^{\mu}(x)\quad \forall x\in S_t.\]

The dynamic programming recursion

The principle of optimality leads to a recursion procedure for finding optimal plicy. We define optimal reward-to-go as follows, which is also called value function. \[V_t(x)=\underset{\mu\in \mathbb M}{Sup} \quad V_t^{\mu}\]

\(\mathbf{Proposition}\): The value function \(V_t(x)\) is the unique solution to the recursion below

\[V_t(x)=\mathbb E[g_{T+1}(x(T+1)+\overset{T}{\underset{s=t}{\Sigma}}g_s(x(s),\mu(s),w(s))| x(t)=x],\] for all \(t\) and all \(x\in S_t\) with boundary condition \(V_{T+1}(x)=g_{T+1}(x), \forall x\in S_{T+1}.\) Moreover, if \(\mu^*=\mu_t^*(x)\) achieves the maximum in above, then \(\mu=\{\mu_1^*,\mu_2^*,...,\mu_T^*\}\) is an optimal policy.

Systems with observable disturbances

Consider the case in which we determine actions based upon perfect knowledge of the disturbance \(w(t)\) in each time \(t\). In other words, we allow the decision to be a function of both system state \(x(t)\) and random disturbance \(w(t)\). The idea is that in this situation we can observe the disturbance before making our decision.

In this case, the basic dynamic programming recursion becomes \[V_t(x)=\underset{\mu(x,w(t))\in \mathbf U_t(x)}{max} \quad E[g_t(x,\mu(t,w(t)),w(t))+V_{t+1}(f_t(x,\mu(x,u(x,w(t)),w(t)))].\]

Since we can choose a control decision based upon knowing \(w(t)\), the recursion can be rewritten as \[V_t(x)=E[\underset{\mu\in \mathbf U_t(x)}{max} \quad g_t(x,\mu,w(t))+V_{t+1}(f_t(x,\mu,w(t))].\]

The recursion above has switched \(E[max\{\}]\) with \(max \{E[]\}\) because optimal decision \(\mu_t(x)\) in time \(t\) can be chosen based upon each realized random term \(w(t)\). By using this transformation we have reduced the state space from \(S_t\times W_t\) in original DP problem to \(S_t\) in the reduced-form DP.

Application of dynamic program in revenue management

Here is a typical example of how this transformation applies in RM. Suppose \(x(t)\) is a scalar capacity, \(y(t)\) is the revenue of the request in period \(t\), and \(\mu(t)=1\) if we decide to accept a request and \(0\) otherwise. The reward function is simply \(y(t)u(t)\). Capacity as a system state evolves according to \(x(t+1)=x(t)-u(t),\) and revenue is derived by a random process \(y(t+1)=w(t+1)\).

A dynamic program can be formulated traditionally as \[V_t(x,y)=\underset{\mu\in \{0,1\}}{max} E\big[yu+V_{t+1}(x-u,w(t))\big]\].
However, with transformation above, the recursino can be reduced in observable-disturbance form as

\[G_t(x)=E\big [\underset{\mu\in \{0,1\}}{max} \{w(t)u+G_{t+1}(x-u)\}\big].\]

Note that \(G_t(x)\) has similar interpretation as \(V_t(x,y)\), namely, the optimal expected reward-to-go from time \(t\) onward given state \(x(t)\) at time \(t\). Conceptually, we can consider recursion \(G_t\) in a 2-stage manner as follows. First, state \(x\) is realized but \(y\) remains uncertain. We measure the optimal expected reward at this point, yielding \(G_t(x)\). Then the value \(y=w(t)\) is realized, and we make our optimal decision. This takes us to next state \(x(t+1)\).

\(\mathbf{Exercise}\): A single-leg revenume managment problem.
1. Assuming there are 10 classes. 2. Demand \(D_j\) is calculated through discretizing a truncated normal with mean 0 and standard deviation 2, on support \([0,20]\). Speciccally, take: \[P(D_j = k) =\frac{\Phi((k + 0.5- 10)/2)-\Phi((k -0.5-10)/2)}{\Phi((20.5-10)/2)-\Phi((-0.5-10)/2)}, \quad k = 0,...,20\] Note that this discretization and re-scaling verifies: \[\overset{20}{\underset{k=0}{\Sigma}}P(Dj = k))= 1.\] 3. Total capacity available is C = 100. 4. Prices are \(p_1 = 500; p_2 = 480; p_3 = 465; p_4 = 420; p_5 = 400; p_6 = 350; p_7 = 320; p_8 = 270; p_9 = 250\), and \(p_{10} = 200\).

Formulate the problem as a dynamic progrm to solve for optimal protection levels \(y\) the total expected revenue \(V_{10}(100).\)

What is revenue management?

Every seller of a product or service faces a number of fundamental decisions.

1. A child selling lemonade outside her house has to decide on which day to have her sale, how much to ask for each cup, and when to drop the price (if at all) as the day rolls on.
   
2. A homeowner selling a house must decide when to list it, what the asking price should be, which offer to accept, and when to lower the listing price—and by how much—if no offers come in.
   

Businesses face even more complex selling decisions.
1. how can a firm segment buyers by providing different conditions and terms of trade that profitably exploit their different buying behavior or willingness to pay?
2. How can a firm design products to prevent cannibalization across segments and channels?
3. Once it segments customers, what prices should it charge each segment?If the firm sells in different channels, should it use the same price in each channel?
4. How should prices be adjusted over time, based on seasonal factors and the observed demand to date for each product?
5. If a product is in short supply, to which segments and channels should it allocate the products?
6. How should a firm manage the pricing and allocation decisions for products that are complements(seats on two connecting airline flights) or substitutes (different car categories for rentals)?

Revenue management (RM) is concerned with such demand-management decisions1 and the methodology and systems required to make them. It involves managing the firm’s “interface with the market,” as it were—with the objective of increasing revenues. RM can be thought of as the complement of supply chain management (SCM), which addresses the supply decisions and processes of a firm with the objective (typically) of lowering the cost of production and delivery.

Demand-Management Decisions

RM addresses three basic categories of demand-management decisions:

1. Structural decisions: Which selling format to use (such as posted prices, negotiations, or auctions); which segmentation or differentiation mechanisms to use (if any); which terms of trade to offer (including volume discounts and cancellation or refund options); how to bundle products; and so on.
2. Price decisions: How to set posted prices, individual-offer prices, and reserve prices (in auctions); how to price across product categories; how to price over time; how to mark down(discount) over the product lifetime; and so on.
3. Quantity decisions: Whether to accept or reject an offer to buy; how to allocate output or capacity to different segments, products, or channels; when to withhold a product from the market and sale at later points in time; and so on.

Structural decisions about which mechanism to use for selling and how to segment and bundle products are normally strategic decisions taken relatively infrequently. Whether a firm uses quantity-based or price-based RM controls varies even across firms within a given industry.

What’s New About RM?

In one sense, RM is a very old idea. The theory of RM, at a broad level, is not new either.What is new about RM is not the demand-management decisions themselves, but rather how these decisions are made. The new approach is driven by scientific advances in economics, statistics, and operations research and at the same time the advances in information technology.
The process of managing demand decisions with science and technology—implemented with disciplined processes and systems, and overseen by human analysts (a sort of “industrialization” of the entire demand-management process)—defines modern RM.

The Origins of RM?

Where did RM come from? In short, the airline industry.

The starting point for RM was the Airline Deregulation Act of 1978. With this act,the U.S. Civil Aviation Board (CAB) loosened control of airline prices, which had been strictly regulated based on standardized price and profitability targets.

The potential of this market was embodied in the rapid rise of upstars such as PeopleExpress. A significant portion of price-sensitive discretionary travelers migrated to the new, low-cost carriers. For the majors, the price war with the upstarts was deemed almost suicidal. American solved these problems using a combination of purchase restrictions and capacity controll fares. American further embarked on the development of what became known as the Dynamic Inventory Allocation and Maintenance Optimizer system (DINAMO). These efforts on DINAMO represent,in many ways, the first large-scale RM system development in the industry. DINAMO was implemented in full in January 1985 along with a new fare program entitled Ultimate Super-Saver Fares, which matched or undercut the lowest discount fares available in every market American served.

A large, modern airline today would just not be able to operate profitably without RM. By most estimates, the revenue gains from the use of RM systems are roughly comparable to many airlines’ total profitability in a good year (about 4% to 5% of revenues).

Industry Adopters Beyond the Airlines

The production-inflexibility characteristics of airlines are shared by many other service industries, such as hotels, cruise ship lines, car rental companies, theaters and sporting venues, and radio/TV broadcasters,to name a few. Indeed, RM is strongly associated with service industries.

Retailers have recently begun to adopt RM, especially in the fashion apparel, consumer electronics, and toy sectors. Retail demand is highly volatile and uncertain, consumers’ valuations change rapidly over time, and with short selling seasons and long production and distribution lead times, supply is quite inflexible. On the technology front, the introduction of bar codes and point-of-sale (POS) technology has resulted in a high degree of automation of sales transactions for most major retailers.

The energy sector has been a recent adopter of RM methods as well, principally in the area of managing the sale of pipeline capacity for gas transportation. Again, energy demands are volatile and uncertain, and the technology for generating and transmitting electricity and gas can be inflexible. Also, thanks to deregulation in the industry, there has been a lot of experimentation and innovation in the pricing practices of energy, gas, and transmission markets.

A Conceptual Framework for RM

RM generally follows four steps:

1. Data collection: collect and store relevant historical data such as prices, demand and causal factors.
2. Estimation and forecasting: estimate the demand, price elasticity, cancellation rate, and so on.
3. Optimization: find optimal control policies such as product allocations, prices, discounts and so on.
4. Control: control inventory.

In reality, the RM process involves cycling through the steps above in repeated intervals.

Example: a quantity-based RM system

Connection of Littlewoods rule to Newsvendor model

Consider a Newsvendor problem where we make a fixed decision \(Q\), that is the protection level of the higher fare class of hotel rooms, then a random event \(D\) with distribution \(F\) occurs, the number of people requesting a room at the full fare. If we protect too many rooms, i.e., \(D<Q\), then we end up earning nothing on \(Q-D\) rooms. So the overage penalty \(C\) is \(r_L\) per unsold room. If we protect too few rooms, i.e., \(D<Q\), then we forgo \(r_H-r_L\) in potential revenue on each of the \(D-Q\) rooms that could have been sold at the higher fare so the underage penalty \(B\) is \(r_H-r_L\). The critical ratio is

\[\frac{B}{B+C}=\frac{r_H-r_L}{r_H}\]
From the newsvendor analysis, the optimal protection level is the smallest value \(Q^*\) such that

\[F(Q^*)>\frac{B}{B+C}=\frac{r_H-r_L}{r_H}.\]

Single Resourece n-class static model: Geneal Case

Seuqence of envets in a periods:

1) Realizaion of \(D_i\) in period \(j\)
2) Decision \(u\) of quantity to accept of bookings where \(u=u(j,x,D_j)\), and \(x\) is the capacity at time \(j\).
3) Revenue \(p_jU\) to be collected and proceed to next stage of \(j-1\)

Let \(V_j(x)\) be the value function that represents the expected value at stage \(j\) with capacity \(x\). Hence the Belman euqaiton is

\[V_j(x)=E[\underset{0\le u\le \min\{D_j,x\}}{Max} \{p_j u_j+V_{j-1}(x-u)\}]...(1)\]
with a boundary condition \(V_0(x)=0\).
#### Case 1: Demand and capcity are discrete
Define \(\Delta V_j(x)=V_j(x)-V_j(x-1)\) the expected marginal value of capacity at stage \(j\). The Bellman equation \((1)\) can be re-written as

\[V_{j+1}(x)=V_j(x)+E[\underset{0\le u \le min(D_j,x)}{Max}\{\Sigma_{z=1}^{u} \{p_{j+1}-\Delta V_j(x+1-z)\}]...(2)\]
Caveat: Express out the terms in \(\Sigma\) as follows to obtain the equation \((2)\) from \((1)\)

\[p_{j+1}-V_j(x)+V_j(x-1)\] \[p_{j+1}-V_j(x-1)+V_j(x-2)\] \[...\] \[p_{j+1}-V_j(x+1-u)+V_j(x-u)\]
The optimal control can be expressed in one of the following 3 ways.
1) Optimal protection levels \(y_j^*=max\{x: p_{j+1}<\Delta V_j(x)\}, j=1,2,...,n-1.\)
2) Optimla booking limits \(b_j^*=C-y_{j-1}^*\), where \(j=2,3,...,n\) and \(C\) is the full capacity.
3) Optimal bid prices \(\pi_{j+1}(x)=\Delta V_j(x)\) and we accept a \(z^{th}\) request if its price exceeds the corresponding bid price at stage \(j+1\) as follows. \[ u^*(j+1,D_{j+1}) = \left\{ \begin{array}{ll} 0 & \quad p_{j+1}< \pi_{j+1}(x) \\ max\{z:p_{j+1} \ge \pi_{j+1}(x-z)\} & \quad \text{Otherwise} \end{array} \right. \] #### Case 2: Demand and capcity are continuous
Similar arguments follow as above with the same model \((1)\). The main differences are continuous variables \(D_j,x,u\). The optimal protection levels can be defined by
\[y_j^*=max\{x:p_{j+1}< \frac{\partial{V_j(x)}}{ \partial{x}}\}\] Further, we define \(n-1\) fill events as follows.

\[B_j(y,D)=\{D_1>y_1,D_1+D_2>y_2,...,D_1+D_2+...+D_j>y_j\}\]
and we have a sufficient and necessary conditon for a vector of optimal protection levels as follows.

\[P(B_j(y^*,D))=\frac{p_{j+1}}{p_1}\] As can ben seen,the optimal protection levels \(y_j\) are strictly increasing in \(j\) if the revenues \(p_j\) are strictly decreasing in \(j\). In particular, littlewoods rule is a special case.
### Single Resourece n-class static model: Heuristics

Example: 4 classes with iid normal demand as follows.

\[D_1\sim N(17.3, 5.8)\quad \text{and}\quad P_1=1050\] \[D_2\sim N(45.1, 15.0)\quad \text{and}\quad P_2=567\] \[D_3\sim N(39.6, 13.2)\quad \text{and}\quad P_3=534\] \[D_4\sim N(34.0, 11.3)\quad \text{and}\quad P_4=520\]

Solve for EMSR-a , EMSR-b and Optimal \(y_j,j=3,2,1.\)

Solution:
1) Optimal protection levels

\[P(D_1>y_1)=\frac{P_2}{P_1}\] \[P(D_1>y_1,D_1+D_2>y_2)=\frac{P_3}{P_1}\] \[P(D_1>y_1,D_1+D_2>y_2,D_1+D_2+D_3>y_3)=\frac{P_4}{P_1}\]

Solve for \(y_1,y_2,y_3\).

Reference code in R

Mu=c(17.3,62.4)
sigma=matrix(c(33.64,33.64,33.64,258.64),2,2)
pmvnorm(lower = c(16.7,42.89),mean=Mu,sigma = sigma)
qmvnorm(0.5086, mean=Mu,sigma = sigma, tail = “upper”)

Mu_3=c(17.3,62.4,102)
sigma_3=matrix(c(33.64,33.64,33.64,33.64,258.64,258.64,33.64,258.64,432.88),3,3
) pmvnorm(lower = c(16.7,42.8,72.3),mean=Mu_3,sigma = sigma_3)
qmvnorm(0.4952, mean=Mu_3,sigma = sigma_3, tail = “upper”)

2. EMSR-a
   \[p(D_3>y_3^4)=\frac{p_4}{p_3}\Rightarrow y_3^4=39.6+\Phi^{-1}(\frac{p_3-p_4}{p_3})*13.2\]
   \[p(D_2>y_2^4)=\frac{p_4}{p_2}\Rightarrow y_2^4=45.1+\Phi^{-1}(\frac{p_2-p_4}{p_2})*15.0\]
   \[p(D_1>y_1^4)=\frac{p_4}{p_1}\Rightarrow y_1^4=17.3+\Phi^{-1}(\frac{p_1-p_4}{p_1})*5.8\]
   We further obtain \(y_3=y_3^4+y_2^4+y_1^4\dot{=}14.1+24.2+17.4=55.7\)
   
   

3. EMSR-b
   At stage 4, the aggregated demand and weight-average revenue have the forms as follows. Since \(D_j, j=1,2,3\) are \(i.i.d\) normally distributed we have \[S_4=D_3+D_2+D_1\sim N(102,432.88),\]
   and \[\bar{p_4}=\frac{1050*17.3+567*45.1+534*39.6}{102}=636.11 .\] As a result, we obtain \(y_4=102+20.81*\Phi^{-1}(1-\frac{520}{636.11})\dot{=}83.0\)

Structure of optimal controls

Value functin above can be wriiten as the follwing Bellman equation.

\[V_t(x)=E[\underset{u \in \mathbb{u}(x)}{max}P(t)^{T}u(t,x,p)+V_{t+1}(x-Au)]\] with boundary conditon \(V_{T+1}=0 \forall x.\) An optimal solution satisfiles
\[u_j^*(t,x,p_j)= \left\{ \begin{array}{ll} 1 & \quad if\quad (p_j)\ge V_{t+1}(x)-V_{t+1}(x-A_j) \quad\text{and}\quad A_j\le x \\ 0 & \quad \text{Otherwise} \end{array} \right.\] It says that the optimal policy is to accept a request for product \(j\) at price \(p_j\) if and only if the capacity is enough and the prie exceeds the marginal opportunity cost.

Bid price controls

We suppose the value function has a gradient \(\Delta V_{t+1}(x)\). The optimal control can be approximated by the folllowign bid prices.
\[P_j\ge V_{t+1}(x)-V_{t+1}(x-A_j)\]
\[\dot{=} \Delta V_{t+1}^T(x)A_j\]
\[= \underset{i\in A_j}{\Sigma} \pi_i(t,x),\] where \(\pi_i(t,x)=\frac{\partial{V_{t+1}(x)}}{\partial{x_i}}.\) The bid price control policy specifies a set of bid prices for each resource, at each point in time and for each capacity level such that we accpet a request for a particular product if and only if there is available capacity and the price exceeds the sum of bid prices for all the resources used by the product.

Despite the generality and simple extension of bid prices from single resource to network, bid prices are notalways optimal form of control as the example below shows.

Example: Consider a network with 2 resources. There is one unit of capacity of each resource and two time periods. The data are shown as below.

\begin{array} {|r|r|} Period& Product& A_j& Fare& Probability\ 1 & 1 & (1,0) & $250 & 0.3\ & 2 & (0,1) & $250 & 0.3\ & 3 & (1,1) & $500 & 0.4\ 2 &3 & (1,1) & $500 & 0.8\ & NA & & & 0.2\ \end{array}

Questions: 1) what is a bid price policy? 2) what does best bid price control look like? 3) how is an optimal control policy?
Hint to optimal policy

The derived optimal expected revenue is \(440=0.88*500.\)

Virtual nesting controls

Virtual Nesting starts by assigning every origin-destination fare(ODF) to a bucket in a resource that is used in the ODF.

1. A bucket works like a fare class.
2. A bucket is a collection of ODF’s.
3. Think of higher buckets as higher customer fare classes where we price the resources higher.
   

ODF-to-bucket assignment is called indexing. Given this assignment, find the booking limits of an ODF by using EMSR heuristics or another method. Virtual Nesting is attributed to American Airlines and developed in 1983. The key issue here is indexing.

Deterministic linear programming

Let the aggregate demand at time t for product \(j\) be denoted by \(D_j\) with mean \(\mu_j\).Further \(\mathbb D=(D_1,D_2,...,D_n)\) and \(\mathbb \mu=\mathbb E [\mathbb D]\). The deterministic Linear Programming(DLP) Model can be expressed as follows.

\begin{array} &V_t^{DLP}(x)=& max P^Ty &s.t. Ayx &0y \end{array}
The decision variables \(y=(y_1,y_2,...,y_n)\) represent the partitioned allocation of capacity for each of the \(n\) products. This approximation treats demand as it is deterministic and equal to its mean \(\mu\). Using Jensen’s equality, one can show \(V_t^{DLP}(x)\) is in fact an upper bound on the optimal value function. More often, the primal allocations are discarded due to poor revenue performance. However, since solving DLP can be very efficiently, the dual prices \(\pi^{DLP}\) are used as bid prices.Empirical studies show that the performance of frequently updated dual prices is respectable.

Example: An airline network with 10 city pairs as shown below.
Solve for a deterministic solution assuming demand

Virtual nesting

Example: A simple network with single class as shown below.

Solve for a virtual nesting control.

Why demand modelling and forecasting is important in revenue management?

A revenue management system requires forecasts of quantities such as demand, price elasticity and cancellation probabilities. It is reported that 20% error reduction in forecasting leads to 1% revenue improvement. With new technology of collecting customer data in almost real time and advance of forecasting software packages, accurate forecasting adds significant values in revenue management.

Forecasting process

Demand forecsting is more of an iterative process than techniques. As shwon below, it starts with collecting and storing data. Actual modeling by statistical techniques is just an intermediate step in the overall process. More importantly, it is to monotor and manage the forecasting performance and update previous forecasts.

2. Decomposition techniques
3. Exponential smoothing
4. Regression methods
5. Time-series analysis
6. Bayesian forecasting methods
7. Neural-network methods