Assignment Problem

An Application - Airline Crew Assignment

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.

Example

Best-ride airlines that operates seven days a week has the following time-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

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

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

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.