Robust Milp Formulations for the Two-Stage Weighted Vertex P-Center Problem

The weighted vertex p-center problem (PCP) consists of locating p facilities among a set of available sites such that the maximum weighted distance (or travel time) from any demand node to its closest located facility is minimized. This paper studies the exact solution of the two-stage robust weighted vertex p-center problem (RPCP2). In this problem, the location of the facilities is fixed in the first stage while the demand node allocations are recourse decisions fixed once the uncertainty is revealed. The problem is modeled by box uncertainty sets on both the demands and the distances. We introduce five different robust reformulations based on MILP formulations of (PCP) from the literature. We prove that considering a finite subset of scenarios is sufficient to obtain an optimal solution of (RPCP2). We leverage this result to introduce a column-and-constraint generation algorithm and a branch-and-cut algorithm to efficiently solve this problem optimally. We highlight how these algorithms can also be adapted to solve the single-stage problem (RPCP1) which is obtained when no recourse is considered. We present a numerical study to compare the performances of these formulations on randomly generated instances and on a case study from the literature. © 2023 Elsevier Ltd