travelling salesman local search heuristic

I am trying to create a local search heuristic to solve the TSP, and this process seems to be failing. I have generated a random Hamiltonian cycle and stored it in outgoing[] with outgoing[i] denoting the vertex which one of the edges originating at i points towards. distances[a][b] denotes the distance from vertex a to vertex b. However, whenever I run this code, instead of optimizing the Hamiltonian cycle which I pass in outgoing, the algorithm simply creates the new cycle 0->numcities-2->1->numcities-1. It should simply switch the outgoing vertices repeatedly if it can improve upon the distance of a vertex to its outgoing vertex. I am probably overlooking something minor, but I simply cannot figure out what I did wrong. I will be running this many times by the way, and that is what the boolean changed is used for.

for(int i = 0; i < numcities; i++)
{
   for(int j = i+1; j < numcities; j++)
   {
      if(distances[i][outgoing[i]] + distances[j][outgoing[j]] > distances[i][outgoing[j]] + distances[j][outgoing[i]] && i != outgoing[j] && j != outgoing[i])
      {
        changed = true;
        int temp = outgoing[j];
        outgoing[j] = outgoing[i];
        outgoing[i] = temp;
      }
    }
}

The problem is that when you swap outgoing[i] and outgoing[j], you are creating two subtours -- two smaller cycles.

For example, suppose numcities=6 and your starting tour is 0 1 2 3 4 5. Suppose your if statement is true for i=1, j=3. Your code sets outgoing[1] = 4 and outgoing[3] = 2. So the code thinks the tour is now 0 1 4 5 since outgoing[1] = 4. This isn't precisely the tour that you are getting, but I think it's the same basic idea.

To fix this, you need to think of the tour in 3 parts -- (A) the part up to and including city i, (B) the part between i and j (including j), and (C) the part after j. When you swap the edges you need to reconfigure the tour so (A) is the same as before, then part (B) is reversed, then part (C) is intact.

So in my example, part (A) is 0 1, part (B) is 2 3, and part (C) is 4 5. After breaking the edges 1-2 and 3-4, and reattaching, you get the tour 0 1 3 2 4 5.

What you are implementing here is called a 2-opt. You'll find more information on it in lots of places.