Placing coffee machines such that everyone is covered

Published April 5, 2026

Background

You own an office and care for your employees. One way in which you care for them is providing coffee access. You'd like the commute to the machine to be at most a two minute walk. This can be simplified to a maximum of a 250 feet radius from any such position in the office.

Data

\[ 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.