Abstract
Facility location problems (FLPs) are a family of optimisation problems with significant social impact. This class of problems has been the subject of study since the 1960s, with classical approaches including the Weber problem and the p-Median problem. Currently, more complex variations of these problems are being investigated. In particular, the Induced p-Median Problem with Upgrades (IpMU) represents a variation of the classical p-Median problem, where the concepts of transport cost and time are separated as distinct metrics in the input graph of the problem. Furthermore, the problem includes a budget which allows one to relax the graph costs, reducing the cost of the edges, thus improving the associated routes between the designated medians and the customers. In this study, a metaheuristic algorithm, based on the Greedy Randomized Adaptive Search Procedure (GRASP), is proposed. A two-phase resolution scheme is defined, studying the median problem and the upgrading problem independently. The results obtained are promising when compared to the state-of-the-art, which is based entirely on mathematical programming models. The execution time was improved on average by two orders of magnitude for the harder instances, and the best known result was obtained in more than 99% of the tested instances.
Sergio Salazar
Artificial Intelligence Phd Student
Sergio Salazar graduated in Mathematics and Computer Science from the Rey Juan Carlos University in 2023. He is working here as a predoctoral researcher focusing in Continious Facilities Location Problems.
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.
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.