This paper is concerned with an interesting variant of the traveling salesman problem (TSP) called a profitable tour problem (PTP). Unlike TSP, in PTP there is no need to visit all the cities, and each city is associated with a profit which the salesman gets in case he visits that city. Like TSP, a travel cost is incurred in visiting a city that depends on the city visited last before visiting the city in consideration. The goal of the problem is to maximize the total profit minus total travel cost. In this paper, we have proposed three methods, viz. a multi-start hyper-heuristic (MSHH), a multi-start iterated local search (MS-ILS) and a multi-start general variable neighborhood search (MS-GVNS) to solve the PTP. MSHH uses eight different low level heuristics, whereas MS-ILS and MS-GVNS utilize variable neighborhood descent search over five different neighborhoods for local search. To evaluate the performance of the proposed approaches, a set of benchmark instances is generated based on the publicly available TSPLIB instances. Computational results on these instances show the effectiveness of our proposed approaches.