TopIntroduction
Many problems within the Combinatorial Optimization area considered as NP-Complete problems (Papadimitriou & Steiglitz, 1998) require the use of heuristics to obtain high-quality solutions, due to their complexity and nature. One of the most frequently used is local search. It starts with an initial solution then applies a sequence of local changes in attempt to improve the value of the objective function and obtain the local optima. The types of movements applied in local searches are called neighborhood functions or neighborhood structures because they access to neighboring solutions and define the size of the neighborhood.
Sometimes the use of a sole heuristic is not enough to find good solutions for hard problems, because the solution space is very complex. In such cases, the variable neighborhood structures have demonstrated being efficient search methods for these problems.
This article presents two important optimization problems undertaken by different neighborhood structures, the Classical Symmetric Travelling Salesman Problem (CSTSP), and the Unrelated Parallel Machines Problem (UPMP).
An analysis of efficacy and efficiency is performed to identify the best neighborhood structure for each problem before its implementation within a heuristic or metaheuristic, such as Iterated Local Search, Tabu Search (Michaelewicz & Fogel, 2000), Memetic Algorithms (Cruz et al., 2008), Ant Colony (Alba, 2005), among others. The hybridization using heuristics and local search has been shown to be more efficient and effective in searching for solutions to NP problems than the heuristic alone.
There is some research in the literature about variable neighborhood search, as they are referred to in this article. Arajy y Abdullah (2010a) present a two-phase hybrid approach; the structure combines a variable neighborhood search (VNS) in the first-phase with an iterated local search in the second-phase, while always accepting the best solutions. The VNS involves 13 different neighborhood structures, which are randomly selected during execution. Experimental results show the algorithm is competitive with other approaches in literature. For nine data sets, it obtained one improved and eight equal solutions.
In (Hansen & Mladenović, 1999) a VNS implemented in a local search algorithm is presented. In addition, some modifications of this approach are explained. Variants of VNS were tested in five problems: Travelling Salesman Problem (TSP), p-median Problem (PM), Multi-source Weber Problem (MW), Minimum Sum-of-squares Clustering Problem (MSSCC), and Bilinear Programming Problem with Bilinear Constraints (BBLP), showing competitive results especially for the PM and MW problems. In (Arajy & Abdullah, 2010b) a VNS is presented in the first-phase, with an iterated local search in the second-phase for the Attribute Reduction in Rough Set Theory. The approach was tested in over 13 well-known datasets. Experimental results demonstrate that the VNS was able to produce solutions competitive with the best techniques.
This research was motivated by the continuous need to find high-quality solutions for important combinatorial problems; such as TSP and UPMP, because in Metaheuristics, the local search is the most time-consuming procedure. Therefore, in this research a VNS is applied to an NP and an NP-Complete problem to observe its performance in different complexity problems, under the same conditions.
Experimental results show that the good performance of a VNS depends on the search space complexity of the problem. High-quality solutions are obtained for CSTSP (classified as NP-Complete problem), but poor-quality solutions for UPMP (a less complex NP problem). Although in most cases VNS produce very good solutions, the results show that this is not a rule for all discrete optimization problems. The contribution of this research is the finding that the performance of local search depends on the hardness of the problem. Contrary to what one might expect, the performance only is better for the NP-complete problem than for the NP problem, both studied in this article.
This article is organized as follows. Section two presents an introduction to the complexity problems undertaken, which are the CSTSP and the UPMP. Section four describes the neighborhood structures tested in this research. Section five details the proposed VNS and the experimental tests. Section six explains the statistical analysis of the obtained results for each structure. Finally, section seven presents conclusions.