简介这份PDF是2023年安徽建筑大学校内数学建模竞赛的正式赛题聚焦鲜奶配送站点的最优化设置问题面向数学建模参赛者及运筹优化、供应链方向学习者。资源为单文件PDF压缩包大小仅98KB包含赛题正文与92个网点坐标、订奶量、配送道路的数据表说明便于直接按题目建模。题目拆解为三个递进式子任务最经济配送站选址、10分钟配送时限约束下的站点设置、各站点配送量均衡优化分别对应设施选址、车辆路径及库存控制等经典模型需综合权衡建设成本、运输时效与均衡指标。借助这份资料可完整演练从数据读取、时间与距离计算到模型构建及求解的建模流程适合练习整数规划、启发式算法与多目标优化为校内赛或国赛积累实战案例。目前已有3073人学习下载可作为赛前模拟与专题训练的有力素材。1. 鲜奶配送站点的最优化设置92个网点数据背后的选址难题鲜奶配送站点的最优化设置难就难在“时效”和“成本”两件事要同时算账。这份某高校的校内数学建模竞赛赛题PDF给了一家牛奶公司在某市的92个网点坐标、订奶量以及网点之间的配送道路数据要求回答三个问题怎么选址最经济、10分钟配送时间限制下最少建几个站、以及配送量怎么均衡。它本质上不是一道单纯的图论题而是设施选址Facility Location与覆盖模型、容量约束的组合优化题。第一问对应固定费用选址模型第二问对应集合覆盖模型第三问则是带配送量上下限的容量约束选址。适合数学建模备赛者、物流规划方向的从业者也适合所有想用整数规划把“选址”跑出数值结果的人。2. 从附件数据到选址模型三类经典设施选址模型怎么选拿到这份PDF先把附件的数据结构看清楚92个网点有坐标、有订奶量网点之间给了配送道路的长度。这意味着我们手里有一张带权无向图网点是节点道路是边。后面所有模型的目标函数、约束条件都要依赖“网点到网点的最短路径距离”而不是直接拿坐标算直线距离。这一步做不对后面三个问题的结论都会跟着错。2.1 P-中位、UFLP、集合覆盖三兄弟的适用边界选址模型里最常用的是P-中位模型、固定费用选址模型UFLP和集合覆盖模型。它们的核心区别在于“站点数量是给定的还是模型自己算出来的”。模型决策变量类型目标函数适合场景P-中位P-median给定站点数量 k最小化所有网点到最近站点的加权距离和已知必须建 k 个站求位置固定费用选址UFLP站点是否开放 网点分配关系最小化站点建设成本 运输成本站点数量未知经济性优先集合覆盖Set Covering站点是否开放最小化满足覆盖所有需求的站点数量或建设总成本有硬性覆盖半径求最少站点数第一问原文说“选择一个或多个点建设配送站”站点数量本身就是待求变量。如果先用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(fx_{j}, catBinary) for j in range(n)} y {(i, j): pulp.LpVariable(fy_{i}_{j}, catBinary) 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/h10 分钟是 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(fx_{j}, catBinary) 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 分钟得到的站点数量变化很有参考价值时间窗最大配送距离 (km)最少站点数按道路距离8 分钟2.667约 24~2710 分钟3.333约 16~1912 分钟4.000约 11~1415 分钟5.000约 8~10站点数量随着覆盖半径增大快速下降但并不是线性关系。半径从 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(fy_{i}_{j}, catBinary) for i in range(n) for j in range(n)} load {j: pulp.LpVariable(fload_{j}, lowBound0) 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。从那以后我每次做任何选址题都强制先画网点分布图、跑一遍距离矩阵自检再进模型。这个习惯帮我避开了很多表面上精致、实际上不可用的成果。希望帮到你。本文还有配套的精品资源点击获取