Deliverables
DS/FIN 372 – Optimization Methods in Finance Project 5 – Dynamic Programming
One RMarkdown (.Rmd) file and one HTML file, submitted to Canvas. Your report should go into some detail about how you solved the problem, include some graphs that explain your results, and include relevant code chunks in the final output. 66% of your grade will be based on whether you get the problem right or not, the remaining 34% will be based on the quality of your analysis. We will re-run your code with a new data set. If you don’t get the right answer or your Rmd file doesn’t run, we will go through your code and give partial credit accordingly. The easier it is to read your code the easier it is for us to understand what you’re doing, so use a lot of comments in your code!
Problem Overview
Should airlines overbook flights? To passengers, it is annoying to be on an overbooked flight, but is it worth it to airlines? This project will combine the airline ticket pricing problem we worked in class with the bus operator problem we worked in class, to pick the optimal allowed overbooking policy.
You work for an airline in the pricing department and you want to find the optimal pricing policy and number of tickets to offer for sale on a particular flight to maximize expected discounted profit, which comes from the revenue of ticket sales minus overbooking costs. Revenue comes in from demand for tickets in the time before takeoff, where you will decide the optimal price to charge each day. Overbooking costs come in when more people show up for the flight than there are seats on the plane, if the flight is overbooked. In that case you must pay a stipend to the passengers who cannot get on the plane.
The flight you’re analyzing has two ticket classes, coach and first-class. Your manager is not willing to allow overbooking in first-class, due to loss of goodwill from high-paying customers, but is open to the idea of overbooking coach. In the case that more people show up with tickets for coach than there are seats available in coach, you can bump ticket holders up to first-class if there are seats available in first- class. Everyone that gets bumped up to first-class from coach imposes an overbooking cost to the airline, because the service in first-class is more costly to the airline, and everyone that does not get a seat on the flight imposes a greater overbooking cost to the airline.
When selling tickets in coach there are two possible ticket prices, each leading to different demand distributions, and there are two possible ticket prices for first-class, again leading to different demand distributions. We will assume that demand for coach and first-class seats are independent. On each day there will be either 0 or 1 ticket sold in coach and 0 or 1 ticket sold in first-class. The probability of a sale for each ticket class depends on the price of the ticket; just like in the example in class. If there is more demand for first-class than there are seats in first-class, customers won’t buy a coach seat. If there is more demand for coach seats than allowed by the overbooking policy, customers won’t buy a first-class seat.
For a given overbooking policy you will find the optimal pricing policy using dynamic programming. You will solve this dynamic programming problem for several overbooking policies and find the overbooking policy with the largest expected discounted profit.
Specifics
1) Assume there are 365 days until the plane departs, so you have 365 opportunities to sell tickets, after that people either show up or not to the flight. There are 100 seats in coach and 20 seats in first-class. Each coach ticket holder shows up to the flight with probability 95%, and each first-class ticket holder shows up to the flight with probability 98%. You can charge $300 or $350 for coach tickets, and you can charge $425 or $500 for first-class tickets. On each day, if the price is $300 for coach there is a 65% chance a coach ticket is sold, if the price is $350 for coach there is a 30% chance a coach ticket is sold, if the price is $425 for first-class there is an 8% chance a first-class ticket is sold, and if the price is $500 for first-class there is a 4% chance a first-class ticket is sold. For the first iteration, examine the expected discounted revenue when you allow coach to be oversold by 5 seats. It costs the airline $50 to bump a coach passenger to first-class and it costs the airline $425 to bump a coach passenger off the plane. The discount rate is 15% per year, so the discount factor is 1/(1+0.15/365). What is the expected discounted profit of selling these tickets and paying out overbooking costs over the course of the year?
2) Repeat step (1) while allowing coach to be oversold by 6, 7, 8, …, 15 seats.
3) Which overbooking policy from step (2) leads to the largest profits by the airline?
4) Now that you have solved the problem backwards, use the optimal overbooking policy to
simulate the solution forward many times. How often is coach overbooked? How often are passengers kicked off the plane? What is the average overbooking cost? What is the volatility of discounted profits? Are there any other interesting questions you can think of? Make a few histograms to examine these questions.
5) Pretend you are an analyst in the sales department of a major airline. Your boss is interested in potentially overbooking flights. Your team has been asked to write a report about the effectiveness of overbooking. Write this project as if this is what you’re going to deliver to your boss. Your boss is pretty technical and understands optimization, so don’t be afraid to include quantitative material. Your boss is also busy, so be sure to include some visualizations to get the important points across. For the purpose of your report, you can assume that your boss is interested in the data posted with the project.
NOTE: I will spend a fair amount of time talking about how to solve this problem in class. I highly recommend you attend lecture live on zoom rather than watching the recorded videos later, so that you can get your questions in.