This paper presents a technique that generalizes the classical k-opt exchange procedure for the symmetric MTSP (Multiple Traveling Salesmen Problem), by considering exchanges leading to the partition of a single tour into a number of smaller subtours. These subtours are then merged back together into an equivalent single tour. In this way, more exchange opportunities are explicitly considered during the k-opt procedure and greater improvements can be achieved. As the authors will show, the technique is particularly powerful for MTSP problems with time windows. Numerical results are presented at the end of the paper for the classical non-constrained MTSP and for the MTSP with time windows.
