2026/07/28 by Felipe Albuquerque, Rosa Figueiredo, Cyrille Genre-Grandpierre
#math.OC #cs.DM
This paper studies the Capacitated p-Location Problem (CpLP) and its extensions incorporating equity considerations. In location science, the p-Median problem (pMP) is a classical model that selects p facilities from a finite set of candidates to serve a set of customers while minimizing total allocation costs. The CpLP, which includes the Capacitated p-Median Problem (CpMP) and its relaxed variant (CpMPr), extends the pMP by incorporating capacity constraints on facilities. We formalize the CpLP with Territorial Coverage Constraints (CpLP-TC), an extension that enforces equity across spatial units, and generalize it to a multi-scale variant (CpLP-MTC) that enforces equity simultaneously across nested spatial scales. We present a strengthened Integer Linear Programming (ILP) formulation with valid inequalities that enables the exact solution of medium-sized instances. To tackle larger problems, we adapt the Random Sampling Spatial Voting (RSSV) heuristic, originally proposed for the pMP, into a competitive open-source matheuristic that combines a heuristic reduction phase with the strengthened ILP formulation. The resulting method remains flexible, requires minimal parameter tuning, and is accessible to non-specialist users.Computational experiments on a new open-source benchmark instance set, built from a French regional case study, demonstrate the effectiveness of both the exact and heuristic approaches. Beyond their computational performance, the results quantify the trade-offs between efficiency and territorial equity under different equity constraints, providing practical insights for equitable location planning.