Crew Assignment Problem: Examples

Let's solve the following problem with the Hungarian Method. We will use the same process as used in the last example.

Example

Universal bus service operates seven days in a week. A trip from Delhi to Rajpura takes six hours by bus. A typical time table of the bus service in both directions is given below:

Use Horizontal Scrollbar to View Full Table.

The cost of providing this service by the transport company depends upon the time spent by the bus crew (driver and conductor) away from their places in addition to service times. There are five crews. There is a constraint that every crew should be provided with more than 4 hours of rest before the return trip and should not wait for more than 24 hours for the return trip. The company has residential facilities for the crew of Delhi as well as of Rajpura. Find which line of service be connected with which other line so as to reduce the waiting time to the minimum.

Solution.

If bus no. A is combined with bus no. 1, the crew after arriving at Rajpura at 12 noon starts at 5.30 next morning. Thus, the waiting time is 17.30 hours as shown in table 1. Some of the assignments are infeasible, e.g., bus no. 3 leaves Rajpura at 15.00 hours. Thus, the crew of bus no. A after reaching Rajpura at 12 noon are unable to take the minimum required rest of four hours, if they are asked to leave by bus no. 3. Hence, A3 is an infeasible assignment. Thus, its cost is M, a large positive number.

Table 1

Similarly, if the crew are assumed to stay at Rajpura, then the waiting times of the crew in hours at Delhi are given in table 2.

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 Delhi, otherwise based at Rajpura.

Table 3

On small screens, scroll horizontally to view full calculation

Table 4

To simplify the problem, we multiply every element of the matrix with 2. Thus, the resulting matrix is:

Now solve the above problem by the Hungarian method.

The optimal solution is 4.30 + 9.30 + 9 + 5 + 5.30 = 33.30 hours