Dr.PandaIn this video, I’m going to show you how to solve travelling salesman problem (or TSP) using optimization solver in Matlab.
As we know, TSP is one of the famous optimization problems in which we need to find the shortest closed tour (called path) through a set of stops (or cities).
In this video, I use several instances with different numbers of cities (ranging from 20 to 140 cities) to demonstrate the capability of optimization solver in Matlab. Let’s see.
For more videos like this, check my YouTube channel here.
MATLAB CODE
clc
close all
clear all
%Original code source: https://www.mathworks.com/help/optim/ug/travelling-salesman-problem.html
figure;
load('usborder.mat','x','y','xx','yy');
rng(3,'twister') % makes a plot with stops in Maine & Florida, and is reproducible
nStops = 140; % you can use any number, but the problem size scales as N^2
fprintf('Number of cities in this instance: %d\n',nStops);
stopsLon = zeros(nStops,1); % allocate x-coordinates of nStops
stopsLat = stopsLon; % allocate y-coordinates
n = 1;
while (n <= nStops)
xp = rand*1.5;
yp = rand;
if inpolygon(xp,yp,x,y) % test if inside the border
stopsLon(n) = xp;
stopsLat(n) = yp;
n = n+1;
end
end
plot(x,y,'Color','red'); % draw the outside border
hold on
% Add the stops to the map
plot(stopsLon,stopsLat,'*b')
idxs = nchoosek(1:nStops,2);
dist = hypot(stopsLat(idxs(:,1)) - stopsLat(idxs(:,2)), ...
stopsLon(idxs(:,1)) - stopsLon(idxs(:,2)));
lendist = length(dist);
Aeq = spones(1:length(idxs)); % Adds up the number of trips
beq = nStops;
Aeq = [Aeq;spalloc(nStops,length(idxs),nStops*(nStops-1))]; % allocate a sparse matrix
for ii = 1:nStops
whichIdxs = (idxs == ii); % find the trips that include stop ii
whichIdxs = sparse(sum(whichIdxs,2)); % include trips where ii is at either end
Aeq(ii+1,:) = whichIdxs'; % include in the constraint matrix
end
beq = [beq; 2*ones(nStops,1)];
intcon = 1:lendist;
lb = zeros(lendist,1);
ub = ones(lendist,1);
opts = optimoptions('intlinprog','Display','off');
[x_tsp,costopt,exitflag,output] = intlinprog(dist,intcon,[],[],Aeq,beq,lb,ub,opts);
segments = find(x_tsp); % Get indices of lines on optimal path
lh = zeros(nStops,1); % Use to store handles to lines on plot
lh = updateSalesmanPlot(lh,x_tsp,idxs,stopsLon,stopsLat);
tours = detectSubtours(x_tsp,idxs);
numtours = length(tours); % number of subtours
%fprintf('# of subtours: %d\n',numtours);
A = spalloc(0,lendist,0); % Allocate a sparse linear inequality constraint matrix
b = [];
while numtours > 1 % repeat until there is just one subtour
% Add the subtour constraints
b = [b;zeros(numtours,1)]; % allocate b
A = [A;spalloc(numtours,lendist,nStops)]; % a guess at how many nonzeros to allocate
for ii = 1:numtours
rowIdx = size(A,1)+1; % Counter for indexing
subTourIdx = tours{ii}; % Extract the current subtour
% The next lines find all of the variables associated with the
% particular subtour, then add an inequality constraint to prohibit
% that subtour and all subtours that use those stops.
variations = nchoosek(1:length(subTourIdx),2);
for jj = 1:length(variations)
whichVar = and((sum(idxs==subTourIdx(variations(jj,1)),2)),(sum(idxs==subTourIdx(variations(jj,2)),2)));
A(rowIdx,whichVar) = 1;
end
b(rowIdx) = length(subTourIdx)-1; % One less trip than subtour stops
end
% Try to optimize again
[x_tsp,costopt,exitflag,output] = intlinprog(dist,intcon,A,b,Aeq,beq,lb,ub,opts);
% Visualize result
lh = updateSalesmanPlot(lh,x_tsp,idxs,stopsLon,stopsLat);
% How many subtours this time?
tours = detectSubtours(x_tsp,idxs);
numtours = length(tours); % number of subtours
end
title('Final solution');
hold off
fprintf('The solution gap = ')
disp(output.absolutegap)
fprintf('Note: If the solution gap = 0, the global optimal solution is found')
P/s: If you find the post useful, share it to remember and to help other people as well.
Please explain MATLAB code for Travelling Salesperson Problem
Sorry, it’s too lengthy to explain the code line by line.
I get this mistake. Please can you help me?
Undefined function or variable ‘updateSalesmanPlot’.
Error in IP (line 47)
lh = updateSalesmanPlot(lh,x_tsp,idxs,stopsLon,stopsLat);
Please check the function: ‘updateSalesmanPlot’
hi, I got the same error. How can I solve it? Could you explain it?
what was the error?
‘updateSalesmanPlot’ is not found in the current folder or on the MATLAB path, but exists in:
C:\Users\maglor\Documents\MATLAB\Examples\optim\TravelingSalesmanProblemExample
Change the MATLAB current folder or add its folder to the MATLAB path.
Error in Untitled (line 47)
lh = updateSalesmanPlot(lh,x_tsp,idxs,stopsLon,stopsLat);
So I changed folder path and now I got this error below;
Attempt to execute SCRIPT updateSalesmanPlot as a function:
C:\Users\maglor\Desktop\updateSalesmanPlot.m
Error in updateSalesmanPlot (line 47)
lh = updateSalesmanPlot(lh,x_tsp,idxs,stopsLon,stopsLat);
should I make a new script ?
What is your version of Matlab. I used 2016a version of Matlab
Error using updateSalesmanPlot
Too many input arguments.
Error in updateSalesmanPlot1 (line 47)
lh = updateSalesmanPlot(lh,x_tsp,idxs,stopsLon,stopsLat);
Would I create a function as “updateSalesmanPlot” ?
sir do you have code for “parcel delivery using multi trucks and multi drones? “
Hi, I don’t have that code. I suggest you to customize my existing codes to solve the problems in your fields. Good luck!
Hello, how can I customize this code by providing the information about the longitude and latitude for each cities that I want to use? thankyou.
Here is how to update the city locations: https://learnwithpanda.com/2021/01/17/python-code-of-the-2-opt-algorithm-for-solving-the-traveling-salesman-problems/
Thank you. Very helpful video. Unfortunately, I did not receive any confirmation mail. What should I do?
Thanks again
Maybe, the email was in the spam folder
Thanks, received after two hours. You are very helpful
pls I need the code
Hi, this is optimization solver in Matlab. Just install matlab version 2016a and then you will get it.
HI, I found a problem in line 43
Error using optimoptions (line 124)
Invalid solver specified. Provide a solver name or handle
(such as ‘fmincon’ or @fminunc).
Type DOC OPTIMOPTIONS for a list of solvers.
Error in Untitled3 (line 43)
opts = optimoptions(‘intlinprog’,’Display’,’off’);
Your matlab version does not have optimization toolbox. I used matlab version 2016a
Hello, I am wondering what code should I add so I can see the total distance of the final optimize path? Is it just
fprintf(‘Total Distance Travel: %d\n’,lendist)?
The total distance is shown in the command window