For cubic cells, I think the way to do it is to calculate distance for just one point component-wise, and if the distance in any component is greater than 1/2, switch to a different point.
I thought about this in 2-d: There's two points, $A$ and $B$. Since both $A$ and $B$ form a grid, because they're periodic, you can forget about the original unit grid and simply imagine that $A$ is randomly placed within a square created by the points of $B$. Now if I draw lines that represent the points equidistant from any two corner points of this $B$ square, they will form a cross in the middle of the square. So the maximum distance that $A$ can be from $B$, component-wise, is 1/2. If I take any $B$ and calculate the distance to $A$, that will tell me what to do:
- If $A_x-B_x > 1/2$, move to the next $B$ point in the -x direction
- If $A_x-B_x < 1/2$, move to the next $B$ point in the +x direction
- If $A_y-B_y > 1/2$, move to the next $B$ point in the -y direction
- If $A_y-B_y < 1/2$, move to the next $B$ point in the +y direction
- Else, keep the same $B$ point
In 3-d it's the same idea, but you can move in the z-direction.
For non-cubic cells, I can't think of a way that's as quick and simple. One thing you could do is pre-compute the distances between different points in the lattice, so that if you calculate the distance to $A$ and $B_1$ and find that it's less than half of the distance between $B_1$ and $B_i$, then you know that $B_i$ will not be the closest point to $A$, and you didn't have to calculate $B_i$'s position explicitly. There might be a way to do a similar trick as the 3-d one with planes: if you pre-compute vectors $d_{ij}=B_i-B_j$ and then if $d_{ij}\cdot A - \frac{d_{ij}^2}{2} >0$, then $a$ is closer to $B_i$ than $B_j$. This should work because $d_{ij}\cdot r = c$ defines a plane parallel to the plane of points equidistant between $B_i$ and $B_j$; since it should be half-way between $B_i$ and $B_j$ substitute $d_{ij}/2$: $d_{ij}\cdot d_{ij}/2=c$. The problem here is that unlike the simple 3-d case, knowing that $A$ is closer to $B_i$ than $B_j$ doesn't help for any other point $B_k$. Still, 27+ dot products with pre-computed vectors might still be a big speed-up.
Best Answer
I did a project on TSP many years ago where I compared four different algorithms' performance over numerous datasets (in Java).
The algorithms I used were:
My results showed that RMHC performed better than both RRHC and HC; however, SA performed the best overall, providing slightly more precise results than the other three.
All of my tests were run over 100, 1,000, 10,000, 100,000 and 1,000,000 iterations and each and every time SA came out on top.
I hope this helps.