Generating Travelling-Salesman Problems with Known Optimal Tours
提出一种随机生成旅行商问题实例的算法，这些实例的最优路径已知，可用于测试和比较不同求解方法的性能。
AbstractAn 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.Keywords: problem generatortravelling-salesman problemView correction statement:Erratum: Generating Travelling-Salesman Problems with Known Optimal Tours An erratum to this article is available at http://dx.doi.org/10.1057/jors.1989.48.An erratum to this article is available at http://dx.doi.org/10.1057/jors.1989.48.