A Variable Neighborhood Search approach for the Hamiltonian p-median problem

Resumen

The Hamiltonian -Median Problem (HpMP) is a generalization of the well-known Traveling Salesman Problem (TSP), where the goal is to find non-intersecting cycles in an undirected graph, minimizing the total sum of the costs of those cycles. The HpMP has actual applications such as laser multi-scanner problems, school locations, depot locations, or leather cutting problems, among others. Despite these relevant applications, HpMP problem has been mainly approached by considering an exact perspective, where they only solve small or medium instances in a moderate computing time. In this paper, we propose a parallel General Variable Neighborhood Search (GVNS) procedure to effectively and efficiently solve the HpMP. The computational experiments section firstly tunes the parameters of the algorithm and studies the influence of the proposed strategies. Then, the best variant is compared with the current state-of-the-art methods over the same set of instances. The obtained results show the superiority of the proposal in both, objective function value and computing time. These results are finally confirmed by conducting non-parametric statistical tests.

Publicación
Applied Soft Computing
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.