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.
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
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
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.
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
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
Quantitative Techniques for management Related Tutorials
|Business Analyst Tutorial||Project Management Tutorial|
|Business Environment Tutorial||Marketing Research Tutorial|
|Business Management for Financial Advisers Tutorial||Research Methodology Tutorial|
|Business Ethics Tutorial||International Business Management Tutorial|
Quantitative Techniques for management Related Interview Questions
|Business Analyst Interview Questions||Project Management Interview Questions|
|Business Environment Interview Questions||Marketing Research Interview Questions|
|Business Management for Financial Advisers Interview Questions||Research Methodology Interview Questions|
|Business Ethics Interview Questions||Business Management Interview Questions|
|International Business Management Interview Questions|
Quantitative Techniques for management Related Practice Tests
|Business Analyst Practice Tests||Project Management Practice Tests|
|Business Environment Practice Tests||Marketing Research Practice Tests|
|Business Management for Financial Advisers Practice Tests||Research Methodology Practice Tests|
|Business Ethics Practice Tests||Business Management Practice Tests|
Quantitative Techniques For Management Tutorial
Quantitative Techniques – Introduction
Measures Of Central Tendency
Linear Programming: Graphical Method
Linear Programming: Simplex Method
Waiting Model (queuing Theory)
Theoretical Probability Distributions
Probability Distribution Of A Random Variable
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.