Traditional clustering algorithms such as KMEANS or HMEANS give poor
results when applied to large data sets with many clusters. A new
metaheuristic, Variable Neighboorhood Search, is applied to large
scale clustering with various criteria: minimum sum of squares,
minimum sum of stars (the p-median problem) and minimum sum of
continuous stars (the multisource Weber problem).  Computational
results on problems with up to several thousand entities is reported
on.