3. Composing flight crews
Ardous
Description
During the Second World War the Royal Air Force (RAF) had many foreign pilots speaking different
languages and more or less trained on the different types of aircraft. The RAF had to form pilot/co-pilot
pairs (crews) for every plane with a compatible language and a sufficiently good knowledge of the
aircraft type. In our example there are eight pilots. In the following table every pilot is characterized by
a mark between 0 (worst) and 20 (best) for his language skills (in English, French, Dutch, and Norwegian),
and for his experience with different two-seater aircraft (reconnaissance, transport, bomber, fighterbomber, and supply planes).
| Pilot | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| Language | English | 20 | 14 | 0 | 13 | 0 | 0 | 8 | 8 |
| French | 12 | 0 | 0 | 10 | 15 | 20 | 8 | 9 | |
| Dutch | 0 | 20 | 12 | 0 | 8 | 11 | 14 | 12 | |
| Norwegian | 0 | 0 | 0 | 0 | 17 | 0 | 0 | 16 | |
| Plane type | Reconnaissance | 1 | 8 | 12 | 5 | 0 | 0 | 8 | 0 |
| Transport | 10 | 0 | 9 | 14 | 15 | 8 | 12 | 13 | |
| Bomber | 0 | 17 | 0 | 11 | 13 | 10 | 0 | 0 | |
| Fighter Bomber | 0 | 0 | 14 | 0 | 0 | 12 | 16 | 0 | |
| Supply plane | 0 | 0 | 0 | 0 | 12 | 18 | 0 | 18 |
Table 3.1 Ratings of pilots
A valid flight crew consists of two pilots that both have each at least 10/20 for the same language and
10/20 on the same aircraft type.
Question 1: Is it possible to have all pilots fly?
Subsequently, we calculate for every valid flight crew the sum of their scores for every aircraft type for which both pilots are rated at least 10/20. This allows us to define for every crew the maximum score among these marks. For example, pilots 5 and 6 have marks 13 and 10 on bombers and 12 and 18 on supply planes. The score for this crew is therefore max(13 + 10, 12 + 18) = 30.
Question 2: Which is the set of crews with maximum total score?
🚀 Test your code
Try to solve the problem below in the code editor before reading the solution.
Answer
View Answer
Results
In answer to the first question, the program finds that four crews are flying, that is, all eight pilots.
For the second question, the optimization calculates a maximum total score of \(125\) for the four crews \([1,2]\), \([3,7]\), \([4,5]\), and \([6,8]\).
Figure 3.1:Compatibility graph for pilots
Explanation
Let \(PILOTS\) be the set of pilots. This type of problem is easily modeled through an undirected compatibility graph \(G = (PILOTS, ARCS)\). Every node represents a pilot, two nodes \(\textit{p}\) and \(\textit{q}\) are connected by an undirected arc (or edge) \(a = [\textit{p}, \textit{q}]\) if and only if pilots \(\textit{p}\) and \(\textit{q}\) are compatible, that is, they have a language and a plane type in common for which both are rated at least 10/20.
The arcs are assigned weights corresponding to the maximum score \(SCORE_a\) of the flight crew. Figure 3.1 shows the resulting graph with the scores for question 2. A valid set of crews corresponds in \(G\) to a subset of arcs such that any two among them have no node in common. In Graph Theory, such a set is called a matching. For question 1 we are looking for the maximum cardinality matching, for question 2 for the matching with maximum total weight. The graph suggests we formulate the model as follows.
Model Formulation
For every edge \(a = [\textit{p}, \textit{q}]\) in the graph, a binary variable \(fly_a\) indicates whether this edge is used or not (3.3). Through constraints (3.2) every node r is contained in at most one edge. The objective function (3.1) accumulates the weight of the chosen edges for question 2.
For question 1, we maximize the number of flight crews to see whether all pilots are taken: the coefficients \(SCORE_a\) need to be removed from the objective function. Note that the matching of maximum cardinality is a special case of matching with maximum weight, with all weights equal to 1.
Solutions
import gurobipy as gp
from gurobipy import GRB
Pilot,Eng,Fre,Dut,Nor,Reco,Tran,Bomb,Figh,Supp = gp.multidict(
{
1: [20,12, 0,0 ,18,0 ,0 ,0 ,0 ],
2: [14,0 ,20,0 ,12,17,17,0 ,0 ],
3: [0 ,0 ,12,0 ,15,0 ,0 ,14,0 ],
4: [13,10,0 ,0 ,0 ,11,11,0 ,0 ],
5: [0 ,15,8 ,17,0 ,13,13,0 ,12],
6: [0 ,20,11,0 ,0 ,10,10,12,18],
7: [8 ,8 ,14,0 ,8 ,0 ,0 ,16,0 ],
8: [8 ,9 ,12,16,0 ,0 ,0 ,0 ,18],
}
)
Arcs,scores = gp.multidict({
(1,2): 30,
(2,3): 27,
(2,4): 28,
(2,6): 27,
(3,6): 26,
(3,7): 30,
(4,5): 29,
(4,6): 21,
(5,6): 30,
(5,8): 30,
(6,7): 28,
(6,8): 36,
})
Arcs = gp.tuplelist(Arcs)
m =gp.Model('Composing flight crews')
Z= m.addVar(vtype=GRB.INTEGER,obj=1, name="Z")
x={}
for i, j in Arcs:
x[i,j] = m.addVar(vtype=GRB.BINARY,obj=1, name="x_{}{}".format(i,j))
m.setObjective(Z,GRB.MAXIMIZE)
m.update()
for p in Pilot:
m.addConstr(gp.quicksum(x[i,j] for i,j in Arcs.select(p,'*')) + gp.quicksum(x[j,i] for j,i in Arcs.select('*',p)) <= 1)
m.addConstr((gp.quicksum(x[i,j] for i,j in Arcs))==Z)
m.optimize()
print('Objective Value: %g' % m.objVal)
#Part (b) of problem
crew_score=0
for i, j in Arcs:
if x[i, j].x>0.5:
crew_score+=scores[i,j]*x[i,j].x
print('Arc (%s,%s): %g' % (i, j, scores[i, j]))
print("Crew Score",crew_score)
Access to detailed solutions requires a login. Already have an account? Don't have an account yet?
👋 Please log in to view the solution
Akhil Singh Chauhan
Creator