The comments about hard problems and hard instances is very interesting. I'm curious if there are any ways to generate hard traveling salesman problems. Or even better, if you can start with a solution (e.g., an order of 1,...,n) and generate a good traveling salesman around that.