New TSP Construction Heuristics and Their Relationships to the 2-Opt |
| |
Authors: | Hiroyuki Okano Shinji Misono Kazuo Iwano |
| |
Affiliation: | (1) Tokyo Research Laboratory, IBM Japan, 1623-14, Shimotsuruma, Yamato, Kanagawa, 242-8502, Japan |
| |
Abstract: | Correction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. This study analyzes the 2-Opt dependency, which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics. In accordance with the analysis, we devise a new construction heuristic, the recursive-selection with long-edge preference (RSL) method, which runs faster than the multiple-fragment method and produces a comparable tour when they are combined with the 2-Opt. |
| |
Keywords: | traveling salesman problem construction heuristic edge-exchange heuristic 2-Opt dependency |
本文献已被 SpringerLink 等数据库收录! |
|