Back with the last part of TSP problem, if you missed the first one you can find it here.

The TSP competition ended up in June, and I finished in third position. As you may have noticed in the results table, there is a couple of problem which where hard to lower, especially the u1060.

Let's see some code...
2OPT:
// Take a tour array
// Return running time
double twoOpt(int *tour) {
clock_t start, end;

if (LOG) {
fprintf(debfp, "2 Opt local optimization...\n");
}
if (DEBUG)
printf("2 Opt local optimization...\n");

start = clock();

int bestGain = INT_MAX;
int best_i;
int best_j;
int gain;
double ct = 0.0;
int count = 0;
// Continue until no improvements are possible
while (bestGain != 0) {
bestGain = 0;
for (int i = 1; i < dimension; i++) {
int j = i + 2;
for (; j < dimension; j++) {
gain = compute_gain(tour, i, j);
// Search for the biggest gain
if (gain < bestGain) {
bestGain = gain;
best_i = i;
best_j = j;
}
}
}
count++;

if (DEBUG2OPT)
printf("Best optimization %d->%d and %d->%d = %d\n", tour[best_i],
tour[best_i + 1], tour[best_j], tour[best_j + 1], bestGain);

if (LOG) {
fprintf(debfp, "Best optimization %d->%d and %d->%d = %d\n",
tour[best_i], tour[best_i + 1], tour[best_j], tour[best_j
+ 1], bestGain);
}

if (bestGain != 0) {
if (DEBUG2OPT)
printf("SWAP");

// Swap cities
swap(tour, best_i + 1, best_j);
// Reverse path
reverseArray(tour, best_i + 1, best_j);
}
}

end = clock();
ct = ((end - start) / ((double) CLOCKS_PER_SEC)) * 1000.0;
return ct;
}

Simulated Annealing:
int *simulatedAnnealing(int *tour, int remainingMS, int startTemp,
double delta, int iteration) {
int *current = (int *) calloc(sizeof(int), dimension + 2);
int *best = (int *) calloc(sizeof(int), dimension + 2);
int *next = (int *) calloc(sizeof(int), dimension + 2);

clock_t start, end;

current = tour;
next = tour;
best = current;
double temp = startTemp;
int diff = 0;

int iter = iteration;
if(randomSeed==0)
randomSeed = time(NULL);

srand(randomSeed);

double random = 0.0;
int lenNext = 0;
int lenCurrent = 0;
int lenBest = length(current);

if (DEBUGSA) {
printf("SA: Random seed: %d\n Remaining time: %d\n", randomSeed, remainingTime);
}

while (temp > 0 && remainingMS > 0) {

while (iter > 0) {
// Start clock
start = clock();
next = doubleBridge(current); // Diversification
twoOpt(next); // Intensification
lenNext = length(next);
lenCurrent = length(current);
diff = lenNext - lenCurrent;

if (DEBUGSA) {
printf("SA: Difference between next[%d] and current[%d] = %d\n", lenNext, lenCurrent, diff);
}

if (diff < 0) {
current = next;
if(lenNext < lenBest)
{
if(tourCheck(next, lenNext))
{
if(lenNext < bestknown)
{
printf("Stopped something wrong!");
getchar();
}
copy(next, best, dimension + 2);
printf("*** NEW BEST: %d\n", lenNext);
lenBest = lenNext;
} else
{
printf("Wrong tour!\n");
}

}
} else {
random = (rand() / ((double)RAND_MAX));
if (DEBUGSA) {
printf("SA: Generated random: %2.3f\n", random);
}
// Stochastic decision
if (random < exp(-diff / temp)) {
// current = next
if (DEBUGSA) {
printf("Current = next");
}
copy(next, current, dimension + 2);
} else {
// keep current
}
}
// Compute remaining time
end = clock();
remainingMS -= (((end - start) / ((double) CLOCKS_PER_SEC))
* 1000.0);

iter--;
}
iter = iteration;
temp = temp * delta;
}
return best;
}