In the field of evolutionary computation, it is common to use benchmarks of instances of a given problem in order to carry out a performance evaluation of existing and newly developed algorithms. When the final goal is to solve specific real-world problems, real instances are used to perform such comparisons, and, thus, we are not interested in an extensive performance evaluation. However, when the objective of the research is to contribute with methodological developments, then large benchmarks of instances are needed in order to evaluate the efficiency of the proposed algorithm under different scenarios. At this point, it is a usual practice, based on the knowledge of the problem to create new “challenging” instances artificially. In this sense, a recurrent option is to generate instances by sampling their parameters uniformly at random (u.a.r.) in some ranges. Taking this assumption as starting point for the talk, we will present a series of discoveries regarding the generation of random instances for a number of permutation-based combinatorial optimization problems.