View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from

4.7 | 6 ratings Rate this file 23 Downloads (last 30 days) File Size: 20.1 KB File ID: #35178 Version: 1.1
image thumbnail



Jonas Lundgren (view profile)


22 Feb 2012 (Updated )

Heuristic method for the Traveling Salesman Problem (TSP)

| Watch this File

File Information

A number of nearest neighbour tours are generated from randomly selected starting points. Each tour is improved by 2-opt heuristics (pairwise exchange of edges) and the best result is selected.

MATLAB release MATLAB 7.11 (R2010b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (9)
19 Dec 2016 zhu jinxiang

20 Jan 2016 Michael Schroer

It's amazing how much more efficient this code is than the other algorithms on the File exchange I've seen. Very nice piece of code.

Also, for the lucky among us who have access to the parallel computing toolbox, a few small changes to the code allow the use of parfor in the bottleneck loop:

% par for loop
Lvals = inf*ones(m,1);
pvals = zeros(m,n);
parfor k = 1:m
% Nearest neighbour tour
p = greedy(s(k),D);
% Improve tour by 2-opt heuristics
[p,L] = exchange2(p,D);
% Keep best tour
Lvals(k) = L;
pvals(k,:) = p;
Lmin = min(Lvals);
pmin = pvals(Lvals==Lmin,:);

I don't fully understand how this gives me the speedup that it does, but I ran this for a particular problem of interest to me with 256 points. The standard code ran in 147 seconds, and the parfor loop (on my 12 core Xeon) ran in 0.87 seconds!

24 Sep 2013 Mark

Mark (view profile)

What is wrong with the sample code provided by Francesco? It works fine for me. He even gave you links to the mat files he was using.

Comment only
23 Sep 2013 abhishek

Can anybody mail me exactly working program because whenever i try to run this code it shows some error like,
"Input argument "X" is undefined" and
"Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit. Be aware that exceeding your available stack space can
crash MATLAB and/or your computer"

Please help me.. i urgently require this program so please somebody mail me or tell me how to remove these errors..
my mail id is
thanking you!!!

Comment only
10 Jul 2013 Mark

Mark (view profile)

Seems to be an issue with the heuristic and my specific set of "cities". I tried it with uniformly distributed cities in a square area and it seems to behave well. I wish I could remove my previous rating....

10 Jul 2013 Liber Eleutherios

Hi Mark, Jonas's is a heuristic method and it provides random results. But the speed of the algorithm and the efficiency of the path found are amazing compared to other alternatives currently submitted to File Exchange.
Try this simple example:

% Generate a 2D Random Walk with unitary step
N = 1000; % number of nodes
xy = randn(1, 2); % 2D coordinates of nodes
xy(N, 2) = 0;
for hh = 2:N
tmp = randn(2, 1);
tmp = tmp / sqrt(sum(tmp.^2));
xy(hh, 1) = xy(hh - 1, 1) + tmp(1);
xy(hh, 2) = xy(hh - 1, 2) + tmp(2);

% Calculate matrix of distances with function distmat from FE#15145
distM = distmat(xy);

% Solve TSP problem with tspsearch
tic, [TSP_2OPT_P TSP_2OPT_C] = tspsearch(distM); toc
% Elapsed time is 9.769581 seconds.
% Show total distance / total cost
% TSP_2OPT_C = 5.603308638831134e+002

% Have a look at the path: impressive!
plot(xy(:, 1), xy(:, 2), '.b')
for hh = 1:N-1
hold on
plot(xy(TSP_2OPT_P(hh:hh+1), 1), xy(TSP_2OPT_P(hh:hh+1), 2), '-r')
plot(xy(TSP_2OPT_P([1 N]), 1), xy(TSP_2OPT_P([1 N]), 2), '-r')

% Now solve TSP problem using Yonathan Nativ's FE#24857 function - which is also very good:
tic, [xy_tsp ind_tsp] = solveTSP(xy, 0); toc
% Elapsed time is 9.771463 seconds.
min_cost = distM(ind_tsp(1), ind_tsp(end)) + sum(distM(sub2ind([N, N], ind_tsp(1:end-1), ind_tsp(2:end))))
% min_cost = 5.949210148822580e+002

% Have a look at the path: it's still very efficient! Only the last connection is unreasonable:
plot(xy(:, 1), xy(:, 2), '.b')
for hh = 1:N-1
hold on
plot(xy(ind_tsp(hh:hh+1), 1), xy(ind_tsp(hh:hh+1), 2), '-r')
plot(xy(ind_tsp([1 N]), 1), xy(ind_tsp([1 N]), 2), '-r')

Comment only
08 Jul 2013 Mark

Mark (view profile)

Is it just me, or does the algorithm seem to hang randomly once you go past ~350 points???

28 May 2013 Liber Eleutherios

Best TSP engine on FE - much better than Yonathan Nativ's FE#24857 (which is now my second best).

21 Nov 2012 Emmanuel Luevano

Hey dude, It's a good job, easy to apply and very fast!!

23 Feb 2012 1.1

Some examples added

Contact us