The Capacitated $p$-Location Problem with Territorial Coverage Constraints: Efficient Solution and Case Study

Abstract

This paper studies the Capacitated $p$-Location Problem (C$p$LP) and its extensions incorporating equity considerations. In location science, the $p$-Median problem ($p$MP) 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 C$p$LP, which includes the Capacitated $p$-Median Problem (C$p$MP) and its relaxed variant (C$p$MP${}^r$), extends the $p$MP by incorporating capacity constraints on facilities. We formalize the C$p$LP with Territorial Coverage Constraints (C$p$LP-TC), an extension that enforces equity across spatial units, and generalize it to a multi-scale variant (C$p$LP-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 $p$MP, 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.

arXiv comment29 pages, 10 figures