Then try Domino's, Taco Bell etc.
AKA Traveling salesman problem? Even with a few hundred cities that would be difficult to find the optimal solution, let alone thousands. You could find a decent to even good solution with other algorithms, though
Many NP-hard approximation algorithms classes teach a 1.5 approx known as the Christofides algorithm. This algorithm is guaranteed to provide an approximate solution that is no worse than 1.5 times the optimal total distance, and often much better.
or solve/run Concorde on Argonne National Laboratory's server here:
Disclaimer: free for academic use
Now uses the the Concorde cutting-plane-based exact TSP solver.
Edit: I really should have named the repo colonel-sanders.