Home > Operation Research calculators > Travelling salesman problem using diagonal completion method example

6. Travelling salesman problem using diagonal completion method example ( Enter your problem )
  1. Example-1
  2. Example-2
Other related methods
  1. Assignment problem using Hungarian method
  2. Travelling salesman problem using Hungarian method
  3. Travelling salesman branch and bound (penalty) method
  4. Travelling salesman branch and bound method
  5. Travelling salesman nearest neighbor method
  6. Travelling salesman diagonal completion method
  7. Crew assignment problem

1. Example-1
(Previous example)
7. Crew assignment problem
(Next method)

2. Example-2





Find Solution of Travelling salesman problem using diagonal completion method (MIN case)
Work\JobABCDE
Ax2571
B6x382
C87x47
D1246x5
E1328x


Solution:
The number of rows = 5 and columns = 5
   `A`  `B`  `C`  `D`  `E`    
 `A` M2571
 `B` 6M382
 `C` 87M47
 `D` 1246M5
 `E` 1328M
   



Step-1: Find out the each row minimum element and subtract it from that row
   `1`  `2`  `3`  `4`  `5`    
 `1` M1460(-1)
 `2` 4M160(-2)
 `3` 43M03(-4)
 `4` 802M1(-4)
 `5` 0217M(-1)
   


Step-2: Find out the each column minimum element and subtract it from that column.
   `1`  `2`  `3`  `4`  `5`    
 `1` M1360
 `2` 4M060
 `3` 43M03
 `4` 801M1
 `5` 0207M
   (-0)(-0)(-1)(-0)(-0)


Step-3: Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
   `1`  `2`  `3`  `4`  `5`    
 `1` `M``1``3``6``0^(color{red}{(1)})`
 `2` `4``M``0^(color{red}{(0)})``6``0^(color{red}{(0)})`
 `3` `4``3``M``0^(color{red}{(9)})``3`
 `4` `8``0^(color{red}{(2)})``1``M``1`
 `5` `0^(color{red}{(4)})``2``0^(color{red}{(0)})``7``M`
   


Step-4: List the penalties `P(i,j)` in descending order by value.

`P(3,4)=9`

`P(5,1)=4`

`P(4,2)=2`

`P(1,5)=1`

`P(2,3)=0`

`P(2,5)=0`

`P(5,3)=0`

Step-5: The links `(3,4),(5,1),(4,2),(2,3)` are selected for inclusion in the feasible partial tour.

Step-6: Feasible partial tour contains the following chains
`3->4->2,5->1`

`(2,3),(1,5)` can not be selected, because they are the closing links and create prohibited subtours.

Step-7: The new submatrix is :
   `3`  `5`    
 `2` M2
 `1` 5M
   



Repeat from step-1 to step-7
Step-1: Find out the each row minimum element and subtract it from that row
   `3`  `5`    
 `2` M0(-2)
 `1` 0M(-5)
   


Step-3: Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
   `3`  `5`    
 `2` `M``0^(color{red}{(0)})`
 `1` `0^(color{red}{(0)})``M`
   


Step-4: List the penalties `P(i,j)` in descending order by value.

`P(2,5)=0`

`P(1,3)=0`

Step-5: The links `(2,5),(1,3)` are selected for inclusion in the feasible partial tour.

Step-6: Feasible partial tour contains the following chains
`3->4->2->5->1->3`

So our final path is `C->D->B->E->A->C`

and total distance is `4+4+2+1+5=16`


This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here



1. Example-1
(Previous example)
7. Crew assignment problem
(Next method)





Share this solution or page with your friends.


 
Copyright © 2023. All rights reserved. Terms, Privacy
 
 

.