Even though the problem is computationally difficult, a large number of heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.
Chiar dacă problema este dificilă computațional, se cunosc numeroși algoritmi euristici⁠(d) și exacți⁠(d), astfel încât unele cazuri cu zeci de mii de orașe pot fi rezolvate complet și chiar probleme cu milioane de orașe pot fi aproximate cu o eroare de 1%.