设施选址与覆盖模型

设施选址研究在有限的候选位置中设置多少个服务点、服务谁以及怎样评价服务质量。消防站希望最远到达时间不要太长，配送仓库可能更关心总运距，疫苗点还要考虑容量。这些目标不能用一个未经说明的“最佳位置”混在一起。

同一组地点，三种答案

考虑沿公路分布的三个需求点 $A, B, C$ ，位置为 $0, 4, 10$ 千米，每日需求量分别是 $5, 2, 3$ 单位。允许在 $0, 5, 10$ 千米三处择一建站，暂以公路距离近似行车距离。对每个候选地，逐点算距离和需求加权总距离：

建站位置	到 $A, B, C$ 的距离（千米）	需求加权距离	最远距离
0	$0, 4, 10$	$5 (0) + 2 (4) + 3 (10) = 38$	10
5	$5, 1, 5$	$5 (5) + 2 (1) + 3 (5) = 42$	5
10	$10, 6, 0$	$5 (10) + 2 (6) + 3 (0) = 62$	10

所以使平均服务距离最小的站点在零千米；使最远距离最小的站点在五千米。若服务半径定为四千米，零千米站可覆盖 $A, B$ ，合计需求七；五千米站只覆盖 $B$ ，需求二；十千米站只覆盖 $C$ ，需求三。最大覆盖又选零千米。图上五千米站位于 $A$ 和 $C$ 之间，却超出了四千米覆盖半径，说明“居中”不等于满足既定时限。

一条从零到十千米的道路上有三个需求点A、B、C和位于五千米的候选站；需求量分别为五、二、三，标出了零、四、五、十千米 — 同一条路可产生不同的最优站址，取决于总距离、最远距离还是覆盖量。

选址—指派的整数模型

令 $I$ 是需求点集合， $J$ 是候选设施集合， $d_{i j}$ 为从需求点 $i$ 到设施 $j$ 的行车距离或预计时间， $w_{i} \geq 0$ 为需求权重。设二元变量 $y_{j} = 1$ 表示开设设施 $j$ ， $x_{i j} = 1$ 表示需求点 $i$ 指派给 $j$ 。预算恰好开 $p$ 处时， $p$ -中位点模型为 $min \sum_{i \in I} \sum_{j \in J} w_{i} d_{i j} x_{i j}$ $\sum_{j} x_{i j} = 1 (i \in I), x_{i j} \leq y_{j}, \sum_{j} y_{j} = p, x_{i j}, y_{j} \in {0, 1} .$ 第一个约束让每个需求点恰好有一个服务点；第二个阻止指派到关闭的站。若 $d_{i j}$ 是千米、 $w_{i}$ 是每日服务次数，目标单位就是“次·千米／日”。如果站有容量 $K_{j}$ ，还需 $\sum_{i} w_{i} x_{i j} \leq K_{j} y_{j}$ ；没有容量约束的解不保证能在营业时间内完成服务。

若要控制最坏响应距离，在上述指派约束下增设 $t \geq d_{i j} x_{i j}$ 对所有 $i, j$ ，并最小化 $t$ ，得到离散 $p$ -中心模型。在所有需求点都被指派的前提下， $t$ 至少等于各实际指派距离的最大值；而最小化会把它压到这个最大值。若优先考虑某类脆弱人群的时限，可以对相应 $i$ 另加 $\sum_{j} d_{i j} x_{i j} \leq T_{i}$ ，不必把所有公平要求藏进一个权重。

最大覆盖与最小覆盖

给定服务时限 $R$ ，定义 $N_{i} = {j : d_{i j} \leq R}$ 。令 $z_{i} = 1$ 表示需求点被服务半径覆盖。固定开站数 $p$ 的最大覆盖模型为 $max \sum_{i} w_{i} z_{i}, z_{i} \leq \sum_{j \in N_{i}} y_{j}, \sum_{j} y_{j} \leq p, z_{i}, y_{j} \in {0, 1} .$ 目标权重非负时，只要附近有站，最优解会令 $z_{i} = 1$ 。若要求全部需求都覆盖，并希望开站成本最少，改为 $min \sum_{j} c_{j} y_{j}$ ，条件 $\sum_{j \in N_{i}} y_{j} \geq 1$ 对每个 $i$ 成立；这就是集合覆盖式选址。如果某个 $N_{i}$ 为空，全部覆盖模型根本无可行解，必须先补候选点或放宽时限。

从地图到可靠决策

距离矩阵应按道路方向、速度限制、拥堵时段和实际入口计算；跨河的欧氏距离虽短，驾车时间却可能长得多。将区域压成少量需求点会掩盖街区内部差异，尤其影响边界居民。建站成本、需求预测与道路阻断有不确定性时，至少比较多个时段和故障情景，并报告最坏响应、未覆盖人口、利用率以及迁址后的变化。求解器返回一个整数方案后，逐个核对开站数、指派关系、容量与覆盖半径；模型目标值本身不能证明现实中的响应时间达标。

参考资料与相关词条