The Prize Collecting Travelling Salesman Problem (PCTSP) is a generalization of the Travelling Salesman Problem. It can be associated to a salesman that collects a prize in each city visited and pays a penalty for each city not visited, with travel costs among the cities. The objective is to minimize the sum of the costs of the trip and penalties, including in the tour an enough number of cities that allow collecting a minimum prize. This paper approaches new heuristics to solve the PCTSP, using a hybrid evolutionary algorithm, called Evolutionary Clustering Search (ECS) and an adaptation of this, called CS, where the evolutionary component will be substituted by the metaheuristics GRASP and VNS. The validation of the obtained solutions will be through the comparison with the results found by a commercial solver that was able to solve only small size problems.