Assignment Problem

Travelling Salesman Problem

This humorously named problem refers to the following situation:
A travelling salesman, named Rover plans to visit each of n cities. He wishes to visit each city once and only once, arriving back to city from where he started. The distance between City i and City j is c_ij. What is the shortest tour Rover can take?

If there are n cities, there are (n - 1)! possible ways for his tour. For example, if the number of cities to be visited is 5, then there are 4! different combinations. Such type of problems can be solved by the assignment method.
Let c_ij be the distance (or cost or time) between City i to City j and

The following example will help you in understanding the travelling salesman problem.

Example

A travelling salesman, named Rolling Stone plans to visit five cities 1, 2, 3, 4 & 5. The travel time (in hours) between these cities is shown below:

How should Mr. Rolling Stone schedule his touring plan in order to minimize the total travel time, if he visits each city once a week?

"As every thread of gold is valuable, so is every minute of time." - John Mason

Solution

After applying steps 1 to 3 of the Hungarian method, we get the following assignments.

Table

To
From	1	2	3	4	5
1	µ	1	3		1
2	1	µ	2		1
3	2	1	µ	2
4			3	µ	4
5				3	µ

Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix.

Table

Select the smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment. Repeating step 3 on the reduced matrix, we get the following assignments.

Table

To
From	1	2	3	4	5
1	µ		2		1
2		µ	1		1
3	1		µ	2
4			3	µ	5
5				4	µ

The above solution suggests that the salesman should go from city 1 to city 4, city 4 to city 2, and then city 2 to 1 (original starting point). The above solution is not a solution to the travelling salesman problem as he visits city 1 twice.

The next best solution can be obtained by bringing the minimum non-zero element, i.e., 1 into the solution. Please note that the value 1 occurs at four places. We will consider all the cases separately until the acceptable solution is obtained. To make the assignment in the cell (2, 3), delete the row & the column containing this cell so that no other assignment can be made in the second row and third column.

Now, make the assignments in the usual manner as shown in the following table.

Table

He starts from city 1 and goes to city 4; from city 4 to city 2; from city 2 to city 3; from city 3 to city 5; from city 5 to city 1.

Substituting values from original table:
4 + 7 + 6+ 4 + 5 = 26 hours.

In this chapter, we focussed on a special type of transportation problem where the objective was to allocate n different facilities to n different tasks. Although an assignment problem can be formulated as a linear programming problem, it is solved by a special method known as Hungarian Method. If the number of persons is the same as the number of jobs, the assignment problem is said to be balanced. If the number of jobs is different from the number of persons, the assignment problem is said to be unbalanced. Some assignment problems entail maximizing the profit, effectiveness, or layoff of an assignment of persons to tasks or of jobs to machines. The Hungarian Method can also solve such problems. Further, the Hungarian method can also be utilized for solving crew assignment problem and the travelling salesman problem.