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 timedouble 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;}`
You may download the whole source (with his Makefile) here.
Enjoy