ENHANCED META-HEURISTICS WITH VARIABLE NEIGHBORHOOD SEARCH STRATEGY FOR COMBINATORIAL OPTIMIZATION PROBLEMS

Variable neighborhood search (VNS) is a simple meta-heuristic that systematically changes the size and type of neighborhood during the search process in order to escape from local optima. In this paper, enhanced versions of tabu search and memetic algorithm with variable neighborhood search for combinatorial optimization problems are introduced. The set of constructed neighborhoods satisfies the property that each small neighborhood is a subset of a larger one. Most of the work published earlier on VNS starts from the first neighborhood and moves on to higher neighborhoods without controlling and adapting the ordering of neighborhood structures. The order in which the neighborhood structures have been selected in this paper during the search process offers a better mechanism for performing diversification and intensification. A set of industrial and random problems is used to test the effectiveness of the two enhanced meta-heuristics using the maximum satisfying problem as a test case.