1
$\begingroup$

When devising heuristics for the TSP I often see edge exchange algorithms suggested. But I also find them a bit hard to understand and somewhat cumbersome to implement.

When I think about a TSP, I imagine a permutation of the nodes of the problem, and hence I always default to swapping nodes in the permutation.

Is there any literature on the relative performance of edge exchange heuristics and node swap heuristics?

Also, is a node swap heuristic a special case of an edge exchange?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Well, you can achieve a node swap with 2 edge swaps, but an edge swap can take around n/4 node swaps. So edge swaps are stronger. $\endgroup$
    – user1502040
    Mar 17 at 20:38
  • $\begingroup$ The value of the solution of a TSP is a function of its edges. The more edges are changed, the furthest the neighbor will be from the current solution. In contrast, this is not true for some scheduling problems. And therefore, in this case, the "shift job" neighborhood might be more "elementary". In practice, 2-opt and sub-block shifts neighborhoods are used both together $\endgroup$
    – fontanf
    Mar 18 at 0:20

0

Reset to default

Your Answer

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