Mechprof.com

Mechprof.com is The platform to learn Designing, Digital Manufacturing , manufacturing, simulation , CAM , CAD design, operation research, industrial engineering, mechanical tools, design, AutoCAD , Ansys, solidworks.

Recent Updates

Wednesday, May 6, 2020

Travelling Salesman problem

Travelling Salesman problem :-



The objective of the Travelling salesman problem is to find the shortest Distance / Time / Cost.

Conditions :-

➤There are a number of cities a salesman must visit. e.g.- A, B, C & D.
➤The distance , cost / time between two cities is given.
➤The salesman start from his home city he must visit every city exactly at once & return to it's home city.

Algorithm To find the Solution of Travelling Salesman:- Also Known as Hungerian Method:-


PHASE 1 :- Row & Column Reduction.

STEP 1. Subtract the minimum value of each row from the entries of that Row.

STEP 2. Subtract the minimum value of each column from the entries of that column.


PHASE 2 :- Optimization the Problem.

STEP 1. Draw a minimum number of lines to cover all the zeros of the matrix.
PROCEDURE:-
(a) ROW SCANNING:- 

(1) Starting from the first row, ask the following questions , is there exactly one zero in the column, if yes make a square around that entry and draw a Vertical line passing through that zero ; otherwise skip that row.

(2) After scanning the last row , check whether all the zero are covered with lines. if yes, go to step 2, otherwise , do column scanning.

(b) COLUMN SCANNING:-

(1) Starting from the first column , ask the following questions , is there exactly one zero in the column, if yes make a square around that entry and draw a Horizontal line passing through that zero ; otherwise skip that column.

(2)  After scanning the last column , check whether all the zero are covered with lines.

STEP 2. Check whether the No. of square marked is equal to the no. of rows of the matrix. If yes, go to Step 5 ; otherwise go to Step 3.

STEP 3. Identify the minimum value of the undeleted cell values.
(a) Add the minimum undeleted cell value at the intersection points of the present matrix.
(b) Subtract the minimum undeleted cell value from all the undeleted cell value.
(c) All the other entries remains same.

STEP 4. GO to Step 1.

STEP 5. Treat This solution as marked.
the optimality is reached.



Thank you. 

No comments:

Post a Comment

If you have any doubts let me know.