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.
Alberto Herrán González
Profesor Titular de Universidad
J. Manuel Colmenar
Profesor Titular de Universidad
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
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.