In this paper, we suggest DE-VNS as a new heuristic that combines two well known metaheuristic approaches: Differential Evolution (DE) and Variable Neighbourhood Search (VNS), which have, in the last few years, attracted a considerable attention both by academics and practitioners. In our hybrid heuristic, the idea of neighbourhood change is used to estimate the crossover parameter of DE. We propose a family of distributions to be used in order to control the distances among solutions in the search space. Our hybrid heuristic has excellent characteristics, and it comes out that it is more favorable than the recent DE approaches when tested on standard and large instances from the literature.