A parallel variable neighborhood search approach for the obnoxious p-median problem

Resumen

The obnoxious p-median problem consists of selecting p locations, considered facilities, in a way that the sum of the distances from each nonfacility location, called customers, to its nearest facility is maximized. This is an urn:x-wiley:09696016:media:itor12510:itor12510-math-0001-hard problem that can be formulated as an integer linear program. In this paper, we propose the application of a variable neighborhood search (VNS) method to effectively tackle this problem. First, we develop new and fast local search procedures to be integrated into the basic VNS methodology. Then, some parameters of the algorithm are tuned in order to improve its performance. The best VNS variant is parallelized and compared with the best previous methods, namely branch and cut, tabu search, and GRASP over a wide set of instances. Experimental results show that the proposed VNS outperforms previous methods in the state of the art. This fact is finally confirmed by conducting nonparametric statistical tests.

Publicación
International Transactions in Operational Research
Alberto Herrán González
Alberto Herrán González
Profesor Contratado Doctor
J. Manuel Colmenar
J. Manuel Colmenar
Artificial Intelligence Professor

Mis intereses de investigación se centran en las metaheurísticas aplicadas a problemas de optimización. He trabajado en diferentes problemas de optimización combinatoria aplicando algoritmos trajectoriales como GRASP o VNS. Además, estoy muy interesado en las aplicaciones de la Evolución Gramatical, específicamente en el dominio de los modelos y la predicción, como alternativa a los enfoques de aprendizaje automático.

Abraham Duarte
Abraham Duarte
Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.