The problem addressed in this paper can be described as follows. Given a set of n cities, including the initial city or depot, and a predetermined value k (≤ n). A deliveryman, departing from the depot, must visit only k cities (including the depot) once, and after visiting the last city; the deliveryman does not need to return to the depot. The objective is to minimize the total distance traveled by the deliveryman. The problem is called as the Open k-Traveling Salesman Problem (O-k-TSP). This problem comprises two sub-problems: selecting exactly k cities to be visited and obtaining the best order to visit these cities (optimal sub-route). As the O-k-TSP problem is NP-Hard, in this paper, a simple heuristic based on the meta-heuristic GRASP (Greedy Randomized Adaptive Search Procedure) is developed, where the local search, used to improve the different constructed solutions, is based on the heuristic RVND (Random Variable Neighborhood Descend). The performance of the proposed heuristic was evaluated using a set of TSPLIB instances and the obtained results were compared with results generated by a Genetic Algorithm (GA) from the literature. The obtained results indicate that the proposed approach has a superior performance in relation to GA.