MATLAB Answers

0

Travelling salesman problem - Detecting subtour

Asked by Anjaneya Tiwari on 1 May 2019
Latest activity Answered by Alan Weiss
on 1 May 2019
I am trying to solve TSP using linear Integer Programming. I am trying to detect subtour to element them. When I solve the optimisation problem, I get a matrix with all the allowable routes as 1. I then multiply this with the distance matrix to get the total distance.
My matrix is very big but a smaller example will be:
As you can see here starting from 1st location, it first goes to 3rd location, then to 2nd location, then to 5th location and back to 1st location. This is one subtour and the second subtour is from 4th location it goes to 6th location and then back to 4th.
I am not sure how to go about coding this subtour such that it finds the smallest subtour and adds the constraint and then rerun the optimisation problem in a loop until there is only 1 subtour left.
Right now I am trying to find column location of 1 in 1st row and then go to row = column and repeat this. But I am not sure how to write this.
Please hlep!
Thanks

  0 Comments

Sign in to comment.

1 Answer

Answer by Alan Weiss
on 1 May 2019

If you have an Optimization Toolbox™ license, take a look at this example, which has code that does what you ask. Access the code by clicking Try This Example on the upper-right.
Alan Weiss
MATLAB mathematical toolbox documentation

  0 Comments

Sign in to comment.