From 1938 to 1978, the Civil Aeronautics Board set fares, routes, and schedules for all interstate air transport. Most airlines were very positive on this system, as it guaranteed their profits.
However, this system led to higher costs for a traveling public as well as to various inefficiencies. For example, applications for new routes and fares were often delayed or dismissed. In response to these inefficiencies, the administration of President Carter passed the Airline Deregulation Act in 1978.
The act encouragedThis led to more passengers. The number of air passengers increased from over 200 million in 1974 to over 720 million in 2010. More competition led to lower fares, as we discussed, while meeting operating costs. This further led to heavy losses by air carriers. Nine major carriers and more than a hundred smaller airlines went bankrupt between 1978 and 2002. So it is natural to ask how did airlines compete?
In their attempt to sell more seats, airlines started to offer deep discounts. For example, on January 17, 1985, American Airlines launched its Ultimate Super Saver fares to compete with PeopleExpress. The key strategy involved selling enough seats to cover fixed operating costs while selling remaining seats at higher rates to maximize revenues. This led to the science of revenue management that we’ll study in this lecture.
The key question in revenue management is how many seats to sell on discount. The key consideration is:
To illustrate how linear optimization works in revenue management, let us consider a simple example –
a flight from New York to Los Angeles. In this flight, there are two types of economy fares, Early Bird fares that cost $238, and Last Minute fares that cost $617. In this flight, a Boeing 757 is used that has 166 economy seats.
Demand for these prices has been forecasted using analytics tools, looking at historical data and incorporating models like time series or linear regression.
Forecasts have errors, and therefore, we need to assess the sensitivity of our decisions to these errors. To illustrate the use of linear optimization, we assume that demand has already been forecasted.
We’ll illustrate how our decisions on how many discount seats to sell vary as the demand forecasts vary. If the demand for regular seats is 50, and for discounted fares is 150, and the capacity is 166 seats, then the optimal allocation is going to be to sell the 50 seats to satisfy the regular demand, and then we allocate the remaining 116 seats to the discounted fare class. If the regular demand increases to 100 seats, then we allocate these 100 seats to these customers, and only 66 seats to discounted fare customers. Finally, if the regular demand increases to 200, then we allocate all of our capacity, 166 seats, to these customers. While this seems simple, what happens if we have 100 flights with connections in tens of fares? We’ll next see how to formulate the problem mathematically and solve it in a systematic way, using linear optimization.
We’ll assume that the price of regular seats is $617, and the price of discount seats is $238. Also, let’s assume that we forecasted the demand of regular seats to be 100, and the demand of discount seats to be 150. The capacity of our airplane is 166 seats. Let’s go ahead and formulate this mathematically as a linear optimization problem.
In the case of regular seats, this is $617 times R, the number of regular seats we sell. And for discount seats, this is $230 times D, the number of discount seats we sell. We sum these together to get the total revenue, and our objective is to maximize this sum.
Regular seats, R, shouldn’t exceed 100. So R should be less than or equal to 100.
Discount seats, D, can’t exceed 150. So D should be less than or equal to 150.
The final step is to make sure our variables are taking reasonable values. In this case, it wouldn’t make sense to sell a negative number of seats, so we need to make sure that both R and D are greater than or equal to 0.
Mathematically, this can be written as maximize 617R + 238D, the total revenue, subject to the constraints: R + D is less than or equal to 166, the capacity constraint; R less than or equal to 100, and D less than or equal to 150, which are the demand constraints; and R and D are both greater than or equal to 0. This is called a linear optimization problem.
Beneficial to allocate a bigger aircraft for this flight. This would change the capacity constraint, which currently limits the capacity to 166. With our current aircraft, the management knows that the cost per hour is $12,067.
In this script file, we show how the airline revenue management problems discussed in this lecture can be solved in R using the “lpSolveAPI” package. This package allows you to solve linear optimization problems in R using the lp_solve library, which is an open-sourced optimization solver.
If you are solving larger and more complex optimization problems, lp_solve might not be powerful enough to solve your problems. There are other optimization packages available in R that rely on commercial solvers, such as cplexAPI and Rcplex. For more information, see the CRAN Optimization page: http://cran.us.r-project.org/web/views/Optimization.html
First, you need to install and load the lpSolveAPI package:
library(lpSolveAPI)Now let’s start by solving the simple airline problem with just two decision variables: the number of regular seats to offer, and the number of discount seats to offer.
The first step is to create a model, which takes as arguments the number of constraints in your model, and the number of decision variables in your model. We have three constraints (one capacity constraint and two demand constraints) and two decision variables.
AirlineSimple = make.lp(3,2)Now we need to set up the constraints and objective. The best way to do this using the lpSolveAPI package is by viewing the constraints in a matrix format. Our objective and three constraints are as follows: ##### max 617R + 238D ##### subject to 1R + 1D <= 166 ##### 1R + 0D <= 100 ##### 0R + 1D <= 150
So the first column in our constraint matrix is c(1,1,0), and the second column in our constraint matrix is c(1,0,1). We also need to indicate that these are less-than-or-equal constraints, and set the right-hand-side values to c(166,100,150):
set.column(AirlineSimple, 1, c(1,1,0))
set.column(AirlineSimple, 2, c(1,0,1))
set.constr.type(AirlineSimple, c("<=","<=","<="))
set.rhs(AirlineSimple, c(166,100,150))And our objective coefficients are c(617,238):
set.objfn(AirlineSimple, c(617,238))The default setting is minimize for the objective, so we need to tell R that we are maximizing our objective:
lp.control(AirlineSimple,sense='max')## $anti.degen
## [1] "fixedvars" "stalling"
##
## $basis.crash
## [1] "none"
##
## $bb.depthlimit
## [1] -50
##
## $bb.floorfirst
## [1] "automatic"
##
## $bb.rule
## [1] "pseudononint" "greedy" "dynamic" "rcostfixing"
##
## $break.at.first
## [1] FALSE
##
## $break.at.value
## [1] 1e+30
##
## $epsilon
## epsb epsd epsel epsint epsperturb epspivot
## 1e-10 1e-09 1e-12 1e-07 1e-05 2e-07
##
## $improve
## [1] "dualfeas" "thetagap"
##
## $infinite
## [1] 1e+30
##
## $maxpivot
## [1] 250
##
## $mip.gap
## absolute relative
## 1e-11 1e-11
##
## $negrange
## [1] -1e+06
##
## $obj.in.basis
## [1] TRUE
##
## $pivoting
## [1] "devex" "adaptive"
##
## $presolve
## [1] "none"
##
## $scalelimit
## [1] 5
##
## $scaling
## [1] "geometric" "equilibrate" "integers"
##
## $sense
## [1] "maximize"
##
## $simplextype
## [1] "dual" "primal"
##
## $timeout
## [1] 0
##
## $verbose
## [1] "neutral"If we want to take a look at our model, we can just type:
AirlineSimple## Model name:
## C1 C2
## Maximize 617 238
## R1 1 1 <= 166
## R2 1 0 <= 100
## R3 0 1 <= 150
## Kind Std Std
## Type Real Real
## Upper Inf Inf
## Lower 0 0You should see that there is a row called “Lower” in the model output - the values of zero indicate that our decision variables are constrained to be non-negative, which is the default setting. If you want to change the lower or upper bounds for a decision variable, you can do so with the set.bounds function. (Next week we will learn about integer and binary decision variables - to change a decision variable to one of these types, you can use the set.type function.)
Now we are ready to solve our model:
solve(AirlineSimple)## [1] 0An output of zero means that the model was successfully solved. You can look at the optimal objective function value or optimal decision variable values with get.objective and get.variables:
get.objective(AirlineSimple)## [1] 77408get.variables(AirlineSimple)## [1] 100 66You should get an objective value of 77408 and decision variable values of 100 and 66, just like we did in lecture.
The following commands set up and solve the more sophisticated airline problem with six decision variables:
AirlineConnecting = make.lp(8,6)
set.column(AirlineConnecting, 1, c(1,1,1,0,0,0,0,0))
set.column(AirlineConnecting, 2, c(1,1,0,1,0,0,0,0))
set.column(AirlineConnecting, 3, c(1,0,0,0,1,0,0,0))
set.column(AirlineConnecting, 4, c(1,0,0,0,0,1,0,0))
set.column(AirlineConnecting, 5, c(0,1,0,0,0,0,1,0))
set.column(AirlineConnecting, 6, c(0,1,0,0,0,0,0,1))
set.constr.type(AirlineConnecting, rep("<=",8))
set.rhs(AirlineConnecting, c(166,166,80,120,75,100,60,110))
set.objfn(AirlineConnecting, c(428,190,642,224,512,190))
lp.control(AirlineConnecting,sense='max')## $anti.degen
## [1] "fixedvars" "stalling"
##
## $basis.crash
## [1] "none"
##
## $bb.depthlimit
## [1] -50
##
## $bb.floorfirst
## [1] "automatic"
##
## $bb.rule
## [1] "pseudononint" "greedy" "dynamic" "rcostfixing"
##
## $break.at.first
## [1] FALSE
##
## $break.at.value
## [1] 1e+30
##
## $epsilon
## epsb epsd epsel epsint epsperturb epspivot
## 1e-10 1e-09 1e-12 1e-07 1e-05 2e-07
##
## $improve
## [1] "dualfeas" "thetagap"
##
## $infinite
## [1] 1e+30
##
## $maxpivot
## [1] 250
##
## $mip.gap
## absolute relative
## 1e-11 1e-11
##
## $negrange
## [1] -1e+06
##
## $obj.in.basis
## [1] TRUE
##
## $pivoting
## [1] "devex" "adaptive"
##
## $presolve
## [1] "none"
##
## $scalelimit
## [1] 5
##
## $scaling
## [1] "geometric" "equilibrate" "integers"
##
## $sense
## [1] "maximize"
##
## $simplextype
## [1] "dual" "primal"
##
## $timeout
## [1] 0
##
## $verbose
## [1] "neutral"solve(AirlineConnecting)## [1] 0get.objective(AirlineConnecting)## [1] 120514get.variables(AirlineConnecting)## [1] 80 0 75 11 60 26You should get an objective function value of 120514 and decision variable values of 80, 0, 75, 11, 60, 26.
The slides from all videos in this lecture can be downloaded here: https://d37djvu3ytnwxt.cloudfront.net/asset-v1:MITx+15.071x_3+1T2016+type@asset+block/Unit8_RevenueManagement_AllSlides.pdf