Travelling salesman problem - Detecting subtour

2 vues (au cours des 30 derniers jours)
Anjaneya Tiwari
Anjaneya Tiwari le 1 Mai 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

Réponses (1)

Alan Weiss
Alan Weiss le 1 Mai 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

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by