Simulated Annealing

I'm having trouble with my simulated annealing program, and with the concept in general.

How long should I have to run simulated annealing on the 225 city TSP problem?

What I've got right now always gets close to optimal, but it never gets the exact best answer.

How much slower? It already takes like 10 minutes.

At the moment, my initial Temp is (-AverageDistance / Math.Log(0.99))
Where AverageDistance is the calculated from applying the permutation operation 1000 times and the differences.

Then the probability is (Math.Exp(-(deltaE / T)))
Where deltaE is the difference between the current permutation and the next permutation candidate.

It starts at about 100% probability. At some point though, it drops really quickly from about 80% to near 0.

For cooling, I'm just setting the Temp to Temp*0.999999 every iteration.