Air Crew Assignment Problem Hungarian
The Hungarian method discussed in the previous sections can also be utilized to plan the assignment of crew members at different locations by a transport company.
To further enhance your understanding about assignment models, we provide the following examples of crew assignment problem.
Example: Crew Assignment Problem
Bestride airlines that operates seven days a week has the following timetable.
Use Horizontal Scrollbar to View Full Table.


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 No.  101  102  103  104 
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
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
Oh God! It's so lengthy and boring
"Everything becomes interesting when the doer cares about doing it right, or doing it better."  Vinay Chhabra & Manish Dewan.
Repeating the same procedure, we get the following matrix.
Table 7
The optimal solution is 21 + 8 + 18 + 5 = 52 hours.
Leave a Comment
(0 Comments)