| Description |
TSP_NN Traveling Salesman Problem (TSP) Nearest Neighbor (NN) Algorithm
The Nearest Neighbor algorithm produces different results depending on which city is selected as the starting point. This function determines the Nearest Neighbor routes for multiple starting points and returns the best of those routes
Summary:
1. A single salesman travels to each of the cities and completes the route by returning to the city he started from
2. Each city is visited by the salesman exactly once
Input:
XY (float) is an Nx2 (or Nx3) matrix of cities
DMAT (float) is an NxN matrix of point to point distances/costs
POPSIZE (scalar integer) is the size of the population (should be <= N)
SHOWPROG (scalar logical) shows the GA progress if true
SHOWRESULT (scalar logical) shows the GA results if true
Output:
OPTRTE (integer array) is the best route found by the algorithm
MINDIST (scalar float) is the cost of the best route
Example:
n = 50;
xy = 10*rand(n,2);
popSize = n;
showProg = 1;
showResult = 1;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
[optRoute,minDist] = tsp_nn(xy,dmat,popSize,showProg,showResult);
Example:
n = 100;
phi = (sqrt(5)-1)/2;
theta = 2*pi*phi*(0:n-1);
rho = (1:n).^phi;
[x,y] = pol2cart(theta(:),rho(:));
xy = 10*([x y]-min([x;y]))/(max([x;y])-min([x;y]));
popSize = n;
showProg = 1;
showResult = 1;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
[optRoute,minDist] = tsp_nn(xy,dmat,popSize,showProg,showResult);
Example:
n = 50;
xyz = 10*rand(n,3);
popSize = n;
showProg = 1;
showResult = 1;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);
[optRoute,minDist] = tsp_nn(xyz,dmat,popSize,showProg,showResult); |
