Application of the dispersion models in order to address the cannibalization phenomenon within franchised chains is a new approach. In this work we have developed a Variable Neighborhood Search (VNS) method in order to solve the MaxMinMin p-dispersion problem, which adds a new type of plateau search mechanism to the classical VNS metaheuristic framework. Besides, several other contributions have been made to the basic VNS heuristic in terms of the descent and perturbation procedures. To the best of our knowledge this is the first application of the VNS to the MaxMinMin problem and our approach, compared to previous methods, finds or improves the results for all of the large-sized benchmarks within a shorter time and low computational efforts. Finding most of the proven optimal solutions in a fraction of a second, the robustness and quality of the solutions and the low complexity of the methods show that the proposed heuristic solution procedure dominates the state-of-the-art algorithms for the MaxMinMin problem.
Published October 2012 , 21 pages