Proceedings of the Fourth International Workshop on Knowledge Discovery, Knowledge Management and Decision Support

Simulated Annealing and Variable Neighborhood Search Hybrid Metaheuristic for the Geographic Clustering Simulated Annealing and Variable Neighborhood Search Hybrid Metaheuristic for the Geographic Clustering Simulated Annealing and Variable Neighborhood Search Hybrid Metaheuristic for the Geographic

Authors
María Beatríz Bernábe Loranca, David Pinto Avendaño, Elias Olivares Benitez, Javier Ramírez Rodríguez, José Luis Martínez Flores
Corresponding Author
María Beatríz Bernábe Loranca
Available Online October 2013.
DOI
https://doi.org/10.2991/.2013.17How to use a DOI?
Keywords
Clustering, Dunn, Simulated Annealing, Var-iable Neighborhood Search, Hybrid Metaheuristic
Abstract
In this work we present a new hybrid approach for solv-ing the clustering problem for geographic data, which is known to be NP-hard. Two metaheuristics that have prov-en efficiency in combinatory optimization problems have been chosen for the comparison: Simulated Annealing (SA) and Variable Neighborhood Search (VNS). The proposed model is based on the partitioning around the medoids and on P-median. Previous test runs have shown satisfactory results (in terms of quality and time) for in-stances of 469 geographic objects, but when instances of greater size are used then variability in the results has been detected. In an effort to achieve better results for the clustering problem, we have incorporated a hybridization of simu-lated annealing and variable neighborhood search to the geographic clustering problem. We have considered dif-ferent sizes in the tests runs for distinct groups observing that the solutions obtained with the hybrid approach, named SA-VNS hybrid, overcome SA and VNS when they have been implemented individually. Finally, with the aim of evaluating the benefits of the me-ta-heuristic proposed, we have measured the internal con-nection of the obtained clusters by means of the Dunn In-dex. The results obtained show that the hybrid SA-VNS performs better than SA and VNS with respect to the compactness feature.
Open Access
This is an open access article distributed under the CC BY-NC license.

Download article (PDF)

Proceedings
Fourth International Workshop on Knowledge Discovery, Knowledge Management and Decision Support
Part of series
Advances in Intelligent Systems Research
Publication Date
October 2013
ISBN
978-90-78677-86-4
ISSN
1951-6851
DOI
https://doi.org/10.2991/.2013.17How to use a DOI?
Open Access
This is an open access article distributed under the CC BY-NC license.

Cite this article

TY  - CONF
AU  - María Beatríz Bernábe Loranca
AU  - David Pinto Avendaño
AU  - Elias Olivares Benitez
AU  - Javier Ramírez Rodríguez
AU  - José Luis Martínez Flores
PY  - 2013/10
DA  - 2013/10
TI  - Simulated Annealing and Variable Neighborhood Search Hybrid Metaheuristic for the Geographic Clustering Simulated Annealing and Variable Neighborhood Search Hybrid Metaheuristic for the Geographic Clustering Simulated Annealing and Variable Neighborhood Search Hybrid Metaheuristic for the Geographic
BT  - Fourth International Workshop on Knowledge Discovery, Knowledge Management and Decision Support
PB  - Atlantis Press
SP  - 140
EP  - 147
SN  - 1951-6851
UR  - https://doi.org/10.2991/.2013.17
DO  - https://doi.org/10.2991/.2013.17
ID  - BernábeLoranca2013/10
ER  -