ABSTRACT
The most general version of the Prize-Collecting Traveling Salesman Problem (PCTSP) was first introduced by Balas [1]. In this problem, a salesman has to collect a certain amount of prizes (the quota) by visiting cities. A known prize can be collected in every city. Furthermore, by not visiting a city, the salesman incurs a pecuniary penalty. The goal is to minimize the total travel distance and the total penalty, while starting from a given city and collecting the quota.
