The paragraph on V-opt heuristic TSP algorithms at this site mentions a very effective algorithm due to Lin-Kernigham-Johnson. That page says:
For many years Lin–Kernighan–Johnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best known solutions for all other TSPs on which the method had been tried.
Impressive, so what is the complexity of that algorithm? Does the algorithm often work faster than predicted based on theoretical complexity (if yes, how much)? Is that algorithm used most often in software that solves the TSP?