En este documento, abordamos el desafío de crear conjuntos de candidatos para instancias de Problemas del Viajante de Comercio (TSP) a gran escala, donde la elección de un subconjunto de aristas es crucial para la eficiencia. Los métodos tradicionales para mejorar recorridos, como búsquedas locales y heurísticas, dependen en gran medida de la calidad de estos conjuntos de candidatos pero a menudo tienen dificultades en situaciones a gran escala debido a una cobertura insuficiente de aristas o una alta complejidad temporal. Presentamos una nueva heurística basada en clustering difuso, diseñada para producir conjuntos de candidatos de alta calidad con una complejidad temporal casi lineal. Probada exhaustivamente en instancias de referencia, incluidos tipos VLSI y Euclídeos con hasta 316,000 nodos, nuestro método supera consistentemente a técnicas tradicionales y líderes actuales para TSP grandes. Los recorridos de nuestra heurística abarcan casi todas las aristas de las soluciones óptimas o mejor conocidas, y sus conjuntos de candidatos son significativamente más pequeños que los producidos con la heurística POPMUSIC. Esto resulta en una ejecución más rápida de métodos de mejora posteriores, como la heurística de Lin-Kernighan de Helsgaun y algoritmos evolutivos. Esta mejora sustancial en el tiempo de cálculo y la calidad de la solución establece nuestro método como un enfoque prometedor para resolver eficazmente instancias de TSP a gran escala.