El problema de k-means es uno de los modelos más populares en el análisis de grupos que minimiza la suma de las distancias al cuadrado de los objetos agrupados a los centros de clúster buscados (centroides). La simplicidad de su implementación algorítmica alienta a los investigadores a aplicarlo en una variedad de ramas de la ingeniería y la ciencia. Sin embargo, se ha demostrado que el problema es NP-duro, lo que hace que los algoritmos exactos sean inaplicables para problemas a gran escala, y los algoritmos más simples y populares resultan en valores muy pobres de la suma de las distancias al cuadrado. Si un problema debe resolverse en un tiempo limitado con la máxima precisión, lo cual sería difícil de mejorar utilizando métodos conocidos sin aumentar los costos computacionales, los algoritmos de búsqueda de vecindario variable (VNS), que buscan en vecindarios aleatorios formados por la aplicación de procedimientos aglomerativos codiciosos, son competitivos. En este artículo, investigamos la influencia del parámetro más importante de dichos vecindarios en la eficiencia computacional y proponemos un nuevo algoritmo (solucionador) basado en VNS, implementado en la unidad de procesamiento gráfico (GPU), que ajusta este parámetro. La evaluación comparativa en conjuntos de datos compuestos por hasta millones de objetos demuestra la ventaja del nuevo algoritmo en comparación con los conocidos algoritmos de búsqueda local, dentro de un tiempo fijo, permitiendo la computación en línea.