{ "cells": [ { "cell_type": "markdown", "id": "dcadad27-4c87-4222-b248-17b1068311ff", "metadata": { "tags": [], "id": "dcadad27-4c87-4222-b248-17b1068311ff" }, "source": [ "{index} single: application; airline seating allocation\n", "\n", "{index} single: solver; cbc\n", "\n", "{index} pandas dataframe\n", "\n", "{index} single: AMPL; sets\n", "\n", "{index} stochastic optimization\n", "\n", "{index} chance constraints\n", "\n", "{index} sample average approximation\n", "\n", "{index} two-stage problem\n", "\n", "\n", "# Airline seat allocation problem\n", "\n", "## Attribution\n", "\n", "The following problem statement is adapted from an exercise and examples presented by Birge and Louveaux (2011).\n", "\n", "* Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.\n", "\n", "The adaptations include a change to parameters for consistency among reformulations of the problem, and additional treatments for sample average approximation (SAA) with chance constraints." ] }, { "cell_type": "markdown", "id": "78a7e349-0b92-4f23-b76b-b1d0e1e153f0", "metadata": { "tags": [], "id": "78a7e349-0b92-4f23-b76b-b1d0e1e153f0" }, "source": [ "## Problem description\n", "\n", "An airline is deciding how to partition a new plane for the Amsterdam-Buenos Aires route. This plane can seat 200 economy-class passengers. A section can be created for first-class seats, but each of these seats takes the space of 2 economy-class seats. A business-class section can also be created, but each of these takes the space of 1.5 economy-class seats. The profit for a first-class ticket is three times the profit of an economy ticket, while a business-class ticket has a profit of two times an economy ticket's profit. Once the plane is partitioned into these seating classes, it cannot be changed.\n", "\n", "The airlines knows that the plane will not always be full in every section. The airline has initially identified three scenarios to consider with about equal frequency:\n", "\n", "1. Weekday morning and evening traffic;\n", "2. Weekend traffic; and\n", "3. Weekday midday traffic.\n", "\n", "Under Scenario 1 the airline thinks they can sell as many as 20 first-class tickets, 50 business-class tickets, and 200 economy tickets. Under Scenario 2 these figures are 10 , 24, and 175, while under Scenario 3, they are 6, 10, and 150, respectively. The following table summarizes the forecast demand for these three scenarios.\n", "\n", "
\n", "\n", "| Scenario | First-class seats | Business-class seats | Economy-class seats |\n", "| :-- | :-: | :-: | :-: |\n", "| (1) weekday morning and evening | 20 | 50 | 200 |\n", "| (2) weekend | 10 | 24 | 175 |\n", "| (3) weekday midday | 6 | 10 | 150 |\n", "| **Average Scenario** | **12** | **28** | **175** |\n", "\n", "
\n", "\n", "The goal of the airline is to maximize ticket revenue. For marketing purposes, the airline will not sell more tickets than seats in each of the sections (hence no overbooking strategy). We further assume customers seeking a first-class or business-class seat will not downgrade if those seats are unavailable." ] }, { "cell_type": "markdown", "id": "347cbd20-15e4-4634-8a05-e782dc0e0929", "metadata": { "id": "347cbd20-15e4-4634-8a05-e782dc0e0929" }, "source": [ "## Installation and imports" ] }, { "cell_type": "code", "execution_count": 1, "id": "ea71de65", "metadata": { "ExecuteTime": { "end_time": "2022-09-30T21:49:05.660595Z", "start_time": "2022-09-30T21:49:05.457825Z" }, "id": "ea71de65", "outputId": "2338046a-dbcd-45be-aa03-227edb45e891", "colab": { "base_uri": "https://localhost:8080/" } }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "Using default Community Edition License for Colab. Get yours at: https://ampl.com/ce\n", "Licensed to AMPL Community Edition License for the AMPL Model Colaboratory (https://colab.ampl.com).\n" ] } ], "source": [ "# install dependencies and select solver\n", "%pip install -q amplpy pandas matplotlib numpy scipy\n", "\n", "SOLVER = \"highs\"\n", "\n", "from amplpy import AMPL, ampl_notebook\n", "\n", "ampl = ampl_notebook(\n", " modules=[\"highs\"], # modules to install\n", " license_uuid=\"default\", # license to use\n", ") # instantiate AMPL object and register magics" ] }, { "cell_type": "code", "execution_count": 2, "id": "e91fbe82", "metadata": { "ExecuteTime": { "end_time": "2022-09-30T21:49:07.404490Z", "start_time": "2022-09-30T21:49:05.663157Z" }, "id": "e91fbe82" }, "outputs": [], "source": [ "import numpy as np\n", "import pandas as pd\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "id": "2f7df9f7-9a96-4358-9e47-50cd63d7611a", "metadata": { "id": "2f7df9f7-9a96-4358-9e47-50cd63d7611a" }, "source": [ "## Problem data\n", "\n", "Pandas DataFrames and Series are used to encode problem data in the following cell, and to encode problem solutions in subsequent cells." ] }, { "cell_type": "code", "execution_count": 3, "id": "51e9fdd8-d586-48e6-be86-0d97fbad8a3f", "metadata": { "id": "51e9fdd8-d586-48e6-be86-0d97fbad8a3f" }, "outputs": [], "source": [ "# scenario data\n", "demand = pd.DataFrame(\n", " {\n", " \"morning and evening\": {\"F\": 20, \"B\": 50, \"E\": 200},\n", " \"weekend\": {\"F\": 10, \"B\": 24, \"E\": 175},\n", " \"midday\": {\"F\": 6, \"B\": 10, \"E\": 150},\n", " }\n", ").T\n", "\n", "# global revenue and seat factor data\n", "capacity = 200\n", "revenue_factor = pd.Series({\"F\": 3.0, \"B\": 2.0, \"E\": 1.0})\n", "seat_factor = pd.Series({\"F\": 2.0, \"B\": 1.5, \"E\": 1.0})" ] }, { "cell_type": "markdown", "id": "cfbd3423-f10d-49a4-b7f7-f6545729c9cc", "metadata": { "id": "cfbd3423-f10d-49a4-b7f7-f6545729c9cc" }, "source": [ "## Analytics\n", "\n", "Prior to optimization, a useful first step is to prepare an analytics function to display performance for any given allocation of seats. The first-stage decision variables are the number of seats allocated for each class $c\\in C$. We would like to provide a analysis showing the operational consequences for any proposed allocation of seats. For this purpose, we create a function seat_report() that show the tickets that can be sold in each scenario, the resulting revenue, and the unsatisfied demand ('spillage').\n", "\n", "To establish a basis for analyzing possible solutions to the airline's problem, this function first is demonstrated for the case where the airplane is configured as entirely economy-class." ] }, { "cell_type": "code", "execution_count": 4, "id": "3eed107a-1fec-4d6c-9b01-f399fbe3bb99", "metadata": { "id": "3eed107a-1fec-4d6c-9b01-f399fbe3bb99", "outputId": "d4a06a5a-6e08-4437-d421-f8f4f42ed54d", "colab": { "base_uri": "https://localhost:8080/", "height": 1000 } }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "\n", "Seat Allocation\n" ] }, { "output_type": "display_data", "data": { "text/plain": [ " F B E TOTAL\n", "seat allocation 0.0 0.0 200.0 200.0\n", "economy equivalent seat allocation 0.0 0.0 200.0 200.0" ], "text/html": [ "\n", "
\n", "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
FBETOTAL
seat allocation0.00.0200.0200.0
economy equivalent seat allocation0.00.0200.0200.0
\n", "
\n", " \n", "
\n" ] }, "metadata": {} }, { "output_type": "stream", "name": "stdout", "text": [ "\n", "Tickets Sold\n" ] }, { "output_type": "display_data", "data": { "text/plain": [ " F B E\n", "morning and evening 0 0 200\n", "weekend 0 0 175\n", "midday 0 0 150" ], "text/html": [ "\n", "
\n", "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
FBE
morning and evening00200
weekend00175
midday00150
\n", "
\n", " \n", "
\n" ] }, "metadata": {} }, { "output_type": "stream", "name": "stdout", "text": [ "\n", "Seats not Sold\n" ] }, { "output_type": "display_data", "data": { "text/plain": [ " F B E\n", "morning and evening 0 0 0\n", "weekend 0 0 25\n", "midday 0 0 50" ], "text/html": [ "\n", "
\n", "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
FBE
morning and evening000
weekend0025
midday0050
\n", "
\n", " \n", "
\n" ] }, "metadata": {} }, { "output_type": "stream", "name": "stdout", "text": [ "\n", "Spillage (Unfulfilled Demand)\n" ] }, { "output_type": "display_data", "data": { "text/plain": [ " F B E\n", "morning and evening 20 50 0\n", "weekend 10 24 0\n", "midday 6 10 0" ], "text/html": [ "\n", "
\n", "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
FBE
morning and evening20500
weekend10240
midday6100
\n", "
\n", " \n", "
\n" ] }, "metadata": {} }, { "output_type": "stream", "name": "stdout", "text": [ "\n", "Expected Revenue (in units of economy ticket price): 175.00\n" ] }, { "output_type": "display_data", "data": { "text/plain": [ "