TRAVELLING SALESMAN PROBLEM - Quantitative Techniques for management

Travelling Salesman Problem example in Operation Research

The ‘Travelling salesman problem’ is very similar to the assignment problem except that in the former, there are additional restrictions that a salesman starts from his city, visits each city once and returns to his home city, so that the total distance (cost or time) is minimum.

Procedure:

Step 1: Solve the problem as an assignment problem.
Step 2: Check for a complete cycle or alternative cycles. If the cycle is complete, Go to Step 4. If not, go to the Step 3.
Step 3: To start with, assign the next least element other than zero, (only for first allocation) and complete the assignment. Go to Step 2.
Step 4: Write the optimum assignment schedule and calculate the cost/time.
(Note: If there are two non-zero values in the matrix, it means that there are two optimal
solutions. Calculate the cost for the two allocations and find the optimal solution.)

Example: A Travelling salesman has to visit five cities. He wishes to start from a particular city, visit each city once and then return to his starting point. The travelling cost (in Rs.) of each city from a particular city is given below.

Travelling Salesman Problem

Travelling Salesman Problem

What should be the sequence of the salesman's visit, so that the cost is minimum?
Solution: The problem is solved as an assignment problem using Hungarian method; an optimal solution is reached as shown in Table.

Optimal Solution Reached Using Hungarian Method

Optimal Solution Reached Using Hungarian Method

In this assignment, it means that the travelling salesman will start from city A, then go to city E and return to city A without visiting the other cities. The cycle is not complete. To overcome this situation, the next highest element can be assigned to start with. In this case it is 1, and there are three 1’s. Therefore, consider all these 1’s one by one and find the route which completes the cycle.

Case 1: Make the assignment for the cell (A, B) which has the value 1. Now, make the assignments for zeros in the usual manner. The resulting assignments are shown in table.

Resulting Assignment

Resulting Assignment

The assignment shown in Table 7.42 gives the route sequence
A → B, B → C, C → D, D →E and E → A.
The travelling cost to this solution is
= 2000 + 3000 + 4000 + 5000 + 1000
= Rs.15,000.00

Case 2: If the assignment is made for cell (D, C) instead of (D, E), the feasible solution cannot be obtained. The route for the assignment will be A → B → C → D→ C. In this case, the salesman visits city C twice and cycle is not complete.

Therefore the sequence feasible for this assignment is
A → B → C → D → E → A.
with the travelling cost of Rs.15,000.00

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Quantitative Techniques for management Topics