P中心问题

p中心问题（p-center problem）从候选地点选出 $p$ 个服务设施，使所有需求点到最近设施的距离中的最大值最小。这个最大距离称为服务半径；它适合关心最偏远点的急救站、应急物资点或通信覆盖模型。这里的距离也可以替换为经过道路网计算的行驶时间，但必须对所有点统一单位。^[1]

设公路上的需求点和候选点都是零、二、五、九千米，不限每站服务容量。只建一站时，四种位置的最远距离分别为九、七、五、九，因此选位置五，最优半径五。它和加权距离和最小的p中位问题可以选择不同站址：优化最坏情况与优化总体代价是两种不同标准。

最大距离的模型

记需求集 $I$ 、候选集 $J$ ，距离为 $d_{i j} \geq 0$ 。直接的集合形式为 $r_{*} = min_{S \subseteq J, | S | = p} max_{i \in I} min_{j \in S} d_{i j} .$ 内层先为每个客户找最近设施，外层最大值再找服务最差的客户。次序不能互换；先找一个统一最近的站，描述的是另一个问题。

也可以令二元变量 $x_{i j}$ 表示分配、 $y_{j}$ 表示开站，增加连续变量 $r \geq 0$ ，最小化 $r$ ，满足 $\begin{matrix} \sum_{j} x_{i j} & = 1, x_{i j} \leq y_{j}, \\ \sum_{j} y_{j} & = p, \sum_{j} d_{i j} x_{i j} \leq r (i \in I) . \end{matrix}$ 每个客户只分配到一个开站，因此最后一式恰好把实际分配距离压在半径内。无容量限制时，给定站址可以一律分配给最近站。

给定半径的覆盖判定

试验某个半径 $r$ ，对每个客户只允许连接满足 $d_{i j} \leq r$ 的候选点。此时是否存在不超过 $p$ 个设施覆盖全部客户，等价于是否能在该半径内服务全部客户： $\begin{matrix} \sum_{j : d_{i j} \leq r} y_{j} & \geq 1 (i \in I), \\ \sum_{j} y_{j} & \leq p, y_{j} \in {0, 1} . \end{matrix}$ 从半径内的方案出发，其开站集合必覆盖每个客户，证明必要性；从一个覆盖集合出发，各客户选择一处覆盖自己的站，则构成半径内分配，证明充分性。在 $p \leq | J |$ 且开站没有负面限制时，可补开闲置站，使“不超过”变成“恰好”。

两个中心在2与9，半径3覆盖0,2,5,9；若半径小于3，中间点与两端无法由两处候选中心同时覆盖 — 半径三时，站二覆盖0、2、5，站九覆盖9。图中高低两条覆盖带只为区分设施，不表示第二个空间维度。

两站主例中，选二、九的最近距离为二、零、三、零，半径三。若半径严格小于三，客户九只能由候选九覆盖；剩下一个站必须同时覆盖零、二、五。但候选零到五距离五，候选二到五距离三，候选五到零距离五，候选九更远，没有可选站。因此半径三既可行又不可再缩小。

有限距离矩阵的最优半径必为其中某个距离值。把不同距离排序后，可对“能否覆盖”这个单调判定做二分搜索：在半径 $r$ 已能覆盖时，更大半径也能覆盖。不过每次覆盖判定自身仍可能是困难的整数规划；二分减少试探次数，并未消除组合复杂性。

小规模核对

Python 3

from itertools import combinations
import math

def p_center(distance, p):
    d = tuple(tuple(row) for row in distance)
    if not d or not d[0]:
        raise ValueError("nonempty data required")
    m = len(d[0])
    if any(len(row) != m for row in d) or type(p) is not int or not 1 <= p <= m:
        raise ValueError("rectangular matrix and valid p required")
    if any(not math.isfinite(v) or v < 0 for row in d for v in row):
        raise ValueError("finite nonnegative distances required")
    return min((max(min(row[j] for j in s) for row in d), s)
               for s in combinations(range(m), p))

a = [0,2,5,9]
d = [[abs(x-y) for y in a] for x in a]
print(p_center(d, 2))
# (3, (1, 3))

程序枚举所有设施集合，每次确切计算最大最近距离，故取到的最小值为全局最优；时间为 $O ((\binom{m}{p}) n p)$ ，不需要把距离先四舍五入。设施数达到候选点数时，仍应按客户是否也位于候选点判断半径能否为零。

变式。 若一站可在整条公路连续选址，最左零与最右九的距离和固定为九，故最大值至少为四点五；建在四点五恰好达到。离散站址主例的五因此不能用于连续站址问题。若某些道路是单行线，距离可以非对称，有限候选模型仍成立，但许多依赖对称度量的近似保证不再自动适用。

参考文献

↑ João Pedro Pedroso、Abdur Rais、Mikio Kubo、Masakazu Muramatsu，Mathematical Optimization: Solving Problems using SCIP and Python，The k-Center Problem及The k-Cover Problem：最大最近距离与覆盖判定。

[1] João Pedro Pedroso、Abdur Rais、Mikio Kubo、Masakazu Muramatsu，Mathematical Optimization: Solving Problems using SCIP and Python，The k-Center Problem及The k-Cover Problem：最大最近距离与覆盖判定。

[1]