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.
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 abhishekdixit011@gmail.com
thanking you!!!
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....
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);
end
% Calculate matrix of distances with function distmat from FE#15145
% http://www.mathworks.com/matlabcentral/fileexchange/15145-distance-matrix
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
% TSP_2OPT_C = 5.603308638831134e+002
% Have a look at the path: impressive!
figure
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')
pause(0.1)
end
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:
figure
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')
pause(0.1)
end
plot(xy(ind_tsp([1 N]), 1), xy(ind_tsp([1 N]), 2), '-r')