A variable neighborhood search for the median location problem with interconnected facilities

Abstract

The p-median problem has been widely studied in the literature. However, there are several variants that include new constraints to the classical problem that make it more realistic. In this work, we study the variant that considers interconnected facilities, that is, the distances between each pair of facilities are less than or equal to a certain threshold r. This optimization problem, usually known as the median location problem with interconnected facilities, consists of locating a set of interconnected facilities to minimize the distance between those interconnected facilities and the demand points. The large variety of real-world applications that fit into this model makes it attractive to design an algorithm able to solve the problem efficiently. To this end, a procedure based on the variable neighborhood search methodology is designed and implemented by using problem-dependent neighborhoods. Experimental results show that our proposal is able to reach most of the optimal solutions when they are known. Additionally, it outperforms previous state-of-the-art methods in those instances where the optima are unknown. These results are further confirmed by conducting nonparametrical statistical tests.

Isaac Lozano-Osorio

Phd in Artificial Intelligence

Isaac Lozano graduated with a double degree in Computer Engineering and Computer Engineering from the Universidad Rey Juan Carlos, where he was awarded the prize for the Best Final Project. Subsequently, he completed a Master in Artificial Intelligence Research (UIMP). His main research interests are focused on the interface between Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristic procedures for graph modeled optimization problems.

Jesús Sánchez-Oro

Associate Professor

Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.

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.