crippled-2opt

Heuristic for symmetric travelling salesman.

2-opt and 3-opt are implemented. Works fairly well on 100 locations. Table below shows TSP size and execution time of 10000 runs on Macbook Pro (2,6 GHz Intel Core i5) by optimizing a random initial solution. Optimizing only once takes milliseconds.

Clang: with incremental

N	2-opt	2-opt + 3-opt
10	0.2s	0.2s
50	2.0s	5.6s
100	16.2s	59.9s

Gcc: d886d02

N	2-opt + 3-opt
100	43.4s

GCC seems to make better code and incremental evaluation is not necessary. I'm not sure what the difference is.

It is crippled in the sense that too many computations are made, especially during 3-opt. Crippled also is that first all of the 2-opt moves are done then 3-opt moves. Currently the distances are fetched incrementally and results are reused when changing edges. Now, the only thing left is to eliminate recalculation of same pairs and triplets after executing a move. If we were to take a sequence [a1, ..., aN] and calculated all of the O(N^2) ranges for swap. After executing the best, more than 50% of the ranges can be the same.

Executing the moves (reverse and rotate operations) on the solution representation (array) takes very little time. Most of the time is lost evaluating the moves.