next up previous contents index CD CD Algorithms
Next: Maximum Cut Up: Simulated Annealing Previous: Simulated Annealing

Traveling Salesman Problem

The solution space for traveling salesman consists of the set of all (n-1)! possible circular permutations of the vertices. A candidate solution can thus be represented using an array S of n-1 vertices, where tex2html_wrap_inline25852 defines the (i+1)st vertex on the tour starting from tex2html_wrap_inline25856 . The cost function evaluating a candidate solution is equally straightforward, for we can sum up the costs of the edges defined by S.  

Figure: Improving a TSP tour by swapping a pair of edges  

The most obvious transition mechanism would be to swap the current tour positions of a random pair of vertices tex2html_wrap_inline25858 and tex2html_wrap_inline25860 . This changes up to eight edges on the tour, deleting the edges currently adjacent to both tex2html_wrap_inline25862 and tex2html_wrap_inline25864 , and adding their replacements. Better would be to swap two edges on the tour with two others that replace it, as shown in Figure gif. Since only four edges change in the tour, the transitions can be performed and evaluated faster. Faster transitions mean that we can evaluate more positions in the given amount of time.

In practice, problem-specific heuristics for TSP outperform simulated annealing, but the simulated annealing solution works admirably, considering it uses very little knowledge about the problem.

Mon Jun 2 23:33:50 EDT 1997