Example: Crew Assignment Problem
An airlines that operates seven days a week has the following time-table.
Flight No. Delhi - Mumbai Flight No. Mumbai-Delhi
Departure Arrival Departure Arrival
1 7.00 AM 8.00 AM 101 8.00 AM 9.00 AM
2 8.00 AM 9.00 AM 102 9.00 AM 10.00 AM
3 1.00 PM 2.00 PM 103 12.00 Noon 1.00 PM
4 6.00 PM 7.00 PM 104 5.00 PM 6.00 PM
Crews must have a minimum layover of 5 hours between flights. Obtain the pairing of
flights that minimizes layover time away from home. For any given pairing, the crew will
be based at the city that results in the smaller layover. For each pair also mention the
city where crew should be based.
Solution
To determine optimal assignments, first we calculate layover times from the above time
table.
Calculating values for table 1 (layover time)
First Row
First cell
Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 8.00 AM
Difference between arrival and departure = 24 hours (layover time)
Second cell
Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 9.00 AM
Difference between arrival and departure = 25 hours (layover time)
Third cell
Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 12.00 Noon
Difference between arrival and departure = 28 hours (layover time)
Fourth cell
Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 5.00 PM
Difference between arrival and departure = 9 hours (layover time)
Similarly, values for other rows can be calculated.
Table 1
Crew based at Delhi
Flight 101 102 103 104
No.
1 24 25 28 9
2 23 24 27 8
3 18 19 22 27
4 13 14 17 22
Calculating values for table 2 (layover time)
First Column
First cell
Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 7.00 AM
Difference = 22 hours
Second cell
Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 8.00 AM
Difference = 23 hours
Third cell
Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 1.00 PM
Difference = 28 hours
Fourth cell
Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 6.00 PM
Difference = 9 hours
Similarly, values for other columns can be calculated.
Table 2
Crew based at Mumbai
Flight No. 101 102 103 104
1 22 21 18 13
2 23 22 19 14
3 28 27 24 19
4 9 8 5 24
The composite layover time matrix (table 3) is obtained by selecting the smaller element
from the two corresponding elements of table 1 & 2. The layover time marked
with ( * )represents that the crew is based at Mumbai, otherwise based at Delhi. For
example, corresponding to flight no.1 and 101 in table 1 & 2, we select the minimum
between (24, 22), i.e., 22 for Mumbai. Therefore, this element is marked with ( * ). In
this way, table 3 is completed and shown below.
Table 3
Flight No. 101 102 103 104
1 22* 21* 18* 9
2 23 22* 19* 8
3 18 19 22 19*
4 9* 8* 5* 22
Now the above problem can be easily solved by Hungarian method. The following
matrix shows the assignments.
Table 4
Flight No. 101 102 103 104
1 13* 11* 9*
2 15 13* 11*
3 4 1*
4 4* 2* * 17
Draw the minimum number of vertical and horizontal lines necessary to cover all the
zeros in the reduced matrix.
Table 5
Select the smallest element from all the uncovered elements, i.e., 9. Subtract this
element from all the uncovered elements and add it to the elements, which lie at the
intersection of two lines. Repeating step 3 of the Hungarian algorithm, we obtain a
solution which is shown in the following table.
Table 6
Flight No. 101 102 103 104
1 4* 2* *
2 6 4* 2*
3 4 10*
4 4* 2* * 26
Table 7
Flight No. 101 102 103 104
1 2* * *
2 4 2* 2*
3 6 12*
4 2* * * 26
The optimal solution is 21 + 8 + 18 + 5 = 52 hours.
