Nearest Neighbour Travelling Salesman Problem

I have implemented the nearest neighbour algorithm for solving the TSP. i dont know what im doing wrong i have worked the solution out by hand to achieve the result. Route = 1- 2 - 3 - 6 - 4 - 5 and a Route length of 15. However i cant get my code to achieve this.

function [RouteLength,Route] = TSP(cities)
tic

cities = [0 1 9 2 5 7;
          1 0 1 9 3 3;
          9 1 0 4 10 4;
          2 9 4 0 1 3;
          5 3 10 1 0 5;
          7 3 4 3 5 0];

NumberOfcities = size(cities);
RouteLength = realmax;
for i = 1:NumberOfcities
    
    FirstCity = i;
    path = FirstCity;
    
    distanceTraveled = 0;
    distancesNew = cities;
    
    currentCity = FirstCity; 
    
    for j = 1:NumberOfcities-1
        
        [minimum,NewCity] = min(distancesNew(:,currentCity));
        if (length(NewCity) > 1)
            NewCity = NewCity(1);
        end
        
        path(end+1,1) = NewCity;
        distanceTraveled = distanceTraveled +...
                    cities(currentCity,NewCity);
        
        distancesNew(currentCity,:) = realmax;
        
        currentCity = NewCity;
        
    end
    
    path(end+1,1) = FirstCity;
    distanceTraveled = distanceTraveled +...
        cities(currentCity,FirstCity);
    
    if (distanceTraveled < RouteLength)
        RouteLength = distanceTraveled;
        Route = path;
    end 
end

disp(Route)
toc

[Torsten]

2 -> 1 -> 4 -> 5 -> 6 -> 3 -> 2 is shorter with a length of 14.

Answer 1

[Chetan]

Hi @Darren Tharby!

According to my understanding that you are trying to implement the nearest neighbor algorithm but are facing some issues.

Upon reviewing the code, I noticed a problem with initialising the "distancesNew" variable.

Instead of assigning

distancesNew = cities;

it is important to initialize the elements of the "distancesNew" matrix with the value "realmax" to ensure that the diagonal elements, representing distances from a city to itself, are set to infinity.

To resolve this issue, I suggest modifying the relevant section of your code as follows:

% Initial code 
path = FirstCity; 
distanceTraveled = 0; 
distancesNew = cities; 
distancesNew(1:NumberOfCities+1:end) = realmax; 
currentCity = FirstCity; 
% Remaining code... 

If you require further information on the "realmax" function, I recommend referring to the accompanying documentation.

• Largest positive floating-point number - MATLAB realmax - MathWorks India

I hope this provides you with the required information regarding your query

Thank you

Chetan Verma