Metaheuristic algorithms for the induced p-median problem with upgrades

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. In this approach, a larger set of state-of-the-art instances was analysed to ensure a fair comparison with previous proposals. In addition, the characteristics of the instances were studied to assess their complexity. 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.

• Publication year

  2026

• Venue

  Knowledge-Based Systems

• Publication date

  2026-02-01

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1016/j.knosys.2026.115579arXiv 2602.16170
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient heuristics for the obnoxious planar p-median problem with variable sizes

  2025cited by this paper
• Edge downgrades in the maximal covering location problem

  2025cited by this paper
• Multi-armed bandit for the cyclic minimum sitting arrangement problem

  2025cited by this paper
• Facility Location Selection for Ammunition Depots based on GIS and Pythagorean Fuzzy WASPAS

  2024cited by this paper
• A Basic Variable Neighborhood Search for the Planar Obnoxious Facility Location Problem

  2024cited by this paper
• On the automatic generation of metaheuristic algorithms for combinatorial optimization problems

  2024cited by this paper
• On the complexity of the upgrading version of the maximal covering location problem

  2024cited by this paper
• The Discrete <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si35.svg"><mml:mi>p</mml:mi></mml:math>-Center Location Problem with Upgrading

  2023cited by this paper
• An adaptive parallel evolutionary algorithm for solving the uncapacitated facility location problem

  2023cited by this paper
• The p-median problem with upgrading of transportation costs and minimum travel time allocation

  2023influential reference
• A fast and efficient discrete evolutionary algorithm for the uncapacitated facility location problem

  2022cited by this paper
• A distributionally robust optimisation for COVID-19 testing facility territory design and capacity planning

  2022cited by this paper
• A Practical Methodology for Reproducible Experimentation: An Application to the Double-Row Facility Layout Problem

  2022cited by this paper
• Review of obnoxious facilities location problems

  2021cited by this paper
• Strategic oscillation for the balanced minimum sum-of-squares clustering problem

  2021cited by this paper
• A parallel variable neighborhood search approach for the obnoxious p-median problem

  2020cited by this paper
• The planar multiple obnoxious facilities location problem: A Voronoi based heuristic

  2019cited by this paper
• Bayesian performance analysis for black-box optimization benchmarking

  2019cited by this paper
• Metaheuristic Algorithms: A Comprehensive Review

  2018cited by this paper
• Heuristic Solutions to the Facility Location Problem with General Bernoulli Demands

  2017cited by this paper
• Multi-level facility location problems

  2017cited by this paper
• Metaheuristics

  2016cited by this paper
• Facility Layout And Location An Analytical Approach

  2016cited by this paper
• The irace package: Iterated racing for automatic algorithm configuration

  2016cited by this paper
• Optimization by GRASP: Greedy Randomized Adaptive Search Procedures

  2016cited by this paper
• Upgrading p-Median Problem on a Path

  2015influential reference
• Introduction to Location Science

  2015cited by this paper
• Facility location under demand uncertainty: Response to a large-scale bio-terror attack

  2012cited by this paper
• Solving Large p-Median Problems with a Radius Formulation

  2011cited by this paper
• Solving large p-median problems

  2009cited by this paper
• Knapsack Problems

  2008cited by this paper
• Solving the maximal covering location problem with heuristic concentration

  2008cited by this paper
• Solution methods for the p‐median problem: An annotated bibliography

  2006cited by this paper
• The p-median problem: A survey of metaheuristic approaches

  2005cited by this paper
• A Branch-and-Cut Algorithm for the Median-Path Problem

  2005cited by this paper
• A Hybrid Heuristic for the p-Median Problem

  2004cited by this paper
• An Efficient Genetic Algorithm for the p-Median Problem

  2003cited by this paper
• Facility location : applications and theory

  2001cited by this paper
• Cost-distance: two metric network design

  2000cited by this paper
• First vs. best improvement: An empirical study

  1999cited by this paper
• An exact algorithm for the maximal covering problem

  1996cited by this paper
• Greedy Randomized Adaptive Search Procedures

  1995cited by this paper
• A method for solving to optimality uncapacitated location problems

  1990cited by this paper
• An Improved Algorithm for the Capacitated Facility Location Problem

  1978cited by this paper
• AN EXTENSION OF THE GENERALIZED WEBER PROBLEM

  1968cited by this paper
• A Heuristic Program for Locating Warehouses

  1963cited by this paper
• Error detecting and error correcting codes

  1950cited by this paper

• No citing papers are available for this paper.