Dans ce papier nous considérons le problème d'Arbre Couvrant Minimal de cardinalité k (k-MST) qui généralise le fameux problème de l'arbre couvrant minimal qui est l'un des classes majeurs d'optimisation combinatoire. La modélisation de ce problème a été présentée au début par Hamacher et al. (1991), et il a été démontré par la suite que le problème de k-MST est un problème NP-complet, et c'est pourquoi il est nécessaire de développer des approches approximatives basées sur des métaheuristiques pour résoudre ce problème dans un temps polynomial. Plusieurs approches ont été proposées dans la littérature pour aborder ce sujet. Blum and Blesa (2005) ont proposés trois métaheuristiques: les algorithmes évolutionnaires, les algorithmes de colonies de fourmis et la recherche tabou. Un algorithme hybride combinant TS et ACO est fourni par Katagiri et al. (2012). Dans ce papier nous avons proposé une nouvelle approche basée sur l'algorithme du recuit simulé. Les expérimentations numériques réalisées sur des instances de graphes de la bibliothèque KCTLIB proposés par Blum and Blesa (2005), comparés avec les résultats présentés dans Blum et Blesa (2005) et Katagiri et al. (2012), ont montré l'efficacité de notre approche.