4. 离散选址模型

离散选址问题假定候选设施点已经给定（例如若干可租用的仓库、可布设的基站站址、可开设的配送站），决策变量是"选哪些点、如何分配需求"。与连续选址（可在平面上任意取点）不同，离散模型天然贴近工程实际：土地、道路、审批、既有设施都限制了可选位置。本节围绕集合覆盖、最大覆盖、p-中值、p-中心四个模型，讲清它们各自"优化什么、约束什么、什么时候用"。

一、四个模型的形式化

统一记号：候选设施集合 J = {1,…,m}，需求点集合 I = {1,…,n}，d_ij 为需求点 i 到候选点 j 的距离（或时间），a_ij = 1 表示 j 能在阈值 D 内覆盖 i。决策变量 x_j ∈ {0,1} 表示是否在 j 建站，y_ij ∈ {0,1} 表示 i 是否由 j 服务。

集合覆盖模型（Set Covering, SCLP）：要求每个需求点至少被一个已建设施覆盖，目标是最小化建设数量或总建设成本。

min  Σ_j c_j · x_j
s.t. Σ_{j: a_ij=1} x_j ≥ 1      ∀ i ∈ I
     x_j ∈ {0,1}

它回答的是"最少建几个、建在哪，才能让所有需求点都被服务到"。约束是硬性的全覆盖，因此当预算紧张、需求点又分散时，模型可能无可行解或成本极高。

最大覆盖模型（Maximal Covering, MCLP）：给定设施数量上限 p，最大化被覆盖的需求量（按人口或订单加权）。

max  Σ_i w_i · z_i
s.t. z_i ≤ Σ_{j: a_ij=1} x_j     ∀ i
     Σ_j x_j ≤ p
     z_i, x_j ∈ {0,1}

其中 w_i 为需求权重，z_i 表示 i 是否被覆盖。它把"全覆盖"放宽为"在 p 个设施下覆盖尽可能多"，是预算受限时最常用的模型。

p-中值模型（p-Median）：给定 p 个设施，最小化需求加权总出行距离。

min  Σ_i Σ_j w_i · d_ij · y_ij
s.t. Σ_j y_ij = 1                ∀ i
     y_ij ≤ x_j                  ∀ i,j
     Σ_j x_j = p
     y_ij, x_j ∈ {0,1}

它关注"平均效率"，适合配送中心、快递网点这类以运输成本为主要考量的设施。

p-中心模型（p-Center）：给定 p 个设施，最小化任意需求点到其最近设施的最大距离，即最小化最坏服务半径 R。

min  R
s.t. Σ_j d_ij · y_ij ≤ R         ∀ i
     Σ_j y_ij = 1                ∀ i
     y_ij ≤ x_j                  ∀ i,j
     Σ_j x_j = p

它关注"公平性与最坏情况"，适合急救站、消防站、应急物资点等对响应时间上限有硬要求的场景。

二、用一个教学示例看清差异

假设某城区有 8 个需求点，权重（万单/月）分别为 3、2、4、1、5、2、3、2，候选设施点 5 个，覆盖阈值 D = 3 km，距离矩阵已给定（此处为合理假设的示例数据）。

• 若用集合覆盖，求得最少需 2 个设施即可覆盖全部 8 点，总建设成本最低；但若预算只允许 1 个，则模型无可行解。
• 若用最大覆盖且 p = 1，模型会选择能覆盖权重总和最大的那个候选点，例如覆盖权重 3+4+5+2 = 14 万单，剩余 3 个点（权重合计 6）不被覆盖——这是"可接受的牺牲"。
• 若用 p-中值且 p = 2，模型会选使加权总距离最小的组合，结果可能偏向需求密集区，边缘点距离较远但总成本最优。
• 若用 p-中心且 p = 2，模型会选使最大距离最小的组合，可能把设施放在更"居中"的位置，牺牲总距离换取最远点不超过 2.4 km。

三、求解与实现要点

四个模型都是 0-1 整数规划。小规模（m ≤ 50）可直接用求解器（如 PuLP、OR-Tools、Gurobi）建模求解；p-中值与 p-中心规模较大时，常用拉格朗日松弛、贪心+交换启发式（如 Teitz-Bart 交换法）或遗传算法近似求解。建模时注意三点：

1. 覆盖矩阵先算好：a_ij 由距离矩阵与阈值比较得到，是集合覆盖与最大覆盖的核心输入，务必检查阈值单位与距离单位一致。
2. 权重归一化：最大覆盖与 p-中值都用到 w_i，人口、订单量、GDP 均可，但同一模型内必须统一量纲。
3. p 的敏感性分析：p 每增加 1，覆盖量或总距离如何变化？画出"p—目标值"曲线，找到边际收益骤降的拐点，往往就是合理设施规模。

四、适用场景速查

选型的本质是回答三个问题：服务标准是"必须全覆盖"还是"尽量多覆盖"？设施数量是"由预算决定"还是"由标准决定"？评价指标是"平均效率"还是"最坏情况"？把这三个问题答清楚，模型自然就定了。