Traveling Salesman Problem - Nearest Neighbor

Finds a near-optimal solution to a TSP using Nearest Neighbor (NN)

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
POP_SIZE (scalar integer) is the size of the population (should be <= N)
SHOW_PROG (scalar logical) shows the GA progress if true
SHOW_RES (scalar logical) shows the GA results if true

Output:
OPT_RTE (integer array) is the best route found by the algorithm
MIN_DIST (scalar float) is the cost of the best route

Example:
n = 50;
xy = 10*rand(n,2);
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
pop_size = n;
show_prog = 1;
show_res = 1;
[opt_rte,min_dist] = tsp_nn(xy,dmat,pop_size,show_prog,show_res);

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Traveling Salesman Problem - Genetic Algorithm

• MATLAB release: MATLAB 7.6 (R2008a)
• Other Files: license.txt, ; tsp_nn.m

[Kururunfa Goju]

Very nice. It could benefit from the fact of working with TSPLIB files...

[Sandip Vijay]