I want to try my hand at finding heuristics/approximations for solving the Traveling Salesman Problem, and in order to do that, I'm looking for some "hard" TSP instances (along with their best known solutions) so that I can try solving them and see how well I can do.
Ideally, they would be simply a text-based list of adjacency matrices or adjacency lists (I don't want to deal with parsing, just the algorithm).
By "hard", I mean that they should be practically impossible to solve or approximate using brute-force.
(This is so that I can be reasonably confident that if I find an answer close to the best known answer, then I'm actually doing something right, and not just getting lucky.)
Are there any lists that would work for this purpose? I searched around a bit but didn't find anything.
Here is another question on SE partially answering your problem (it lists problems, but most of these seems not to have a solution provided, but you better check the links anyway - things may have changed).
If you can't find them, what about randomly generating a set of nodes along with a path connecting them, saving the path length as "minimal" (making sure that the longest connection between two nodes is never > X) and then adding a bunch of other paths making sure these are all > X?
This way (unless I am missing something) you have a set of connected nodes "as complex as you want" and know the actual shortest connecting path from the start...
Addendum - if you really want to see how you compare to existing tools, then you have to run these on your generated problems. One that is free and accessible (but I don't know how "efficient" it may be) is the TSP Library for R.
Wikipedia has a list of other free sw packages for this.
Maybe you could create a different SE question asking for how to get other TSP tools.