What is it about?
Based on optimal tours and it's theoretical features, the two-dimensional Euclidean Traveling Salesman Problems are divided into sub-problems recursively. Instantly, using this proposed method, the optimal tours of the TSPs can be divided into several sub tours. Then, the city sets for the sub tours also construct sub-problems, called Shortest Hamiltonian Path Problems, for finding an optimal path. In other words, the proposed method can generate many TSPs with optima from the original TSPs of that optimal tours are already clear.
Featured Image
Why is it important?
The instances of the TSPs are extremely useful to verify new or old methods solving these instances. As an example, TSPLIB is the most famous benchmarks of the TSPs including many instances of that the optimal tours and its costs are discovered. However, it seems that the number of instances is not enough because of high computational costs to obtain the optimal solution. Then, the proposed method can generate new instances with the optima from the original instances in the benchmarks of that the optimal tours are already calculated.
Perspectives
The original and generated instances with the optima are available and applicable for various research for the two dimensional Euclidean TSPs. This achievement will make valuable supports for research of the TSPs and also the combinatorial optimization scope. I hope and believe the research result will lead successes and progresses in TSP research.
Assistant Professor Akihiko Kawashima
Nagoya University
Read the Original
This page is a summary of: Generator of learning data for the TSPs based on the visiting order of the cities on convex hull, September 2010, Institute of Electrical & Electronics Engineers (IEEE),
DOI: 10.1109/isic.2010.5612909.
You can read the full text:
Contributors
The following have contributed to this page
