# Crew Assignment Problem - Airline

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

Best-ride airlines that operates seven days a week has the following time-table.

Use Horizontal Scrollbar to View Full Table.

Flight No. Delhi - Mumbai
Departure Arrival
1 7.00 AM 8.00 AM
2 8.00 AM 9.00 AM
3 1.00 PM 2.00 PM
4 6.00 PM 7.00 PM
Flight No. Mumbai-Delhi
Departure Arrival
101 8.00 AM 9.00 AM
102 9.00 AM 10.00 AM
103 12.00 Noon 1.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 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

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

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

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.