Healthcare Facility Location with the p-Median Model

Published 2026-02-11

Background

The p-median problem is a classic discrete location model. Its objective is to locate \(p\) facilities to minimize the total weighted travel distance between demand nodes and their assigned facilities.

Problem Data

We consider five villages (\(V_1\) to \(V_5\)) with specific populations (weights \(w_i\)) and a distance matrix \(d_{ij}\).

\[ d_{ij} = \begin{bmatrix} 0 & 10 & 25 & 30 & 45 \\ 10 & 0 & 15 & 20 & 35 \\ 25 & 15 & 0 & 10 & 20 \\ 30 & 20 & 10 & 0 & 15 \\ 45 & 35 & 20 & 15 & 0 \end{bmatrix} \qquad w_{i} = \begin{bmatrix} 100 \\ 500 \\ 200 \\ 100 \\ 300 \end{bmatrix} \]

Mathematical Model

Let \(y_j\) be 1 if a facility is built at site \(j\), and \(x_{ij}\) be 1 if village \(i\) is assigned to facility \(j\).

\[ \begin{align} \min \quad & Z = \sum_{i \in V} \sum_{j \in V} w_i d_{ij} x_{ij} \\ \text{s.t.}\quad & \sum_{j \in V} x_{ij} = 1 && \forall i \in V \\ & x_{ij} \le y_j && \forall i, j \in V \\ & \sum_{j \in V} y_j = p \\ & x_{ij}, y_j \in \{0,1\} && \forall i, j \in V \end{align} \]

Python Implementation

Using the PuLP library to solve for \(p = 2\):


import pulp as pl

# Define indices and parameters
V = range(5)
w = [100, 500, 200, 100, 300]
d = [
    [0, 10, 25, 30, 45],
    [10, 0, 15, 20, 35],
    [25, 15, 0, 10, 20],
    [30, 20, 10, 0, 15],
    [45, 35, 20, 15, 0]
]
p = 2

# Define Model
model = pl.LpProblem("p-Median", pl.LpMinimize)

# Decision Variables
y = pl.LpVariable.dicts("y", V, cat='Binary')
x = pl.LpVariable.dicts("x", (V, V), cat='Binary')

# Objective Function
model += pl.lpSum(w[i] * d[i][j] * x[i][j] for i in V for j in V)

# Constraints
for i in V:
    model += pl.lpSum(x[i][j] for j in V) == 1
    for j in V:
        model += x[i][j] <= y[j]

model += pl.lpSum(y[j] for j in V) == p

model.solve()

Results

this is a tets

Discussion

By assigning higher weights to \(V_2\) (population 500), the model is heavily incentivized to place a facility at that location to reduce the weighted distance to zero for that node. This demonstrates how the p-median model prioritizes accessibility for larger population centers.