Progress Control in Variable Neighbourhood Search

The methods of intensification and diversification are indispensable in successful meta heuristics for local search. Intensification corresponds in some sense to local optimisation; the neighbourhood of a solution is searched intensively for solutions which are better or have better opportunities. On the other hand, diversification tries to escape from (relatively small) neighbourhoods to solutions which might lead to better final results. A heuristic that is well aware of the intensification versus diversification problems, is the Variable Neighbourhood Search (VNS), see [2]. In this method, more than one neighbourhood structure is considered. After finishing intensification with respect to one neighbourhood, the heuristic diversifies to another neighbourhood. In this way one hopes to escape from poor local optima. In this work we introduce a model to predict the quality of a neighbourhood. We use this model to identify 'bad' neighbourhoods and avoid searching them. We call this process 'Progress Control'. Computational results are presented to show that progress control helps us finding better solutions in the same amount of time.