local_search returns are inconsistent and path lengths are incorrect

[supersimple33]

When I call solve_tsp_local_search sometimes my path is returned in the form [0,2,1,3,4] and sometimes in the form [0,0,2,1,3,4]. Also the calculated path length is incorrect on cases of where the form has the zeros next to each other. See the following TSP

NODE_COORD_SECTION 1 6734 1453 2 2233 10 3 5530 1424 4 401 841 5 3082 1644 6 7608 4458 7 7573 3716 8 7265 1268 9 6898 1885 10 1112 2049 11 5468 2606 EOF

The path length of solve_tsp_local_search(euc_dist_matrix, nn_path) for that tsp is wrong

[fillipe-gsm]

Hi, @supersimple33

I am not able to reproduce your issue. Can you provide all of the steps you are following since the distance matrix creation, to calling solve_tsp_local_search, with all of its parameters?

In your description, your TSPLIB data is invalid; I am not able to import it using the tsplib_distance_matrix function. Also, what are the values of the arguments euc_dist_matrix and nn_path?

In my attempt, I first fixed your TSPLIB data like the following (I assume you are using the Euclidean distance):

TYPE : TSP
EDGE_WEIGHT_TYPE : EUC_2D
DIMENSION: 11
NODE_COORD_SECTION
1 6734 1453
2 2233 10
3 5530 1424
4 401 841
5 3082 1644
6 7608 4458
7 7573 3716
8 7265 1268
9 6898 1885
10 1112 2049
11 5468 2606
EOF

and put it into a file called data.tsp.

Then I ran it as follows:

from python_tsp.distances import tsplib_distance_matrix
from python_tsp.heuristics import solve_tsp_local_search

distance_matrix = tsplib_distance_matrix("data/data.tsp")

# Attempts
In [24]: solve_tsp_local_search(distance_matrix)
Out[24]: ([0, 2, 1, 3, 9, 4, 10, 5, 6, 8, 7], 19593)

In [25]: solve_tsp_local_search(distance_matrix)
Out[25]: ([0, 7, 8, 6, 5, 10, 4, 9, 3, 1, 2], 19593)

In [26]: solve_tsp_local_search(distance_matrix)
Out[26]: ([0, 7, 8, 6, 5, 10, 4, 9, 3, 1, 2], 19593)

In [27]: solve_tsp_local_search(distance_matrix)
Out[27]: ([0, 7, 8, 6, 5, 10, 4, 9, 3, 1, 2], 19593)

In [28]: solve_tsp_local_search(distance_matrix)
Out[28]: ([0, 2, 1, 3, 9, 4, 10, 5, 6, 8, 7], 19593)

I couldn't observe the behavior you mentioned.

Can you try like I am showing you here and see if the problem persists?

[supersimple33]

Yeah the second part was my own fault I didn't understand you needed to format the input tours as n points not n+1 with returning to the end. That said I think I ran into the same things as #41 since I am doing a very similar thing to what he described. I am about halfway through drafting a PR for this and should have it done by tonight or EOD tmrw hopefully.

[fillipe-gsm]

Hey, since this misunderstanding got sorted, I am going to close this issue.

Feel free to open a new one in case you find a different problem.