  In this paper we propose an efficient solution for the problem of generating
k-labeling forest VNS. This problem is an extension of the Minimum Spanning
Tree Problem Labelling problem with important applications in
telecommunications networks and multimodal transport. It is, given an
undirected graph whose links are labeled, and an integer positive number k,
find the spanning forest with the lowest number of connected components using
at most k different labels. To address the problem a Basic Variable
Neighbourhood Search is proposed where the maximum amplitude of the
neighbourhood space, n, is a key parameter. Different strategies are studied to
establish the value of n. BVNS with the best selected strategy is
experimentally compared with other metaheuristics that have appeared in the
literature applied to this type of problem.
