On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem

Source abstract

Randomized arbitrary insertion (RAI), a well-known heuristic for the traveling salesman problem, is applied to the generalized traveling salesman problem (GTSP). The adaptation of the basic idea to the GTSP leads to eight variants of the basic heuristic. These basic constructive heuristics are followed by the iterative improvement phase, in which segments of the current tour are randomly selected, removed, and reinserted back into the solution using RAI. Experiments show that one of the variants of our heuristic, on average, provides solutions that are less than 1.2% above the best-known solution based on standard libraries of benchmark instances including GTSP, MOM and BAF libraries. Although this does not match the performance of the best state-of-the-art solvers, the 1.2% threshold is a surprisingly good achievement taking into account the conceptual simplicity of the heuristic.