Match twice and stitch: a new TSP tour construction heuristic |
| |
| Authors: | Andrew B Kahng |
| |
| Affiliation: | UCSD Computer Science & Engineering Department, 9500 Gilman Drive, MS 0114, La Jolla, CA 92093-0114, USA |
| |
| Abstract: | We present a new symmetric traveling salesman problem tour construction heuristic. Two sequential matchings yield a set of cycles over the given point set; these are then stitched to form a tour. Our method outperforms all previous tour construction methods, but is dominated by several tour improvement heuristics. |
| |
| Keywords: | Traveling salesman problem Heuristic Tour construction |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
