An insert/delete heuristic for the Travelling Salesman Subset-tour Problem with one additional constraint

The Travelling Salesman Subset-tour Problem (TSSP) differs from the well-known Travelling Salesman Problem (TSP) in that the salesman is not required to visit every city. Many problems, such as the prize collecting TSP, the orienteering problem, and the time constrained TSP, can be viewed as TSSPs with one additional constraint (TSSP+1). In this paper, the authors present a heuristic approach for the TSSP+1 class of problems. The general philosophy of the present approach is to maintain tour feasibility with respect to the TSSP subproblem. This allows the authors to begin their approach with any TSSP tour. In each step, the insertion or deletion of a city is performed either to reduce infeasibility in the additional constraint or to improve upon the minimization objective. The authors present computational results that show the present approach is superior to approaches using just insertion, and thus demonstrate the importance of considering the possible deletion of cities.