This paper considers a variant of the Travelling Salesman Problem which is to determine a tour visiting each vertex in the graph at most at one time; if a vertex is left unrouted a given penalty has to be paid. The objective function is to find a balance between these penalties and the cost of the tour. This problem is called the Profitable Tour Problem (PTP). If, in addition, each vertex is associated with a prize and there is a knapsack which guarantees that a sufficiently large prize is collected, it is the well-known Prize-collecting Travelling Salesman Problem (PCTSP). This paper summarizes the main results presented in the literature, then gives lower bounds for the asymmetric version of PTP and PCTSP. Moreover, it shows through computational experiments, that large size instances of the asymmetric PTP can be solved exactly.
