MaxMinMin p-dispersion problem: A variable neighborhood search approach |
| |
Affiliation: | 1. ISEG, Universidade de Lisboa, Lisboa, Portugal;2. CMAF-CIO, Universidade de Lisboa, Lisboa, Portugal;3. CEMAPRE, Universidade de Lisboa, Lisboa, Portugal |
| |
Abstract: | 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 ascent and perturbation functions. 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 with 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 demonstrate the strength of the proposed heuristic solution procedures. |
| |
Keywords: | Combinatorial optimization Dispersion problems Metaheuristics Variable Neighborhood Search |
本文献已被 ScienceDirect 等数据库收录! |
|