MSBA –Optimization 2 Project 2 – Dynamic Programming

Deliverables

One python (.ipynb or .py) 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 the presentation of your analysis. We will re-run your code with a new set of parameters. If you don’t get the right answer or your python 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 expand the airline ticket pricing problem we worked in class to pick an optimal 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; there are of course other costs, but we’ll consider those to be fixed costs that we can’t optimize over. 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 97%. 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 daily 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?

        a. On the day the flight takes off there is no revenue, only costs. You can calculate the expected cost using the binomial distribution (scipy.stats.binom.pmf), where the number of trials is the number of tickets sold, and a success is if a passenger shows up for the flight.
    2) Repeat step (1) while allowing coach to be oversold by 6, 7, 8, …, 15 seats. Which overbooking policy from this leads to the largest profits by the airline?
    3) Compare the previous policy, where there is a hard cap on seats sold, to another strategy where there is a third choice on each day when you’re deciding ticket prices. Consider a new policy that allows the airline to choose to sell no coach tickets on a day if it wants; the airline has the option to force demand to 0 on a day. Now there are 3 choices each day for coach: high price, low price, and no sale. There are still just 2 choices each day for first class: high and low price. Assume that the airline will never sell more than 120 seats in coach, but on any one day they can choose to not sell coach tickets. This way they can stop over-selling tickets not just based on how many they have sold, but also on how many days are left to sell. Does this policy have a better or worse expected profit than the best policy from step 2?

    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 graphs to examine these questions. Do this for both policies above.

    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. Also, be sure to compare and contrast the two types of overbooking policies you examined here. For the purpose of your report, you can assume that your boss is interested in the probabilities listed with the project.