The Less–is–More Approach to Variable Neighborhood Search: A Comparative Study

The less-is-more approach applied to metaheuristic variable neighborhood search combines simplicity and effectiveness in a unique way. With a minimal volume of source code, one can quickly obtain very good solutions. However, the time spent on algorithm implementation may grow significantly on attempts to fit its elementary components, such as, for example, selection of an initial solution, local search moves, or perturbation moves. This study aims to support such a process through a comparison of several possibilities of element composition, including new ideas for elementary moves. The systematic comparative analysis includes 36 versions of this metaheuristic tested on instances of two problems: the traveling salesman one, since it is a model problem commonly used in real-world applications, and that of DNA sequencing, which is a basic and well-studied problem in bioinformatics. The results give basis for conclusions about the compositions of procedures that perform better than others, in the sense of solution quality and computation time.