I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$ and bigger. I tried of course to generate a graph with a cost matrix with values taken from a random $U(0,1)$, and found out that (as expected) the histogram for the path cost (drawn by sampling a lot of random paths) has a very narrow normal distribution ($\mu$ is $~100$ but $\sigma$ is around $4$). This means, in my opinion, that the problem is very easy, since most random paths will be below the average, and the minimum cost path is very close to a random path.
So I tried the following approach: After generating the $U(0,1)$-matrix, take a long random walk around the graph, and randomly (Bernoulli with $p=0.5$) double or halve the value of the edge. This tends to lower all values, eventually reaching zero, but if I take just the right number of steps, I can get a distribution with $\mu$ around $2$ and $\sigma$ around $1$.
My question is, first, is this even a good definition for an interesting problem? Ideally I would want an instance that is highly multi-modal (for the most common neighborhood functions), and that has very few paths near the minimum value, so that most random solutions will be very far from the optimum. The second question is, given this description, how can I generate instances with such characteristics?