Joy Taxi has four taxi ,1,2,3,4 & there are four customers, P,Q,R,and S requiring taxi. The distance between the taxi customers are given in the table below, in kilometers .The taxi Company wishes to assign the taxis to Customers so that the distance travel ed is minimum through Hungarian Model.

The Hungarian Method based Problem

Step 1 -

• Consider the given Cost Matrix.

Step 2 -

• Checks whether the cost matrix given in the problem is square or not, which means the number of rows is equal to the number of columns.
• If it is so, the assignment problem is said to be balanced; otherwise add dummy rows or columns with cost 0, to make it a square matrix.

Here, The matrix given in the question is a square matrix of order 4 therefore, there is no need to add any extra dummy rows & columns.

Step 3 - Subtract Row Minima -

• Identify the minimum element in each row and subtract it from each element of that row to obtain the next matrix.
• In row 1, the smallest value is 4, in row 2 is 4, in row 3 is 2 and in row 4 is 4.
• The row-wise reduced matrix is shown below.

Step 4 - Subtract Column Minima -

• Identify the minimum element in each column and subtract it from each element of that column to obtain the next matrix.
• In column 1, the smallest value is 0, in column 2 is 0, in column 3 is 0 and in column 4 is 0.
• Since, every column has a small value of 0 therefore, in this example there is no need to do a column-wise reduction matrix.

Now, it is very clear that each row and each column contains exactly one assignment, then the solution is optimal and assignments can be made.

Step 5 -

• Check whether there is at least one zero in each row and each column and make an assignment as follows.
• Starts with examining the rows successively,
  • At Row 1 there is exactly one zero. Mark that zero by the square ([0]). Hence, Taxi 1 is assigned to Customer R. There are no other zeros in its column hence no need to mark a cross (×) anywhere and just draw the Vertical line on that column.
  • At Row 2 there is exactly one zero. Mark that zero by the square ([0]). Hence, Taxi 2 is assigned to Customer Q. There are no other zeros in its column hence no need to mark a cross (×) anywhere and just draw the Vertical line on that column.
  • At Row 3 there is exactly one zero. Mark that zero by the square ([0]). Hence, Taxi 3 is assigned to Customer S. There are no other zeros in its column hence no need to mark a cross (×) anywhere and just draw the Vertical line on that column.
  • At Row 4 there is exactly one zero. Mark that zero by the square ([0]). Hence, Taxi 4 is assigned to Customer P. There are no other zeros in its column hence no need to mark a cross (×) anywhere and just draw the Vertical line on that column.

Now, Number of lines drawn (4) = order of matrix (4), this indicates Optimality is reached,

Step - 6

Taxi 1 is assigned to Customer R = 4 Km

Taxi 2 is assigned to Customer Q = 4 Km

Taxi 3 is assigned to Customer S = 2 Km

Taxi 4 is assigned to Customer P = 4 Km

Therefore, the Minimum Distance Travelled is 14 Km