1
$\begingroup$

I am trying to solve Travelling Salesman Problems using tabu search. I have been able to successfully find "near enough" optimal solutions (as well as one optimal, yay!).

For the moment I am using sub-tour reversal as the local search precedure. The basic gist of it is similar to 2-opt, but rather than swapping two cities, it reverses the subtour between and including those two cities. I.e if we have a tour [1, 2, 3, 4, 5, 6, 1] and we swap city 2 and 5 we get [1, 5, 4, 3, 2, 6, 1].

However I am using two "for" loops to find the best neighborhood from the initial tour. But as you know, going through every single swap is a very time consuming process, which limits me to TSP problems of less than 500 cities. Anything above 1000 cities will take my program hours.

So my question is, can I apply some other method than two or loops to find the best neighborhood in more efficient (fast)?

For now my "for" loops look like this:

int col = 1;
for (int i = 1; i < initialSolution.length-1; i++) {
    for (int j = col; j < initialSolution.length-1; j++) {
        if (i == j) {
            continue;
        }
        if ((i == 1) && (j == initialSolution.length-2)) {
            continue;
        }
        if ((j == 1) && (i == initialSolution.length-2)) {
            continue;
        }
        // LOCAL SEARCH PRECEDURE
    }
}

such that I do not repeat previously reversed tours, and such that I do not reverse the whole tour.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.