Groupe d’études et de recherche en analyse des décisions


Less is more: Basic variable neighborhood search for Minimum differential dispersion problem

, et

Large size optimization problems are usually successfully solved by using some metaheuristic approach. Nowadays, there is a trend to combine several metaheuristics into a new hybrid method in order to demonstrate that it is superior to each of its constituents. In this paper, we apply Basic variable neighborhood search for solving Minimum differential dispersion problem using only the Swap neighborhood structure in both descent (intensification) and shaking (diversification) steps. Despite the simplicity of the method, results obtained by our heuristic significantly outperforms the results obtained by a hybrid heuristic that combines GRASP and exterior path relinking rules. This fact confirms that simplicity is not just user friendly desirable property of heuristic, but it could also contribute to get more efficient and effective method than by using complex hybrid metaheuristics.

, 15 pages