Is there an optimal algorithm for approximating the traveling salesman problem with a large number of cities?

Question

C++ / C#

Hello!
Tell me, please, subject.
A large number refers to 500 or more.
It will be implemented in c++ with 128GB of RAM, with an attempt to parallelize it into 16 threads.
So far, I have tried the branch and bound method (even 100 with difficulty), genetic (far from optimal + it is not clear how
to choose the parameters). Now I'm trying to implement an ant colony.
From the algorithm it is desirable as usual - the smallest time with the best result. Possible resources are listed above.
I tried to find somewhere a comparison of existing algorithms on the same data set, but alas. I feel that my strength is not enough to write (or port already written) and run at least a hundred thousand times for at least some statistics.
PS Datasets preferably with TSPLIB =)

Answer 1

on a cagle in the new year there was a competition in tsp for 198,000 cities, here it is , only there was an additional condition, if possible, the id of every tenth city on the way should be a prime number.
look in the kernels and discussions, there is a lot of information on different solutions and implementations. In short, the solution comes down to 2-opt, 3-opt, 4-opt, 5-opt runs, the longer the better, with a gradual improvement in the result. Plus periodic random changes in the path to knock out the local minimum (annealing method).