Abstract
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
Associate Professor
J. Manuel Colmenar
Full Professor
My research interests are focused on metaheuristics applied to optimization problems. I have worked on different combinatorial optimization problems applying trajectorial algorithms such us GRASP or VNS. Besides, I am very interested in applications of Grammatical Evolution, specifically in model and prediction domain, as alternative to machine learning approaches.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.