An Insert/Delete Heuristic for the Travelling Salesman Subset-Tour Problem with One Additional Constraint
针对旅行商子集巡游问题（TSSP）加上一个额外约束的问题类，提出一种通过插入或删除城市来保持可行性和优化目标的启发式方法，计算表明优于仅用插入的方法。
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 + I 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.