TSP solution interpretation

Question

This is mostly a consulting question.

I've developed a genetic algorithm to solve the TSP, long story short, I have written two different codes the and i used this as my dataset. the programs' found solution are shown below.

As it is obvious the suggested solution from the first program(Prog# 1) is much more promising than the second one(Prog# 2) to be optimized; and the solution from Prog# 2 seems to be a random solution most likely.

BUT the cost of Prog# 1 as i have calculated is 97314.36 and the cost of Prog# 2 is 74635.31 which is almost 20K smaller than the cost of solution from Prog# 1, and as costs are suggesting the solution found by Prog# 2 SHOULD BE much more optimized than the first solution.

Question

1) Why on earth the path plot of solution found by Prog# 2 does not support (visually) the calculated cost value?

2) Considering the blow scripts, is there anything i have missed?

---

For completeness i post the script i used to plot and calculating the cost value.

function tsp_plot_output() 
    close all;
    disp('loading data....');
    x=load('out.res'); 
    dist = 0;
    for i=1:2:size(x, 1)-1
        dist = dist + norm(x(i,:) - x(i+1,:), 2);
    end
    dist = dist + norm(x(1,:) - x(end,:), 2);
    fprintf('COST IS: %.2f\n', dist);
    disp('ploting data....');
    xx = x(:,1); xy = x(1:size(xx, 1),2);
    zxx = x(:,1); zxy = x(1:size(zxx),2);
    plot(xx, xy), title('Found TSP solution');
    hold
    plot(zxx, zxy, 'r.');
end

The code i used in Prog# 1 to pour out the solution is

std::ofstream os(outputfile);
BOOST_FOREACH(size_t city, *best->_genes) {
    auto loc = _data->get(city);
    os<<loc.longitude<<" "<<loc.latitude<<endl;
}
os.close(); 

And same code in Prog# 2

ofstream out(jconfig["output-file"].as_string());
for(int i = 0; i < p->lchrom; i++) {
    city c = data.at(best_found->chrom[i]);
    out<<c.x<<" "<<c.y<<endl;
}
out.close();

Answer 1

Your distance calculation im MATLAB is wrong. You have:

dist = 0;
for i=1:2:size(x, 1)-1
    dist = dist + norm(x(i,:) - x(i+1,:), 2);
end
dist = dist + norm(x(1,:) - x(end,:), 2);

With for i=1:2:size(x,1)-1 you start at i=1, and then add 2 in each step until you reach size(x,1)-1. Therefore, you add the distances from 1-2, then from 3-4, and so on. Of course it should be from 1-2, then 2-3 and so on. This is achieved by

dist = 0;
for k=1:size(x,1)-1
    dist = dist + norm(x(k+1,:) - x(k,:),2);
end
dist = dist + norm(x(end,:) - x(1,:),2);

For an example x = [0,0; 1,1; 1,0] the old routine returned 2.4142, while the corrected one returns the correct sqrt(2) + 1 + 1 = 3.4142.

PS: I changed the running variable to k, as in MATLAB i stands for the imaginary unit (see this question for details). I also changed the order of the x's inside the norm. Of course yours wasn't wrong, but that way it is clear that you take the vector from the current point k to the next point k+1 and not the other direction.