设施选址问题及其变种

设施选址问题（Facility Location Problem, FLP）是运筹学中的一类经典优化问题：从若干候选位置中选择设施（如仓库、工厂、基站、数据中心、医院等）的最佳位置，使其服务需求的总成本最小，同时满足覆盖、容量等约束。它是整数规划的典型应用，广泛存在于物流、供应链、公共服务、通信网络等领域。

根据目标函数与约束性质的不同，选址问题大致可分为覆盖类、中位类、中心类和成本类四大基本模型，并在此基础上衍生出大量变种。

基本建模框架

不妨设：

• $I=\{1,2,\dots,m\}$：需求点集合，需求点 $i$ 的需求量为 $w_i$；
• $J=\{1,2,\dots,n\}$：候选设施位置集合，设施 $j$ 的建造成本为 $f_j$，容量为 $b_j$；
• $d_{ij}$：需求点 $i$ 到设施 $j$ 的距离（或单位服务成本 $c_{ij}$）。

大多数离散选址问题写成 0-1 整数规划。常用决策变量为：

$$y_j = \begin{cases} 1, & \text{若在候选位置 }j\text{ 建立设施},\\ 0, & \text{否则},\end{cases} \qquad x_{ij} = \begin{cases} 1, & \text{需求点 }i\text{ 被设施 }j\text{ 服务},\\ 0, & \text{否则},\end{cases}$$

覆盖类问题

覆盖类问题基于覆盖半径 $R$ 的概念：若 $d_{ij} \le R$，则称设施 $j$ 能覆盖需求点 $i$。记 $N(i) = \{ j \in J : d_{ij} \le R \}$ 为能覆盖需求点 $i$ 的候选设施集合。

集覆盖问题（SCP）

集覆盖问题要求所有需求点都被至少一个设施覆盖，同时最小化设施建设总成本：

$$\min \sum_{j \in J} f_j y_j$$

$$\text{s.t.} \quad \sum_{j \in N(i)} y_j \ge 1, \quad \forall i \in I$$

$$y_j \in \{0,1\}, \quad \forall j \in J$$

它是一般集覆盖问题在选址背景下的特例，也是整个覆盖类模型的分析基础。

最大覆盖问题（MCLP）

当设施数量固定为 $p$ 时，无法保证所有需求点都被覆盖，因此改为最大化被覆盖的需求总量。设 $z_i \in \{0,1\}$ 表示需求点 $i$ 是否被覆盖：

$$\max \sum_{i \in I} w_i z_i$$

$$\text{s.t.} \quad z_i \le \sum_{j \in N(i)} y_j, \quad \forall i \in I$$

$$\sum_{j \in J} y_j = p$$

$$y_j \in \{0,1\}, \quad z_i \in \{0,1\}, \quad \forall i, j$$

约束 $z_i \le \sum_{j \in N(i)} y_j$ 保证了只有当某个覆盖设施被选中时，需求点才算被覆盖。

中位类问题

中位类问题的目标与设施个数无关地考察需求到最近设施的距离总和。

p-中位问题（p-median）

选择 $p$ 个设施，把每个需求点分配给距离它最近的所选设施，最小化总加权分配距离：

$$\min \sum_{i \in I} \sum_{j \in J} w_{i} d_{ij} x_{ij}$$

$$\text{s.t.} \quad \sum_{j \in J} x_{ij} = 1, \quad \forall i \in I$$

$$x_{ij} \le y_j, \quad \forall i \in I, j \in J$$

$$\sum_{j \in J} y_j = p$$

$$y_j \in \{0,1\}, \quad x_{ij} \in \{0,1\}$$

约束 $\sum_j x_{ij} = 1$ 保证每个需求点恰好分配一个设施，$x_{ij} \le y_j$ 保证只能分配给已建立的设施。p-中位问题在许多场景下有极强的积极性，且可借助概率吸收或积分规划高效求解。

单设施连续选址（Weber 问题）

当不限制候选集合，只选择一个设施的连续位置 $y$ 时，问题退化为 Weber 问题：

$$\min_{y \in \mathbb{R}^2} \; \sum_{i \in I} w_{i} \, \|y - a_i\|$$

其中 $a_i$ 为需求点的坐标。该问题可用迭代的 Weiszfeld 算法（本质是一阶不动点迭代）高效求解，是连续选址分析的起点。

中心类问题

p-中心问题（p-center）

与 p-中位不同，p-中心最小化的是最差情况下的服务距离，即采用 min-max 准则，常用于应急设施、医院等对最坏情形敏感的场景。设 $D$ 为最大服务半径：

$$\min D$$

$$\text{s.t.} \quad \sum_{j \in J} d_{ij} x_{ij} \le D, \quad \forall i \in I$$

$$\sum_{j \in J} x_{ij} = 1, \quad \forall i \in I$$

$$x_{ij} \le y_j, \quad \forall i \in I, j \in J$$

$$\sum_{j \in J} y_j = p$$

三个基本范式可这样对比：p-中位最小化总和、p-中心最小化最大值、覆盖问题则固定覆盖半径而要求所有点被覆盖（SCP）或尽量多地覆盖（MCLP）。

固定设施类：UFLP 与 CFLP

无容量设施选址（UFLP）

当设施的固定建造成本 $f_j$ 与可变动分配成本同时存在、且设施无容量限制时，得到无容量设施选址问题：

$$\min \sum_{j \in J} f_j y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} x_{ij}$$

$$\text{s.t.} \quad \sum_{j \in J} x_{ij} = 1, \quad \forall i \in I$$

$$x_{ij} \le y_j, \quad \forall i \in I, j \in J$$

$$y_j \in \{0,1\}, \quad x_{ij} \ge 0$$

由于目标函数关于 $x$ 是线性的，且可行域满足一定的整体结构，UFLP 中可以把 $x_{ij}$ 松弛为连续非负变量而不改变最优值——每个需求点总会分给相邻的已选设施。

有容量设施选址（CFLP）

为每个设施加入容量约束 $b_j$，需求点 $i$ 的需求量记为 $a_i$：

$$\min \sum_{j \in J} f_j y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} x_{ij}$$

$$\text{s.t.} \quad \sum_{j \in J} x_{ij} = 1, \quad \forall i \in I$$

$$\sum_{i \in I} a_i x_{ij} \le b_j y_j, \quad \forall j \in J$$

$$y_j \in \{0,1\}, \quad x_{ij} \ge 0$$

容量约束使得问题从线性规划范畴变成典型的混合整数规划，求解难度相比 UFLP 大幅上升。

重要变种

动态与多期选址

考虑规划周期的特征，设施可在多期规划中被建设、扩建或关闭。通常引入时间维的 $y_{jt}$，并将建设、持有、关闭成本与跨期需求一起纳入目标。

随机与鲁棒选址

当需求 $w_i$ 不确定时，在随机规划框架下，第一阶段的"建哪些设施"决策需在观测需求之前做出（here-and-now），第二阶段的分配决策在需求实现后做出（wait-and-see），目标取需求分布的期望。鲁棒选址则用最坏情形的需求场景或区间刻画不确定性。

枢纽选址（Hub Location）

在航空、快递和多对多通信网络中，货物并不直达每个点对，而是经枢纽中转。Hub 问题同时决定枢纽的位置及其分配关系，且枢纽间常有换乘折扣，目标是在完全连通的网络上优化中转网络的总成本。

多目标与公平性选址

现实中常需在总成本与服务水平（覆盖比例、最大半径）或公平性（最大分担距离、方差）之间权衡，构成多目标选址问题，其解往往是一条 Pareto 前沿曲线。

求解方法论概述

• 精确方法：将经典选址问题建模为整数规划，用分支定界、分支割平面或商业求解器直接求解；对特殊结构（如覆盖问题）常配合集划分与列生成以获得线性规划松弛的下界。
• 元启发式算法：当规模较大时，使用贪婪、局部搜索、禁忌搜索、模拟退火、遗传算法等求解近似最优解。
• 松弛方法：对 p-中位、UFLP 等配上拉格朗日松弛或线性规划松弛，可快速得到高质量的上下界并指导分支限定。

小结

设施选址问题以覆盖、中位、中心、固定成本四大基本模型为骨架，覆盖了对服务半径、分配距离、公平性和成本的不同考量。实际工程中很少直接套用标准模型，而是在这些基本模型之上叠加容量、多期、不确定性或网络结构演化出丰富的变种。这对运筹优化、整数规划与算法设计的能力提出了综合要求，也是车辆路径、公共设施布局与供应链网络设计等周边问题的共同基石。