Fast 2-Opt Travelling Salesman Problem (TSP)

Fast and simple TSP algorithm using 2-opt heuristics for symmetric and non-symmetric problems.

Description

tsp2opt finds a solution to the symmetric and non-symmetric Travelling Salesman Problem (TSP) using the 2-opt heuristic algorithm. It attempts to find the shortest (or longest) possible route that visits each city exactly once.

The function can handle multidimensional coordinates and includes options for setting the number of iterations and cycles. By providing an arbitrary last argument, the function can be instructed to find the maximum length path instead of the shortest.

If the start or endpoints had to be preserved, the function includes the comments for its implementation.

Syntax

[path, dist] = tsp2opt(x)

[path, dist] = tsp2opt(x, iter)

[path, dist] = tsp2opt(x, iter, ~)

Inputs

• x: An N-by-M matrix representing the coordinates of N-nodes (cities) in M-dimensions.
• iter (optional): Iteration count, specified as a scalar or a vector. If scalar, it represents the number of iterations. If vector, the first element specifies the number of attempts. If (any) negative, the non-symmetric TSP is solved. Default: max(10, ceil(n/10))
• N/A (optional): If passed, flag to query for the longest possible route. Default: none

Outputs

• path: A vector containing the indices of the nodes in the order they are visited in the optimized path.
• dist: The total distance of the computed path.

Examples

% Initialize input data
col = [0, 114, 189; 217, 83, 25; 237, 177, 32; 126, 47, 142; ...
    119, 172, 48; 77, 190, 238; 162, 20, 47] / 255;
x = rand(100,2);


% EXAMPLE 1: Validate different input types
rng('default'), [path1, dist1] = tsp2opt(x);
rng('default'), [path2, dist2] = tsp2opt(pdist2(x,x));
if isequal(path1, path2)
    fprintf('SUCCESS: different input types match.\n')
else
    fprintf('ERROR: different inputs do not match.\n')
end


% EXAMPLE 2: Optimized search with cycles/iter.
[path3, dist3] = tsp2opt(x, 5);
[path4, dist4] = tsp2opt(x, [10,100]);
figure, plot(x(path3,1), x(path3,2), 'o:')
hold on, plot(x(path4,1), x(path4,2),'LineWidth',1)
title 'Optimized TSP search'


% EXAMPLE 3: Color sorting for contrast
figure, tiledlayout(3,1), nexttile(1)
imshow(reshape(col, 1, [], 3), 'InitialMagnification', 'fit')
title 'Original color array'
idx = tsp2opt(col); idx = idx(1:end-1); nexttile(2)
imshow(reshape(col(idx,:), 1, [], 3), 'InitialMagnification', 'fit')
title 'Minimum contrast sorting'
idx = tsp2opt(col, [], 'long'); idx = idx(1:end-1); nexttile(3)
imshow(reshape(col(idx,:), 1, [], 3), 'InitialMagnification', 'fit')
title 'Maximum contrast sorting'


% EXAMPLE 4: different types of TSP
idx = tsp2opt(x(1:10,:), 10); figure, plot(x(idx,1), x(idx,2), 'o-')
idx = tsp2opt(x(1:10,:), -10); hold on, plot(x(idx,1) + 1, x(idx,2), 'o-')
title 'Symmetric and non-symmetric problem', pbaspect([2,1,1])