The symmetric clustered traveling salesman problem (Q759661)

A travelling salesman problem (TSP) with n cities and symmetric cost matrix C is considered. The cities are partitioned into m groups called clusters and there is an additional constraint that all cities in each cluster must be visited contiguously. This constrained problem is called the clustered TSP (CTSP). Let C' be the matrix obtained by adding a large positive number H to \(C_{ij}\) whenever cities i and j are not in the same cluster. Any optimal tour for TSP with C' as the cost matrix is an optimal tour for CTSP with C as the cost matrix. However, the usual branch and bound algorithm performs poorly with the cost matrix C'. A bounding approach based on an adaptation of the Lagrangean relaxation approach with the 1-tree relaxation for the CTSP, and by introducting a new multiplier corresponding to the constraint that every feasible tour for the CTSP must have m edges (i,j) with cities i and j belonding to different clusters, is described. Heuristics are developed for finding upper bounds, and some techniques are discussed to detect and eliminate nonoptimal edges. With these changes, the branch and bound approach turns out to be satisfactory for the CTSP, as illustrated by computational results on problems involving up to 150 cities.