If you will even need to solve TSP, this guy solved it almost optimally for millions of cities http://webhotel4.ruc.dk/~keld/ http://webhotel4.ruc.dk/~keld/ T

If you will even need to solve TSP, this guy solved it almost optimally for millions of cities http://webhotel4.ruc.dk/~keld/ http://webhotel4.ruc.dk/~keld/ This is from my experience of dealing with it more than a decade ago.