Abstract: Decomposition methods for solving large-scale Traveling Salesman Problem (TSP) are presented. Three approaches are proposed: macromodeling for clustered TSP as well as extending and “ring” methods for arbitrary points’ distribution. Four stages of the problem solving include partitioning of the input set of points into small subsets, finding the partial high quality solutions in the subsets, merging the partial solutions into the complete initial solution and optimizing the final solution. Experimental investigations as well as the comparative analysis of the results and their effectiveness estimation in terms of quality and running time were conducted. The suggested approaches provide substantial reduction in the running time in comparison with the existing heuristic algorithms. The quality loss is small. The problem instances up to 200,000 points were investigated. The TSP is extensively applied in transportation systems analysis, printed circuit boards, VLSI, SoC and NoC computer-aided design, testing and manufacturing, laser cutting of plastics and metals, protein structure research, continuous line drawings, X-ray crystallography as well as in number of other fields.

Keywords: traveling salesman problem, combinatorial NP-hard problems, decomposition, large-scale.

ACM Classification Keywords: G.2.1 Combinatorics - Combinatorial algorithms; I.2.8 Problem Solving, Control Methods, and Search - Heuristic methods.

Link:

DECOMPOSITION METHODS FOR LARGE-SCALE TSP

Roman Bazylevych, Marek Pałasiński, Roman Kutelmakh, Bohdan Kuz, Lubov Bazylevych

http://www.foibg.com/ibs_isc/ibs-26/ibs-26-p10.pdf