Fleet assignment problem#
Problem description#
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.
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.
# install dependencies and select solver
%pip install -q amplpy numpy pandas matplotlib networkx
SOLVER = "highs" # highs, scip, cbc, mosek, gurobi, cplex, xpress, knitro
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["coin", "highs"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register notebook magics
Generate Flight Data#
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from numpy.random import RandomState
# python generator creates departure and arrival times for a single airport
def generate_flights(
N_flights=30, min_duration=1, max_duration=4, max_departure=24, seed=0
):
rs = RandomState(seed)
for flight in range(N_flights):
end_flight = max_departure + 1
while end_flight > max_departure:
start_flight = np.floor(max_departure * rs.rand())
end_flight = start_flight + 3 * np.ceil(
(max_duration + 1 - min_duration) * rs.rand()
)
yield flight + 1, int(start_flight), int(end_flight)
# generate flight data
FlightData = pd.DataFrame(
[[flight, departure, arrival] for flight, departure, arrival in generate_flights()]
)
FlightData.columns = ["Flight", "Departure", "Arrival"]
FlightData.set_index("Flight", inplace=True)
FlightData.head()
| Departure | Arrival | |
|---|---|---|
| Flight | ||
| 1 | 13 | 22 |
| 2 | 14 | 23 |
| 3 | 10 | 19 |
| 4 | 10 | 22 |
| 5 | 1 | 4 |
Visualize Flight Data#
# visualize flight data
def draw_flights(FlightData):
bar_style = {"alpha": 1.0, "lw": 10, "solid_capstyle": "butt"}
text_style = {
"fontsize": 7,
"color": "white",
"weight": "bold",
"ha": "center",
"va": "center",
}
fig = plt.figure(figsize=(12, 7))
ax = fig.add_subplot(111, xlabel="Departure/Arrival Time", title="Flight schedule")
ax.get_yaxis().set_visible(False)
for flight, row in FlightData.iterrows():
departure, arrival = row
ax.plot([departure, arrival], [flight] * 2, "gray", **bar_style)
ax.text((departure + arrival) / 2, flight, f"Flight {flight}", **text_style)
for hr in range(25):
ax.axvline(hr, alpha=0.1)
ax.set_xlim(-1, 25)
ax.set_xticks([4 * i for i in range(7)])
return ax
ax = draw_flights(FlightData)
AMPL Model#
The fleet assignment problem can be formulated and solved as an MILP. The idea of the MILP formulation is to construct feasible paths in a directed graph where the flights are nodes with indices \(\mathcal{F} = \left\{ 1, \ldots, F \right\}\). The set of arcs \(\mathcal{A} \subseteq \mathcal{F} \times \mathcal{F}\) that can be used by each aircraft is then:
The following cell finds the set of arcs that can be used. These arcs are displayed in a graph of the flight data. Arcs corresponding to the minimum time between arrival and departure are highlighted in red.
min_time = 1
def feasible_flight_pairs(FlightData, min_time=1):
# return a dictionary of turnaound times index by flight pairs
turnaround = (
lambda pair: FlightData.loc[pair[1], "Departure"]
- FlightData.loc[pair[0], "Arrival"]
)
pairs = filter(
lambda pair: turnaround(pair) >= min_time,
[(i, j) for i in FlightData.index for j in FlightData.index if i != j],
)
return {pair: turnaround(pair) for pair in pairs}
flight_pairs = feasible_flight_pairs(FlightData).keys()
The following cell presents a visualization of the graph of feasible paths in which an aircraft can be reassigned from one flight to subsequent flight. Each node on the graph corresponds to a flight. An edge from flight \(f_1\) to flight \(f_2\) is included only if there is at least min_time hours available to turn around the aircraft. Edges that allow exactly min_time hours between flights are colored red because these will be the most affected by unexpected flight delays.
import networkx as nx
dg = nx.DiGraph()
for flight in FlightData.index:
dg.add_node(flight)
for pair, dur in feasible_flight_pairs(FlightData).items():
dg.add_edge(pair[0], pair[1], color="r" if dur <= min_time else "g")
size = int(1.5 * np.sqrt(len(FlightData)))
fig = plt.figure(figsize=(size, size))
pos = nx.circular_layout(dg)
nx.draw_networkx_nodes(dg, pos=pos, node_size=500, alpha=0.8)
nx.draw_networkx_labels(dg, pos=pos, font_color="w")
nx.draw_networkx_edges(
dg, pos=pos, width=0.5, edge_color=[dg.edges[u, v]["color"] for u, v in dg.edges]
);
Naive model formulation#
An idea of an MILP formulation of the problem is to construct a feasible path for each aircraft in a graph where the flights are nodes with indices \(1, \ldots, F\), and there is one source node \(0\) and a sink node \(F + 1\). The set of arcs \(\mathcal{A}'\) that can be used by each aircraft is then:
where \(0\) and \(F + 1\) play the role of dummy flights before the first/after the last flight of a given aircraftâs assignment.
Denote the set of aircraft indices as \(\mathcal{M} = \{ 1, \ldots, M\}\). The decision variables then are:
\(x_{f_1, f_2, i} \in \{0, 1\}\), \(a \in \mathcal{A}'\), \(i \in \mathcal{M}\) indicating whether the connection \((f_1, f_2) = a\) is operated by aircraft \(i\)
\(y_i \in \{0, 1\}\), for \(i \in \mathcal{M}\) indicating whether aircraft \(i\) is used or not
The corresponding MILP is then:
where
the objective function \eqref{eq:71a} aims to minimize the number of airplanes used;
constraint \eqref{eq:71b} enforces that for a given real flight the number of used incoming arcs with airplane \(i\) must be equal to the number of outgoing arcs with this airplane;
constraint \eqref{eq:71c} ensures that each flight is operated by exactly one aircraft;
constraint \eqref{eq:71d} enforces that each airplane serves at most one sequence of flights;
constraint \eqref{eq:71e} ensures that if at least one arc \((f, 0)\) is used using a given airplane, then this airplane is used
This formulation is very explicit and each decision there clearly corresponds to a real-life decision. However, it has a drawback â it is blind to the aircraft being all identical. Consider a situation where aircraft \(1\) is assigned to operate flights \((1, 2, 3)\) and aircraft \(2\) is assigned to operate flights \((4, 5)\). Then, one can simply swap the flight assignment of the two aircraft between them and arrive at another solution is essentially the same if the aircraft are all identical. In terms of mathematical optimization, this means that the problem has a lot of symmetry which produces a huge solution space that the solving algorithm has to explore.
A normal practice is to eliminate symmetry from the problem, for example, by adding so-called symmetry-breaking constraints that do not change the problem but allow only one out of many equivalent solutions. Here, one such constraint would be
which would ensure, at least, that we utilize airplanes in the order they appear on the list, i.e., aircraft \(2\) cannot be used if aircraft \(1\) was not used. However, an even better way of removing symmetry from the problem is to remove the airplanes from the model altogether.
Symmetry-free and totally-unimodular model formulation#
In the next model we only create flight combinations to be operated by a single aircraft and assign the actual aircraft in a post-processing step. First, for each node \(f\in\mathcal{F}\) in the DiGraph we define a set of input nodes \(\mathcal{I}_f = \{f_1: (f_1, f)\in\mathcal{A}\}\) and a set of output nodes \(\mathcal{O}_f = \{f_1: (f, f_1)\in\mathcal{A} \}\). For this application, we use the Python set object to scan the feasible flight pairs and find the inputs and outputs nodes for each flight node.
in_nodes = {flight: set() for flight in FlightData.index}
out_nodes = {flight: set() for flight in FlightData.index}
for flight1, flight2 in flight_pairs:
in_nodes[flight2].add(flight1)
out_nodes[flight1].add(flight2)
The decision variables are:
\(x_{f_1, f_2}\in\{0,1\}\) for all \((f_1, f_2) \in\mathcal{A}\) where \(x_{f_1, f_2} = 1\) indicates that an aircraft used for arriving flight \(f_1\) will be used for departing flight \(f_2\).
\(p_f\in\{0,1\}\) for all \(f\in\mathcal{F}\) where \(p_f = 1\) indicates a previously unassigned aircraft will be used for departing flight \(f\).
\(q_f\in\{0,1\}\) for all \(f\in\mathcal{F}\) where \(q_f = 1\) indicates an aircraft will be unassigned after arrival of flight \(f\).
The binary variables \(p_f\) and \(q_f\) correspond to arcs that link nodes to the sources and sinks of aircraft needed to complete all of the flights \(f\in\mathcal{F}\). The objective is to minimize the number of required aircraft subject to the constraints that exactly one aircraft is assigned to and released from each node.
This model will give solutions where decisions \(x_{f_1, f_2}\) will yield paths corresponding to sequences of flights that can be operated with a single aircraft. To such paths, we can assign aircraft in an arbitrary fashion after the optimization is finished.
As it turns out, for this model formulation it is also easy to verify using the tools of Chapter 4 that the corresponding matrix formulation of the model is totally unimodular. That means, it is possible to eliminate the integrality restriction on the decision variables (keeping the \([0, 1]\) interval bounds) to arrive at an LP-formulated model that yields integral solutions without explicitly requiring it.
For that reason, we are going to use this model formulation in our further analysis.
%%writefile fleet_assign.mod
set FLIGHTS;
set PAIRS in {FLIGHTS, FLIGHTS};
var x{PAIRS} binary;
var p{FLIGHTS} binary;
var q{FLIGHTS} binary;
s.t. Sources{f in FLIGHTS}:
p[f] + sum {(f1, f) in PAIRS} x[f1, f] == 1;
s.t. Sinks{f in FLIGHTS}:
q[f] + sum {(f, f2) in PAIRS} x[f, f2] == 1;
minimize Airplanes:
sum {f in FLIGHTS} p[f];
Writing fleet_assign.mod
ampl = AMPL()
ampl.read("fleet_assign.mod")
ampl.set["FLIGHTS"] = list(FlightData.index)
ampl.set["PAIRS"] = list(flight_pairs)
ampl.option["solver"] = SOLVER
ampl.solve()
print(f"Minimum airplanes required = {ampl.get_value('Airplanes')}")
x = ampl.get_variable("x").to_dict()
p = ampl.get_variable("p").to_dict()
q = ampl.get_variable("q").to_dict()
HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 14
89 simplex iterations
1 branching nodes
Minimum airplanes required = 14.0
We visualize the solution by redrawing the graph of possible path and highlighting the edges that have been selected for aircraft reassignment.
import networkx as nx
dg_soln = nx.DiGraph()
for flight in FlightData.index:
dg_soln.add_node(flight)
for pair, dur in feasible_flight_pairs(FlightData).items():
if x[pair[0], pair[1]] > 0.5:
dg_soln.add_edge(pair[0], pair[1], color="r" if dur <= min_time else "g")
size = int(1.5 * np.sqrt(len(FlightData)))
fig = plt.figure(figsize=(size, size))
nx.draw_networkx_nodes(dg_soln, pos=pos, node_size=500, alpha=0.8)
nx.draw_networkx_labels(dg_soln, pos=pos, font_color="w")
nx.draw_networkx_edges(
dg_soln,
pos=pos,
width=3,
edge_color=[dg_soln.edges[u, v]["color"] for u, v in dg_soln.edges],
)
nx.draw_networkx_edges(
dg, pos=pos, width=0.5, edge_color=[dg.edges[u, v]["color"] for u, v in dg.edges]
)
nx.draw_networkx_edges(
dg_soln,
pos=pos,
width=3,
edge_color=[dg_soln.edges[u, v]["color"] for u, v in dg_soln.edges],
);
We visualize the solution by drawing arcs where \(x_{f_1, f_2} = 1\) and where \(p_f = 1\) and \(q_f = 1\). These arcs draw feasible paths through the graph corresponding to the assignment of one aircraft to service one or more flights. The arcs are green if the time between the two flights is strictly larger the minimum layover time (1h) and red if it is equal.
ax = draw_flights(FlightData)
for flight1, flight2 in flight_pairs:
if x[flight1, flight2] > 0.5:
arr = FlightData.loc[flight1, "Arrival"]
dep = FlightData.loc[flight2, "Departure"]
c = "r" if dep - arr <= min_time else "g"
ax.plot([arr, dep], [flight1, flight2], color=c, lw=4, alpha=0.4)
for flight in FlightData.index:
if p[flight] > 0.5:
dep = FlightData.loc[flight, "Departure"]
ax.plot([-1, dep], [flight] * 2, "g", lw=4, alpha=0.4)
if q[flight] > 0.5:
arr = FlightData.loc[flight, "Arrival"]
ax.plot([arr, 25], [flight] * 2, "g", lw=4, alpha=0.4)
Create Flight and Aircraft Schedules#
Flight Schedule: A table index by flight numbers showing the assigned aircraft, departure, and arrival times.
Aircraft Schedule: A table indexed by aircraft and flights showing departure and arrival times.
FlightSchedule = FlightData.copy()
# create a generator of aircraft ids
aircraft = (f"A{n+1:02d}" for n in range(len(FlightData.index)))
# traverse each path through the graph
for f in FlightData.index:
if p[f] > 0.5:
id = next(aircraft)
FlightSchedule.loc[f, "Aircraft"] = id
while q[f] < 0.5:
f = next(filter(lambda _: x[f, _] > 0.5, out_nodes[f]))
FlightSchedule.loc[f, "Aircraft"] = id
FlightSchedule = FlightSchedule[["Aircraft", "Departure", "Arrival"]]
display(FlightSchedule)
| Aircraft | Departure | Arrival | |
|---|---|---|---|
| Flight | |||
| 1 | A02 | 13 | 22 |
| 2 | A13 | 14 | 23 |
| 3 | A10 | 10 | 19 |
| 4 | A05 | 10 | 22 |
| 5 | A01 | 1 | 4 |
| 6 | A02 | 0 | 12 |
| 7 | A14 | 11 | 23 |
| 8 | A03 | 2 | 11 |
| 9 | A04 | 3 | 15 |
| 10 | A03 | 12 | 18 |
| 11 | A01 | 6 | 18 |
| 12 | A08 | 10 | 19 |
| 13 | A05 | 0 | 9 |
| 14 | A06 | 14 | 23 |
| 15 | A07 | 8 | 14 |
| 16 | A04 | 16 | 19 |
| 17 | A08 | 5 | 8 |
| 18 | A09 | 7 | 13 |
| 19 | A12 | 13 | 19 |
| 20 | A10 | 5 | 8 |
| 21 | A11 | 15 | 21 |
| 22 | A11 | 11 | 14 |
| 23 | A12 | 3 | 6 |
| 24 | A07 | 15 | 18 |
| 25 | A13 | 4 | 10 |
| 26 | A07 | 19 | 22 |
| 27 | A03 | 20 | 23 |
| 28 | A09 | 17 | 20 |
| 29 | A14 | 6 | 9 |
| 30 | A12 | 7 | 10 |
AircraftSchedule = FlightSchedule.copy()
AircraftSchedule["Flight"] = AircraftSchedule.index
AircraftSchedule = AircraftSchedule.sort_values(["Aircraft", "Departure"])
AircraftSchedule.index = pd.MultiIndex.from_frame(
AircraftSchedule[["Aircraft", "Flight"]]
)
AircraftSchedule = AircraftSchedule[["Departure", "Arrival"]]
display(AircraftSchedule)
| Departure | Arrival | ||
|---|---|---|---|
| Aircraft | Flight | ||
| A01 | 5 | 1 | 4 |
| 11 | 6 | 18 | |
| A02 | 6 | 0 | 12 |
| 1 | 13 | 22 | |
| A03 | 8 | 2 | 11 |
| 10 | 12 | 18 | |
| 27 | 20 | 23 | |
| A04 | 9 | 3 | 15 |
| 16 | 16 | 19 | |
| A05 | 13 | 0 | 9 |
| 4 | 10 | 22 | |
| A06 | 14 | 14 | 23 |
| A07 | 15 | 8 | 14 |
| 24 | 15 | 18 | |
| 26 | 19 | 22 | |
| A08 | 17 | 5 | 8 |
| 12 | 10 | 19 | |
| A09 | 18 | 7 | 13 |
| 28 | 17 | 20 | |
| A10 | 20 | 5 | 8 |
| 3 | 10 | 19 | |
| A11 | 22 | 11 | 14 |
| 21 | 15 | 21 | |
| A12 | 23 | 3 | 6 |
| 30 | 7 | 10 | |
| 19 | 13 | 19 | |
| A13 | 25 | 4 | 10 |
| 2 | 14 | 23 | |
| A14 | 29 | 6 | 9 |
| 7 | 11 | 23 |
Reducing riskiness of the schedule#
We will now keep the maximum number of flights at the optimal level, but try to minimize their riskiness. To do so, we define a slightly different MILP that takes the minimum number of planes nplanes in input and has the total number of risky pairs as objective function.
%%writefile fleet_assign_minrisk.mod
set FLIGHTS;
set PAIRS in {FLIGHTS, FLIGHTS};
param N_planes;
param weight{PAIRS};
var x{PAIRS} binary;
var p{FLIGHTS} binary;
var q{FLIGHTS} binary;
s.t. Sources{f in FLIGHTS}:
p[f] + sum {(f1, f) in PAIRS} x[f1, f] == 1;
s.t. Sinks{f in FLIGHTS}:
q[f] + sum {(f, f2) in PAIRS} x[f, f2] == 1;
s.t. MinAirplanes:
sum {f in FLIGHTS} p[f] <= N_planes;
minimize Risk:
sum {(f1, f2) in PAIRS} weight[f1, f2] * x[f1, f2];
Overwriting fleet_assign_minrisk.mod
def schedule(FlightData, N_planes, min_time=1):
pairs = feasible_flight_pairs(FlightData, min_time)
weights = {pair: int(pairs[pair] <= min_time) for pair in pairs}
ampl = AMPL()
ampl.read("fleet_assign_minrisk.mod")
ampl.set["FLIGHTS"] = list(FlightData.index)
ampl.set["PAIRS"] = list(pairs.keys())
ampl.param["N_planes"] = N_planes
ampl.param["weight"] = weights
ampl.option["solver"] = SOLVER
ampl.solve()
x = ampl.get_variable("x").to_dict()
p = ampl.get_variable("p").to_dict()
q = ampl.get_variable("q").to_dict()
ax = draw_flights(FlightData)
for flight1, flight2 in pairs.keys():
if x[flight1, flight2] > 0.5:
arr = FlightData.loc[flight1, "Arrival"]
dep = FlightData.loc[flight2, "Departure"]
c = "r" if dep - arr <= min_time else "g"
ax.plot([arr, dep], [flight1, flight2], color=c, lw=4, alpha=0.4)
for flight in FlightData.index:
if p[flight] > 0.5:
dep = FlightData.loc[flight, "Departure"]
ax.plot([-1, dep], [flight] * 2, "g", lw=4, alpha=0.4)
if q[flight] > 0.5:
arr = FlightData.loc[flight, "Arrival"]
ax.plot([arr, 25], [flight] * 2, "g", lw=4, alpha=0.4)
return ampl
m = schedule(FlightData, N_planes=14, min_time=1)
HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 2
48 simplex iterations
1 branching nodes
m = schedule(FlightData, N_planes=15, min_time=1)
HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 0
45 simplex iterations
1 branching nodes
m = schedule(FlightData, N_planes=15, min_time=2)
HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 3
52 simplex iterations
1 branching nodes
