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

DOI

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.

Copyright

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

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  - Proceedings of the 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  - 10.2991/.2013.17
ID  - BernábeLoranca2013/10
ER  -