Extended GRASP-Capacitated K-Means Clustering Algorithm to Establish Humanitarian Support Centers in Large Regions at Risk in Mexico

Abstract EN

Mexico is located within the so-called Fire Belt which makes it susceptible to earthquakes.

In fact, two-thirds of the Mexican territory have a significant seismic risk.

On the other hand, the country’s location in the tropical zone makes it susceptible to hurricanes which are generated in both the Pacific and Atlantic Oceans.

Due to these situations, each year many communities are affected by diverse natural disasters in Mexico and efficient logistic systems are required to provide prompt support.

This work is aimed at providing an efficient metaheuristic to determine the most appropriate location for support centers in the State of Veracruz, which is one of the most affected regions in Mexico.

The metaheuristic is based on the K-Means Clustering (KMC) algorithm which is extended to integrate (a) the associated capacity restrictions of the support centers, (b) a micro Genetic Algorithm μGA to estimate a search interval for the most suitable number of support centers, (c) variable number of assigned elements to centers in order to add flexibility to the assignation task, and (d) random-based decision model to further improve the final assignments.

These extensions on the KMC algorithm led to the GRASP-Capacitated K-Means Clustering (GRASP-CKMC) algorithm which was able to provide very suitable solutions for the establishment of 260 support centers for 3837 communities at risk in Veracruz, Mexico.

Validation of the GRASP-CKMC algorithm was performed with well-known test instances and metaheuristics.

The validation supported its suitability as alternative to standard metaheuristics such as Capacitated K-Means (CKM), Genetic Algorithms (GA), and Variable Neighborhood Search (VNS).