What is the asymptotic runtime of the best known TSP solving algorithm? I always thought that TSP currently requires time exponential in the number of cities to solve.


  How, then, has Concorde optimally solved a TSP instance with
  85,900 cities?!?


Is this a typo? Is the base of the exponential 1.0000000000000001 or similar? Was it an instance specifically constructed to be solvable easily? What is the asymptotic runtime of the best known TSP solving algorithm?
The worst case running time of Concorde or any other known method is exponential in the size of the input. However, sometimes heuristics or other pruning techniques are effective and you are able to solve some, even large, instances pretty quickly. You should define exactly what you mean by TSP as there are many variants, and many algorithms with different worst case run times.

See the accepted answer in this question on CSTheory to see a list of algorithms.