{ "cells": [ { "cell_type": "markdown", "id": "75c5a019", "metadata": {}, "source": [ "```{index} single: application; fleet assignment\n", "```\n", "```{index} single: solver; cbc\n", "```\n", "```{index} single: solver; highs\n", "```\n", "```{index} pandas dataframe\n", "```\n", "```{index} single: AMPL; AMPL Python API\n", "```\n", "```{index} single: AMPL MP Library\n", "```\n", "```{index} simulations\n", "```\n", "```{index} networkx\n", "```\n", "```{index} Gantt charts\n", "```\n", "\n", "# Fleet assignment problem" ] }, { "cell_type": "markdown", "id": "f5db1388", "metadata": {}, "source": [ "## Problem description\n", "\n", "Given a set of flights to be flown, an airline company needs to determine the specific route flown by each airplane in the most cost-effective way. Clearly, the airline company should try to use as fewer airplanes as possible, but the same airplane can operate two subsequent flights only if the time interval between the arrival of the first flight and the departure of the next flight is longer than or equal to one hour.\n", "\n", "The task of the airline operations team is to determine the minimum number of airplanes needed to operate the given list of flights. This problem is known as the **fleet assignment problem** or **aircraft rotation problem**. We are going to consider the simplest version of the problem where all the of the $M$ available airplanes are assumed to be identical." ] }, { "cell_type": "code", "execution_count": 1, "id": "483305d0", "metadata": { "tags": [] }, "outputs": [], "source": [ "# install dependencies and select solver\n", "%pip install -q amplpy numpy pandas matplotlib networkx\n", "\n", "SOLVER = \"highs\" # highs, scip, cbc, mosek, gurobi, cplex, xpress, knitro\n", "\n", "from amplpy import AMPL, ampl_notebook\n", "\n", "ampl = ampl_notebook(\n", " modules=[\"coin\", \"highs\"], # modules to install\n", " license_uuid=\"default\", # license to use\n", ") # instantiate AMPL object and register notebook magics" ] }, { "cell_type": "markdown", "id": "2dd532d5", "metadata": {}, "source": [ "## Generate Flight Data" ] }, { "cell_type": "code", "execution_count": 3, "id": "020a15ef", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "
\n", " | Departure | \n", "Arrival | \n", "
---|---|---|
Flight | \n", "\n", " | \n", " |
1 | \n", "13 | \n", "22 | \n", "
2 | \n", "14 | \n", "23 | \n", "
3 | \n", "10 | \n", "19 | \n", "
4 | \n", "10 | \n", "22 | \n", "
5 | \n", "1 | \n", "4 | \n", "