In this work we study the p-median problem with maximum distance constraints (PMPDC) which is a variant of the classical p-median problem (PMP). First of all, we provide some different formulations for (PMPDC) because the heuristics procedures for the (PMPDC) with a formulation based on the approach that modifies the distance matrix that leads to dif- ficulties and frequently infeasible solutions. Different heuristic procedures for the (PMPDC) problem are developed. First, a new Lagrangian relaxation algorithm, which differs from those existing in the literature, is developed. Second, we apply a new approach, based on the GRASP methodology ad- dapted to (PMPDC) from (PMP). In addition, we study in depth the rela- tion between the feasibility of (PMPDC) and the parameters p and maximum distance limits, providing an analytic-geometric characterization. Finally, we develop a new resolution methodology to solve a bi-objective problem of in- terest in facility location and healthcare optimization, the p-median-center tradeoff problem, finding all the points on the Pareto front very quickly.
Citation
Some heuristic methods for the p-median problem with maximum distance constraints. Application to a bi-objective problem, Esteban-Pérez A., Sáez-Aguado J. and San-José, Luis A.,technical report, Universidad de Málaga,February/2020.