AN INSERT DELETE HEURISTIC FOR THE TRAVELING 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, we present a heuristic approach for the TSSP + 1 class of problems. The general philosophy of our approach is to maintain tour feasibility with respect to the TSSP subproblem. This allows us to begin our 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. We present computational results that show our approach is superior to approaches using just insertion, and thus demonstrate the importance of considering the possible deletion of cities.