Using tabu search how are the neighbours selected for travelling salesman?

Question

When trying to understand how tabu search can be applied to travelling salesman, I have struggle understanding how the neighbourhood is generated. If we look at this pseudocode from wikipedia:

sNeighborhood ← getNeighbors(bestCandidate)
for (sCandidate in sNeighborhood)
    if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
        bestCandidate ← sCandidate
    end
end

My best candidate starts as the path generated from a nearest neighbours algorithm, what are the neighbours to this path?

Say my path is A,B,D,C,A is the neighbourhood every possibility for each index? e.g. [B,D,C], [A,C,D] etc?

And then we eliminate neighbours that are in the tabu list for each index?

If not, what is my neighbourhood?

Also in the pseudocode the tabu list only adds new best candidates, so then how do we pick a different neighbourhood next time?

if (fitness(bestCandidate) > fitness(sBest))
    sBest ← bestCandidate
end
tabuList.push(bestCandidate)

Wikipedia source code:

https://en.wikipedia.org/wiki/Tabu_search

Answer 1

Question 1

is the neighborhood every possibility for each index?

Not every, in this case, it can be done since total indices are 4 but it will be too complex when the number of indices increases.

In general neighbourhood can be found by using some heuristics (e.g. direct distance between indices). For example, if path is [A, B, C, F, G, E, D, A] and for every index 2 closest indices are chosen, which are (for example), [B, C], [A, F], [A, D], and so on. Now the neighborhood can be generated using these indices, taking only the valid ones (keeping in mind that each city is only visited once and not in the Tabu list).

Question 2

so then how do we pick a different neighborhood next time?

Yes, the best candidate is pushed in the list but not its neighbors, so it will find new neighbors and won't be stuck in an infinite loop.

For example, a path X will give neighbors Y and Z, of which (lets assume) Z is the best, so Z will be pushed in the Tabu list (and X already was in the list), so now Z won't go to find X and therefore will look for new and better neighbors.