Dispersion problems consist of the selection of a fixed number of vertices from a given set so that some function of the distances among the vertices is maximized. Such problems impose a challenge on heuristic and metaheuristic solution procedures. Among different variations of the dispersion models, the MaxMinMin (p-dispersion) and the MaxSumSum (maximum diversity) problems have been subject of much research, yet the MaxMinSum problem has not been well explored in the literature. In this paper we have developed several heuristics based on the Variable Neighborhood Search metaheuristic framework, including various greedy constructive procedures and different shaking strategies. Finally we discuss the tradeoffs among different solution strategies and compare our results with that of exact methods for smaller sized instances which confirm the high quality of our solutions. To the best of our knowledge this is the first application of any heuristic for the MaxMinSum dispersion problem and the results of our extensive computational experiments on large datasets would set a new benchmark for future comparison purposes.