The Traveling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem, commonly studied in computer science and operations research. Due to its complexity and broad applicability, various algorithms have been designed and developed from the viewpoint of intelligent search. In this paper, we propose a two-stage method based on the clustering concept integrated with an intelligent search technique. In the first stage, a set of clustering techniques - fuzzy c-means (FCM), k-means (KM), and k-mediods (KMD) - are employed independently to generate feasible routes for the TSP. These routes are then optimized in the second stage using an improved Genetic Algorithm (IGA). Actually, we enhance the traditional Genetic Algorithm (GA) through an advanced selection strategy, a new position-based heuristic crossover, and a supervised mutation mechanism (FIB). This IGA is implemented to the feasible routes generated in the clustering stage to search the optimized route. The overall solution approach results in three distinct pathways: FCM+IGA, KM+IGA, and KMD+IGA. Simulation results with 47 benchmark TSP datasets demonstrate that the proposed FCM+IGA performs better than both KM+IGA and KMD+IGA. Moreover, FCM+IGA outperforms other clustering-based algorithms and several state-of-the-art methods in terms of solution quality.