Generating Travelling-Salesman Problems with Known Optimal Tours
Jeffrey L. Arthur, James O. Frendewey · Journal of the Operational Research Society · 1988
An algorithm is presented for randomly generating travelling-salesman problems (TSPs) for which the optimal tour is known. Both asymmetric and symmetric problems can be generated, with the option of having the distance matrix satisfying the triangle inequality. No limit exists to the number of nodes that can be considered, making the use of the generator attractive to those involved in the design and comparison of TSP solution approaches. Empirical testing of the generator indicates that the resultant problems are as difficult as problems generated in a completely random manner.