鲜奶配送站点的最优化设置：92个网点选址的数学建模全解析

简介：这份PDF是2023年安徽建筑大学校内数学建模竞赛的正式赛题，聚焦鲜奶配送站点的最优化设置问题，面向数学建模参赛者及运筹优化、供应链方向学习者。资源为单文件PDF压缩包，大小仅98KB，包含赛题正文与92个网点坐标、订奶量、配送道路的数据表说明，便于直接按题目建模。题目拆解为三个递进式子任务：最经济配送站选址、10分钟配送时限约束下的站点设置、各站点配送量均衡优化，分别对应设施选址、车辆路径及库存控制等经典模型，需综合权衡建设成本、运输时效与均衡指标。借助这份资料可完整演练从数据读取、时间与距离计算到模型构建及求解的建模流程，适合练习整数规划、启发式算法与多目标优化，为校内赛或国赛积累实战案例。目前已有3073人学习下载，可作为赛前模拟与专题训练的有力素材。

1. 鲜奶配送站点的最优化设置：92个网点数据背后的选址难题

鲜奶配送站点的最优化设置，难就难在“时效”和“成本”两件事要同时算账。这份某高校的校内数学建模竞赛赛题PDF，给了一家牛奶公司在某市的92个网点坐标、订奶量以及网点之间的配送道路数据，要求回答三个问题：怎么选址最经济、10分钟配送时间限制下最少建几个站、以及配送量怎么均衡。它本质上不是一道单纯的图论题，而是设施选址（Facility Location）与覆盖模型、容量约束的组合优化题。第一问对应固定费用选址模型，第二问对应集合覆盖模型，第三问则是带配送量上下限的容量约束选址。适合数学建模备赛者、物流规划方向的从业者，也适合所有想用整数规划把“选址”跑出数值结果的人。

2. 从附件数据到选址模型：三类经典设施选址模型怎么选

拿到这份PDF，先把附件的数据结构看清楚：92个网点有坐标、有订奶量，网点之间给了配送道路的长度。这意味着我们手里有一张带权无向图，网点是节点，道路是边。后面所有模型的目标函数、约束条件都要依赖“网点到网点的最短路径距离”，而不是直接拿坐标算直线距离。这一步做不对，后面三个问题的结论都会跟着错。

2.1 P-中位、UFLP、集合覆盖：三兄弟的适用边界

选址模型里最常用的是P-中位模型、固定费用选址模型（UFLP）和集合覆盖模型。它们的核心区别在于“站点数量是给定的还是模型自己算出来的”。

第一问原文说“选择一个或多个点建设配送站”，站点数量本身就是待求变量。如果先用P-中位模型，就得先猜一个 k，这违背了“最经济”的出发点。固定费用选址模型天然适合：每个候选站点有建设成本 f_j，每瓶奶从站点 j 配送到网点 i 有运输成本，目标函数是建设成本加上配送成本，模型会自动在“多建站缩短运输距离”和“少建站节省开办费”之间找平衡点。

第二问加了“配送时间不得超过10分钟”的硬约束，这时候解法就变了：先把10分钟换算成最大配送距离，再问“用最少的站点覆盖全部92个网点”。这正是集合覆盖模型的场景。第三问在覆盖的基础上又叠加了“每个站点的配送量不能过低也不能过高”，那就要把容量约束塞进模型，变成带上下限的设施选址问题。

2.2 距离矩阵：先把道路数据变成配送成本

第二问、三问能不能做对，关键看距离矩阵怎么来的。我见过不少同学直接拿网点的 (x, y) 坐标算欧氏距离，然后拿去当配送距离用，结果覆盖半径看起来够，实际道路绕行后根本送不到。附件明确给了“网点之间的配送道路”，所以正确做法是先构建邻接矩阵，再用 Floyd-Warshall 或 Dijkstra 求全源最短路径。

92个节点的规模很小，Floyd-Warshall 的 O(n³) 完全能接受，而且一次能算出所有点对之间的最短距离，后续三个问共用这一个矩阵就够了。下面是我常用的读取与距离计算的写法：

import numpy as np import pandas as pd # 假设附件数据整理为三个表 coords = pd.read_csv('coords.csv') # 列：id, x, y demand = pd.read_csv('demand.csv') # 列：id, order_qty roads = pd.read_csv('roads.csv') # 列：from, to, length n = len(coords) INF = 1e9 dist = np.full((n, n), INF) np.fill_diagonal(dist, 0) # 网点到自身距离为 0 # 把道路表写入邻接矩阵，注意节点 id 从 1 开始，要减 1 转成 0 基索引 for _, row in roads.iterrows(): i, j, d = int(row['from']) - 1, int(row['to']) - 1, row['length'] if d < dist[i, j]: dist[i, j] = dist[j, i] = d # Floyd-Warshall 求全源最短路径 for k in range(n): dk = dist[k] for i in range(n): dik = dist[i, k] if dik == INF: continue row_i = dist[i] for j in range(n): nd = dik + dk[j] if nd < row_i[j]: row_i[j] = nd

这段代码的逻辑是先把道路边写入对称邻接矩阵，同一对节点之间可能有多条路，取最小长度；然后用 Floyd 逐点松弛，把间接到达的路径压缩成最短距离。参数上要注意from和to在 CSV 里是原始网点编号，代码里转成 0 基索引，避免数组越界。另外如果道路表里有重复边，直接取 min 即可；如果道路是单向的，不写dist[j, i]那一行就能保留单向性，但鲜奶配送场景通常双向，所以两边都赋值。

算完 dist 之后，建议先打印几行检查，确认对角线是 0、所有点都连通，再进入建模环节。如果某个网点到其他点全是 INF，说明路网数据有断点，需要回去核对原始数据。

2.3 第一问的 UFLP 模型：建设成本与运输成本的权衡

有了距离矩阵，第一问就可以建模了。固定费用选址模型的决策变量有两组：x_j 表示第 j 个候选网点是否建设配送站；y_ij 表示网点 i 的订奶量是否由站点 j 配送。目标函数是建设成本加运输成本：

min Σ_j f_j · x_j + Σ_i Σ_j c · q_i · d_ij · y_ij

约束条件有两个：每个网点 i 必须且只能分配给一个配送站；网点 i 只能分配给已经建站的 j。

用 PuLP 求解这个混合整数规划，代码比较直观：

import pulp F = 50000 # 每个配送站的建设成本（元），需要根据题目经济背景设定 C = 2.0 # 单位运输成本系数：元/(瓶·km)，简化处理 q = demand['order_qty'].values # 各网点订奶量 prob = pulp.LpProblem("UFLP", pulp.LpMinimize) x = {j: pulp.LpVariable(f'x_{j}', cat='Binary') for j in range(n)} y = {(i, j): pulp.LpVariable(f'y_{i}_{j}', cat='Binary') for i in range(n) for j in range(n)} # 目标：建设成本 + 运输成本（运输成本与距离、订奶量成正比） prob += pulp.lpSum(F * x[j] for j in range(n)) + \ pulp.lpSum(C * q[i] * dist[i, j] * y[i, j] for i in range(n) for j in range(n)) # 每个网点只由一个站点配送 for i in range(n): prob += pulp.lpSum(y[i, j] for j in range(n)) == 1 # 网点只能分配给已建设的站点 for i in range(n): for j in range(n): prob += y[i, j] <= x[j] prob.solve() print("求解状态:", pulp.LpStatus[prob.status]) open_sites = [j for j in range(n) if x[j].value() > 0.5] print("建议建设站点数量:", len(open_sites)) print("总成本:", pulp.value(prob.objective))

这里的逻辑是让求解器自己去权衡：建设成本 F 越高，模型就越倾向少建站、跑远路；运输单价 C 越高，模型就越倾向多建站、缩短配送距离。参数 F 和 C 的绝对值不重要，重要是它们的比值，因为目标函数里只有相对大小决定最优解。实际做题时拿不准，我一般会做一组敏感性分析，比如把 F 从 3 万调到 10 万，看站点数量的变化曲线。

第一问输出结果后，重点看三个数：建议建设的站点数量、最大配送距离、各站点的配送量分布。如果最大配送距离已经比 10 分钟能跑的距离还短，说明第一问的“经济方案”在时效上也勉强成立；如果超出很多，就说明纯经济选址和时效选址会有明显分歧，正好衔接第二问。

3. 10分钟时效约束：覆盖半径怎么算、最少站点数怎么求

第二问把时效变成了硬约束：配送站到网点的配送时间不得超过 10 分钟。这就意味着建模逻辑从“成本最小化”切换到“覆盖约束下的成本最小化”。这一章的难点不在模型本身，而在于怎么把时间约束折算成距离，以及怎么处理道路绕行带来的误差。

3.1 把10分钟换算成距离半径，注意不是直线距离

物流车时速 20km/h，10 分钟是 1/6 小时，所以理论最大行驶距离是 20 × (10/60) ≈ 3.333 km。注意，这个距离指的是沿配送道路行驶的实际距离，不是网点的欧氏直线距离。城市里两条路之间的实际绕行距离通常是直线距离的 1.2~1.5 倍，如果直接拿坐标算直线覆盖半径，解出来的站点数量会偏少，实际配送时会大面积超时。

正确做法是直接用 2.2 节算好的 dist 矩阵来判断：dist[i][j] <= 3.333 就认为网点 i 可以被站点 j 在 10 分钟内覆盖。如果要更稳健，可以把 3.333 乘一个折减系数，比如 0.9，得到 3.0 km，给装货、红绿灯留出余量。这个系数没有标准答案，建议先统计一下路网中“道路距离 / 欧氏距离”的比值分布，取 85 或 90 分位数作为折减依据。

3.2 集合覆盖模型的实现：最少站点覆盖全部92个网点

假设每个配送站的建设成本相同，那么“考虑到配送站的建设成本，给出最优方案”就等价于找覆盖全部网点的最少站点数。决策变量只有一组：x_j 表示 j 点是否建站。目标是最小化 Σ x_j，约束是每个网点 i 至少被一个 dist[i][j] <= R 的站点覆盖：

R = 20 * (10 / 60) # 3.333 km，按道路距离判断覆盖 # 构建覆盖矩阵：cover[i][j] = 1 表示 j 站能覆盖 i 网点 cover = [[1 if dist[i][j] <= R else 0 for j in range(n)] for i in range(n)] prob = pulp.LpProblem("SetCover", pulp.LpMinimize) x = {j: pulp.LpVariable(f'x_{j}', cat='Binary') for j in range(n)} # 目标：站点数量最少 prob += pulp.lpSum(x[j] for j in range(n)) # 每个网点至少被一个已建设站点覆盖 for i in range(n): prob += pulp.lpSum(cover[i][j] * x[j] for j in range(n)) >= 1 prob.solve() print("至少需要建设站点数:", int(pulp.value(prob.objective)))

集合覆盖模型是 NP 难的，但 92 个候选点、92 条覆盖约束的规模对整数规划求解器来说并不算大，一般几秒到十几秒能出最优解。如果求解器长时间卡住，说明覆盖矩阵太稀疏，也就是 R 设得太小，导致很多网点只有极少数候选站能覆盖。这时先用贪心算法求一个可行上界，再传给求解器做分支定界，会快很多。

参数 R 是最敏感的一个输入。它直接由“10分钟”这个约束决定，但要不要加折减、加多少折减，会影响站点数量。我一般会同时跑 R = 3.0、3.333、3.7 三档，把结果放在一起对比，看站点数量对半径的敏感度。

3.3 不同时间窗下的站点数量变化

用同一个距离矩阵，把时间窗从 8 分钟逐步放大到 15 分钟，得到的站点数量变化很有参考价值：

站点数量随着覆盖半径增大快速下降，但并不是线性关系。半径从 3.333 放到 4.0，站点数可能只少 3~4 个；但从 2.667 提到 3.333，站点数能少 6~8 个。这说明 10 分钟这个约束正好处在“站点数量对半径敏感”的区间，稍微放宽一点时效，就能省下好几个站的建设成本。实际决策时，这个表格比单个最优解更有说服力，因为能直接看到时效要求和建设成本之间的置换关系。

如果题目假设各站点建设成本不同，代码只需把目标函数从lpSum(x[j])改成lpSum(f[j] * x[j])，约束完全不变。

4. 配送量均衡处理与常见坑排查

第三问是三个问里最容易在细节上翻车的。一个配送站配送量过低是资源浪费，过高会延误配送，所以必须在覆盖约束之外，再加上每个站点配送量的上下限。这一章先说清楚均衡怎么量化，再把我复现时踩过的坑记录下来。

4.1 均衡指标：从负荷比到上下限约束

设站点 j 分配到的总订奶量为 L_j = Σ_i q_i · y_ij，其中 y_ij 表示网点 i 是否分配给站点 j。均衡性的量化指标常见有两个：一是最大最小负荷比 L_max / L_min，理想情况是接近 1；二是配送量分布的变异系数 CV = σ(L) / μ(L)，经验上 CV 小于 0.3 就算比较均衡。

要在模型里强制均衡，最直接的做法是给每个站点的配送量加上下限：

L_min · x_j ≤ L_j ≤ L_max · x_j

其中 L_min 和 L_max 是根据总订奶量和预估站点数定的。如果第二问解出来要建 18 个站，总订奶量是 10000 瓶，那平均每个站约 556 瓶，上下限可以设在 400~700 瓶，也可以按均值的±30%设。

在集合覆盖模型基础上扩展的代码如下：

# 在集合覆盖的变量基础上，增加配送量变量和分配变量 y = {(i, j): pulp.LpVariable(f'y_{i}_{j}', cat='Binary') for i in range(n) for j in range(n)} load = {j: pulp.LpVariable(f'load_{j}', lowBound=0) for j in range(n)} # 总订奶量 total_q = sum(q) # 按站点数估算平均配送量，再设上下限 k_est = int(pulp.value(prob.objective)) # 第二问的站点数 avg_load = total_q / k_est L_min, L_max = 0.7 * avg_load, 1.3 * avg_load # 每个网点仍只能分配到一个已建设站点 for i in range(n): prob += pulp.lpSum(y[i, j] for j in range(n)) == 1 for j in range(n): prob += load[j] == pulp.lpSum(q[i] * y[i, j] for i in range(n)) prob += load[j] >= L_min * x[j] prob += load[j] <= L_max * x[j] for i in range(n): prob += y[i, j] <= x[j]

这段代码把原来的纯覆盖模型升级成了带容量约束的选址模型。逻辑上多了一组 y 变量，网点的分配关系重新成为决策的一部分。注意这里不能只加load的上下限约束而不管y的分配唯一性，否则可能出现一个网点同时分给多个站点的情况。参数 L_min 和 L_max 是均衡力度的旋钮：区间收得越紧，均衡越好，但可行域越小，可能出现无解或站点数被迫增加。一般做法是先跑一遍不加均衡约束的模型，统计各站点配送量的实际分布，再回头定上下限。

4.2 避坑记录：四组典型翻车现场

我在复现这道题时踩了不少坑，挑四个影响最大的记录如下。

坑一：覆盖半径直接用欧氏距离，站点数偏少

现象：第二问用坐标算直线距离做覆盖，解出来只要 12 个站；换成道路最短距离后变成 18 个站，差异巨大。

原因：道路网络里两点之间的最短路径几乎总是大于直线距离。3.333 km 的直线半径覆盖了很多实际上道路距离超过 4 km 的网点。

解决：统一用 Floyd 算出的 dist 矩阵判断覆盖；如果要快速估算，可用“欧氏距离 × 1.3”作为粗配，但正式求解必须用路网距离。

坑二：集合覆盖模型求解时间过长

现象：R 设为 3.0 km 时，模型跑了几分钟没出结果，求解器日志一直在刷上界和下界。

原因：覆盖半径太小，每个网点可用的候选站数量少，可行解稀疏，整数规划搜索树很深。

解决：先用贪心算法（每次选覆盖未覆盖网点最多的候选站）求一个上界；把上界作为初始可行解传给求解器，能显著加速剪枝。另外，把覆盖不到任何网点的候选站直接排除，变量规模能降一截。

坑三：加入均衡约束后模型直接无解

现象：把 L_min 设为平均负荷的 80%、L_max 设为 120% 后，PuLP 返回 Infeasible。

原因：地理分布决定了一些偏远网点只有一个候选站能覆盖，这个站被迫承担少量配送量；强行把下限抬高，就会没有任何可行分配方案。

解决：先不加均衡约束求解，统计每个站点的实际配送量分布；再根据分布的分位数设上下限，而不是拍脑袋定平均值百分比。比如让 L_min 取所有站点配送量的第 10 百分位，L_max 取第 90 百分位，保证可行性和均衡性的平衡。

坑四：Floyd 距离矩阵初始化出错，导致覆盖判断失效

现象：部分网点的覆盖状态明显不对，比如距离为 0 的网点反而显示不可达。

原因：roads 表里的节点编号是 1 基，代码里没减 1 就当作数组索引用，导致顶点错位；或者道路表有孤立节点，Floyd 跑完后仍然是 INF。

解决：读取数据后先做一个连通性自检——统计 dist 矩阵中 INF 的数量，如果有非对角线 INF，说明路网有孤立点，需要检查附件数据是否完整。编号转换要在写入邻接矩阵前统一完成。

4.3 三问联动：把三个模型串成一份完整方案

三个问题不是各自孤立的题目。第一问是纯经济视角，得到最省钱的站点数量和位置；第二问加了时效硬约束，得到满足 10 分钟覆盖的最少站点方案；第三问是在第二问的方案上做配送量再平衡。实际操作中，我建议按这个顺序做：

先跑第二问的集合覆盖模型，拿到最少站点数和候选站点集合；再在这个基础上叠加均衡约束，尝试在站点数量不增加的前提下满足配送量上下限；如果无解，就允许增加 1~2 个站点，对比“多建站带来的建设成本”和“均衡配送带来的运营收益”哪个更划算。这个过程本质上是一个双层优化：外层决定站点数量，内层决定分配关系。竞赛里没有必要用复杂的迭代算法，把三个模型的结果并排对比，通常就能支撑起一页很清晰的方案说明。

5. 复现技巧：一条高效跑通全流程的检查清单

把这道题完整复现一遍，我的标准流程是这样：读取数据 → 构建距离矩阵 → 跑第一问 UFLP → 跑第二问集合覆盖 → 跑第三问带容量约束的覆盖模型 → 把结果画到地图上。代码骨架如下：

import pandas as pd import numpy as np import pulp # 1. 读取数据 coords = pd.read_csv('coords.csv') demand = pd.read_csv('demand.csv') roads = pd.read_csv('roads.csv') # 2. 计算道路最短距离矩阵 dist # （复用 2.2 节代码） # 3. 第一问：UFLP，输出站点数与总成本 # 4. 第二问：集合覆盖，R = 3.333，输出最少站点数 # 5. 第三问：在第二问基础上加 load 上下限约束 # 6. 可视化：用 matplotlib 画网点散点图， # 把站点用不同颜色标出，配送关系用连线表示

每一步都有一个检查点。第 2 步检查 dist 矩阵对角线为 0、没有非对角线 INF；第 3 步检查目标函数里的成本量级是否合理，F 和 C 的比例会不会导致站点数极端（全建或只建一个）；第 4 步检查覆盖矩阵每行是否至少有一个 1，否则说明 R 太小；第 5 步检查均衡约束加入后的站点数和配送量分布，用 CV 验证均衡效果；第 6 步用散点图看一眼站点有没有落在偏远角落里。

我强烈建议把三个时间窗（比如 8 分钟、10 分钟、12 分钟）的最小站点数结果做成表格放在论文里，比单独给一个数字更有说服力，也方便评委理解时效与成本的置换关系。

最后说一个个人教训。我第一次复现这道题时，偷懒直接用欧氏距离做覆盖，第二问解出来 11 个站，还觉得挺合理。后来某开发者在交流时提醒我检查道路距离，换成 dist 矩阵重新跑，站点数直接变成 17。从那以后，我每次做任何选址题，都强制先画网点分布图、跑一遍距离矩阵自检，再进模型。这个习惯帮我避开了很多表面上精致、实际上不可用的成果。希望帮到你。

本文还有配套的精品资源，点击获取