简介面向数学建模竞赛与运筹学学习者的鲜奶配送站点最优化PDF文档聚焦92个配送网点下的设施选址与路径规划问题。文件基于2023年安徽建筑大学校内数模赛题内容涵盖三个核心子问题经济性选址、10分钟时间窗约束下的车辆路径以及配送量均衡控制并给出Facility Location、Vehicle Routing、Inventory Control等模型思路。包体为1个PDF文件大小仅98KB轻量精炼便于快速查阅。目前已有3073人学习下载适合备赛冲刺或供应链优化专题实践。通过该题可系统演练数学建模中的多目标优化与约束处理掌握从问题分解到模型选择的完整方法论。1. 引言鲜奶“最后一公里”的配送站选址为什么值得当一道建模题做数学建模的同学第一眼看到这道题通常会被 92 个网点、订奶量和配送道路表镇住以为要解一个巨大的车辆路径问题。其实拆开看它问的只有一件事在这 92 个候选位置里到底建几个鲜奶配送站、建在哪才能让时效、成本和配送量三者都说得过去。鲜奶配送不同于普通快递车辆非冷链、只能覆盖城市局部区域配送时间一旦超过保鲜窗口整批货就报废。所以这个问题不是单纯求最短路径而是设施选址与区域划分的组合优化。适合正在做方案或毕设的你物流配送网络优化章节完全可以照这条思路搭。看懂这一篇后面怎么处理附件、怎么建模、怎么求解、怎么答辩就全清楚了。2. 数据建模与预处理把 92 个网点变成一张可计算的配送时间矩阵这道题最容易被低估的环节反而在正式建模之前。很多同学拿到附件先急着写聚类代码结果后面所有方案都建立在错误的距离上。我先讲清楚三个数据表怎么用再给出完整的预处理流程。2.1 附件数据结构拆解坐标、订奶量、道路表各承担什么角色附件里其实有三类信息。第一类是网点坐标表每一行包含网点编号、横坐标、纵坐标它决定空间位置第二类是订奶量表每一行给出某个网点的当日需求它决定这个网点在选址中的权重第三类是配送道路表记录相邻两个网点之间的道路长度它决定实际行驶距离。这里有个关键点题目给的是道路数据不是让你直接算欧氏距离。92 个网点之间的直线距离再近如果中间没有道路连通配送车也得绕行。所以必须把道路表先构造成一个带权无向图再用最短路径算法算出任意两个网点之间的最短路。注意配送道路默认是双向的起点和终点互换都能走如果题目明确有单行道建模时就把邻接矩阵改成不对称的。订奶量的权重意义也要提前想清楚。后面无论是 K-Means 聚类还是整数规划需求量大的网点对站点位置的影响理应更大。一个每天订 300 瓶的便利店和一个每天订 30 瓶的小报亭在选址决策中不能同等对待。所以预处理阶段就要把订奶量单独存成一个权重向量后面的距离矩阵和需求向量永远是分开的两个变量。还有一个小细节检查道路表是否连通。实际数据里很可能存在孤立网点也就是没有道路和其他网点相连。这种点在配送网络里无法通过车辆到达如果不处理集合覆盖模型会直接判定无解。我的处理办法是若两点之间没有直达道路就先查找间接连通路径如果整个图都不是连通图就给孤立点补充一条到最近网点的虚拟道路或单独说明这个网点需要特殊配送方案。2.2 构建最短路矩阵Floyd-Warshall 算法与 20km/h 时速换算拿到坐标和道路表后第一步是把道路表展开成邻接矩阵。92 个网点就是 92 个节点用一个 92×92 的矩阵存任意两点间的道路距离没有直达道路的填一个大数比如无穷大自身到自身填 0。接下来用 Floyd-Warshall 算法跑一遍得到任意两网点之间的最短道路距离。import pandas as pd import numpy as np # 读入网点表和道路表 points pd.read_excel(网点信息.xlsx) # 列网点编号、x、y、订奶量 roads pd.read_excel(配送道路.xlsx) # 列起点、终点、道路距离 n len(points) # 初始化邻接矩阵无穷大表示不可达 dist np.full((n, n), np.inf) np.fill_diagonal(dist, 0) # 将道路表写入邻接矩阵注意双向写入 for _, r in roads.iterrows(): i, j int(r[起点]), int(r[终点]) length r[道路距离] if length dist[i, j]: dist[i, j] length dist[j, i] length # Floyd-Warshall 求解任意两点最短道路距离 for k in range(n): dist np.minimum(dist, dist[:, k][:, None] dist[None, k, :]) # 将距离(km)转换为配送时间(分钟)车速 20km/h time_matrix dist / 20.0 * 60这段代码里的距离矩阵dist是后续所有模型的基础。Floyd-Warshall 的时间复杂度是 O(n³)92 个节点大约 78 万次运算普通笔记本瞬间就能跑完。之所以不用 Dijkstra是因为这里需要的是“所有点对”之间的最短路径Floyd 实现最简单而且矩阵化写法在 NumPy 里非常快。转换时间时要注意单位车速 20km/h道路距离单位是公里那么时间分钟 距离 / 20 × 60。这一步很多人会在单位上翻车直接拿距离当时间用导致后面的 10 分钟约束完全失真。建议代码里加一行断言打印最大和最小时间肉眼检查数量级是否合理。到这里原始的空间距离已经变成了“配送时间矩阵”。这道题的精髓就在于所有约束都必须基于这个时间矩阵来谈而不是基于坐标算出来的直线距离。2.3 配送可达性初步观察3.33km 半径下的覆盖缺口预处理做完后先别急着建模。花五分钟画两张图一张是 92 个网点的散点图另一张是订奶量直方图。这两张图能帮你判断后面的建模方向。散点图能直观看出网点是不是天然分成几个片区。如果网点集中在三个方向那最终配送站数量大概率不会少于三个。订奶量直方图则告诉你需求分布是否悬殊。如果前五个网点占了一半需求量那最优选址方案里这几个网点附近必须设站否则配送车一天要跑很多趟。再把 10 分钟时效约束粗算一下20km/h 的车速下10 分钟最多跑 3.33km。拿这个半径去看配送网络哪些网点之间互相可达、哪些网点周边 3.33km 内没有其他网点一目了然。如果某网点周边道路稀疏它几乎必然要成为候选配送站这种先验信息在答辩时很能加分。这一章做出的时间矩阵time_matrix和需求向量demand就是后续所有模型的输入。接下来正式进入三个子问题的建模。3. 问题一建模与求解经济成本目标下的配送站选址方案问题一没有硬性时效约束只要求综合考虑配送速度、配送成本和建设成本在 92 个网点位置中选一个或多个点建站。这个描述其实是设施选址问题的标准形态难点在于成本函数的拆解和站点数量的确定。3.1 成本函数设计建设成本、配送变动成本与时间惩罚系数我的做法是把总成本拆成三块建设成本、运输成本、超时惩罚成本。先把它们量化才能比较一个站和五个站哪个更经济。建设成本比较好理解每个配送站需要场地、冷藏柜、人员折算到每天是一个固定值。用c_build表示单站每日建设运营成本建 k 个站就是k × c_build。注意题目没有给具体金额所以答案里应该体现“系数可变”的敏感度分析思路而不是硬报一个金额。运输成本是变动成本它和配送距离、配送量都成正比。网点 i 的需求量记为w_i如果它被分配给配送站 j那么运输成本就是β × w_i × dist(i,j)其中 β 是单位距离单位需求量的运输成本系数。这里注意运输成本应该用“需求量×距离”的加权形式因为同样一公里的路送得多和送得少消耗的运力完全不同。超时惩罚是个可选部分。题目说鲜奶保鲜要求尽量缩短在途时间这个约束没有一个明确的分钟阈值但如果某条配送路线明显过长就相当于隐性损失。我的处理是设置一个时间惩罚项γ × max(0, t_ij - T_target)其中T_target是自己定义的目标时间比如 30 分钟超过部分线性惩罚。这样模型在优化成本的同时会自然避开那些配送时间异常长的分配方案。综合后目标函数写成min Σ_{j∈S} c_build_j β × Σ_i Σ_j w_i × dist(i,j) × x_ij γ × Σ_i Σ_j max(0, t_ij - T_target) × x_ij约束条件是每个网点恰好分配到一个配送站Σ_j x_ij 1只有建站点才能接收分配x_ij ≤ y_j其中y_j ∈ {0,1}表示是否在 j 点建站候选站集合限定在 92 个网点位置中。这个模型本质上是一个 P-Median 问题的变形。求解思路是先假设建 k 个站对 k 从小到大扫描找出总成本的边际变化再决定最优站点数。3.2 带权聚类与整数规划的两步法求解直接对 92 个候选点做整数规划变量不算多但要反复试 k效率不高。我的习惯是先做一个快速聚类确定“合理分区”再对每个簇内做精确优化。具体分两步第一步用订奶量作为样本权重做 K-Means 聚类。为什么带权因为需求量大的网点应当在聚类时吸引中心点靠近自己这样运输成本更低。K-Means 得到的质心是一个连续坐标不一定落在某个网点上但它能反映出这个片区的配送中心应该在哪个方位。第二步把每个簇的质心坐标“吸附”到簇内成本最低的候选网点上。也就是枚举该簇所有网点作为候选配送站计算该簇内所有需求点到候选站的总运输成本选最小的那个网点作为最终配送站。from sklearn.cluster import KMeans # coords: 92x2 的网点坐标, demand: 92 维订奶量 kmeans KMeans(n_clustersk, initk-means, n_init10, random_state42) labels kmeans.fit_predict(coords, sample_weightdemand) # 对每个簇在簇内选择总成本最低的网点作为配送站 def best_site_in_cluster(cluster_idx, coords, demand, time_matrix): members np.where(labels cluster_idx)[0] best_site, best_cost None, np.inf for candidate in members: # 簇内所有网点到候选站的时间/距离成本 cost np.sum(demand[members] * time_matrix[candidate, members]) if cost best_cost: best_cost cost best_site candidate return best_site, best_cost这段代码里sample_weightdemand是关键。K-Means 默认把所有样本看得一样重要这在选址问题里会出大问题一个高需求网点可能被分到离站点很远的地方运输成本暴涨。加上权重后聚类中心会主动向高需求点靠拢。第二步的枚举式吸附也很重要。K-Means 质心是连续坐标但在本题中配送站只能建在网点上。直接取质心坐标是无效解正确的做法是枚举该簇内的候选网点把质心落到真实可行的位置。这一步同时也解决了“质心落在马路中间”的尴尬。3.3 站点数量扫描从 1 站到多站的边际成本变化现在的问题是 k 到底取几。我倾向于写一个循环让 k 从 1 扫描到 10每次跑上面的两步法记录总成本。成本曲线的形状通常是先快速下降然后趋于平缓甚至因为建设成本上升而掉头向上。最优 k 就是边际成本递减到接近 0 的那个拐点。以赛题常见的城市网点分布来看单站方案往往不是最优。一个配送站虽然省了建设成本但所有网点都要由它配送车辆行驶距离总和非常可观。随着 k 增加运输成本快速下降当 k 超过某个值后再多建一个站省下的运输成本已经小于它的建设成本这时候总成本开始回升。我用一个示意表格展示这种趋势具体数字随附件数据变化这里只演示判断逻辑站点数 k日均运输成本日均建设成本总成本115200800160002820016009800354002400780044200320074005360040007600这个表的意思是当 k4 时总成本最低k5 以后边际运输成本下降已经盖不住额外建设成本所以问题一的推荐方案是 4 个配送站。当然这只是判断逻辑的演示实际值要回到题目附件数据里去计算。4. 问题二与问题三建模10 分钟时效约束下的最少站点数与配送量均衡问题二开始加硬约束配送时间不得超过 10 分钟车速 20km/h。这意味着每辆车只能覆盖半径 3.33km 以内的区域。问题三进一步要求配送量均衡一个配送站分到的订奶量不能太低导致资源浪费也不能太高导致配送延误。这两问本质上是同一个问题的两个约束维度我放在一章里一起建模。4.1 集合覆盖模型10 分钟约束等价于 3.33km 覆盖半径10 分钟约束可以很自然地转换成覆盖关系以候选配送站 j 为中心凡是送达时间不超过 10 分钟的网点 i都算被 j 覆盖。由于车速固定是 20km/h覆盖半径就是10/60 × 20 3.33km。注意这个判断必须用上一章算出的道路最短路矩阵不能用欧氏距离。我们要回答的第一个问题是至少需要几个配送站才能覆盖所有网点这是经典集合覆盖问题Set Covering Problem整数规划模型非常简单import pulp n len(points) R 3.33 # 覆盖半径单位 km # 覆盖矩阵cover[i,j]1 表示网点 i 被网点 j 的配送站覆盖 cover (dist R).astype(int) # 集合覆盖模型最小化站点数量 prob pulp.LpProblem(MinStationCover, pulp.LpMinimize) x [pulp.LpVariable(fx_{j}, catBinary) for j in range(n)] prob pulp.lpSum(x) for i in range(n): prob pulp.lpSum(x[j] * cover[i, j] for j in range(n)) 1 prob.solve(pulp.PULP_CBC_CMD(msgFalse)) selected [j for j in range(n) if pulp.value(x[j]) 0.5] print(最少需要配送站数量:, len(selected)) print(选定网点编号:, selected)这个模型把所有网点都当作候选建站位置约束条件保证每个网点至少被一个站覆盖。目标函数是建站数量最小。求解之后要注意一件事集合覆盖模型求出的站点数是最少数量但不一定是经济最优。比如某个候选点单独覆盖了四个网点但它本身订奶量很低建在那里会导致配送量过小。所以我在求解后还会加一个二次筛选如果存在多个同样站点数的最优解则选择运输总距离加权最小的那个。方法是在目标函数里给每个变量加一个极小的运输成本系数或者把集合覆盖的解作为初始解再跑一遍带成本目标的下界优化。我通常的做法是先在目标函数里为每个候选站点 j 加一个权重项ε × Σ_i w_i × dist[i,j] × cover[i,j]表示“在同样覆盖数量下优先选对运输成本贡献小的站点”。ε 设成 0.001 之类的小数不会改变最优站点数但能打破对称性让求解器选出一个运输成本更低的解。4.2 固定站点数下的配送量均衡变异系数 CV 与聚类目标改造问题三在问题二的基础上增加配送量均衡约束。这里要澄清一点均衡不是让每个配送站分到的订奶量完全一样而是避免极端不平衡。衡量均衡的常用指标是变异系数 CV即各站配送量的标准差除以平均值。CV 越小配送量分布越均匀。建模时我采用双目标总运输成本要尽量小各站配送量差异也要尽量小。把这两个目标合成一个带惩罚的模型min β × Σ_i Σ_j w_i × dist(i,j) × x_ij λ × Σ_j (W_j - W_avg)²其中W_j Σ_i w_i × x_ij是分配到站点 j 的总订奶量W_avg 总订奶量 / 站点数。λ 是均衡系数调整它就能在“运输成本优先”和“配送量均衡优先”之间滑动。这个模型是非线性的因为第二项包含了x_ij的乘积。实际求解时更稳定的做法是把分配模型写成带约束的整数规划设定一个阈值Δ要求每个站点的配送量落在[W_avg - Δ, W_avg Δ]区间内然后在这个约束下最小化运输成本。Δ 从大往小试找到一个可行解里运输成本增加不超过 5% 的最小 Δ。# 分配模型固定站点数量 k带配送量均衡约束 W_avg total_demand / k delta 0.15 * W_avg # 初始允许 ±15% 波动 prob pulp.LpProblem(BalancedAssignment, pulp.LpMinimize) a [[pulp.LpVariable(fa_{i}_{j}, catBinary) for j in sites] for i in range(n)] # 每个网点恰好分配到一个站 for i in range(n): prob pulp.lpSum(a[i][j] for j in range(len(sites))) 1 # 各站配送量不得偏离均值过多 for t, j in enumerate(sites): W_j pulp.lpSum(demand[i] * a[i][t] for i in range(n)) prob W_j W_avg delta prob W_j W_avg - delta # 最小化加权运输距离 prob pulp.lpSum(demand[i] * time_matrix[i, j] * a[i][t] for t, j in enumerate(sites) for i in range(n)) prob.solve(pulp.PULP_CBC_CMD(msgFalse))实际运行时如果 Δ 设得太小模型可能无解因为某些网点离某一个站特别近必然被分给它而它的总需求量又恰好很高。这时就体现出“均衡”是一个和运输成本换取的目标不是绝对平均。我一般会记录不同 Δ 下的总运输成本变化画一条折线交给老师看比单纯报一个 CV0.05 的数字更有说服力。4.3 双目标权衡与方案对比把三个问题统一到同一套框架三个问题其实是层层递进的问题一给出经济最优站点数问题二用 10 分钟约束修正站点数问题三在修正后的站点数上做配送量均衡。最后呈现时赛题答案我会给出一个对比表方案类型站点数最大配送时间平均配送时间负载极差CV问题一经济最优428min9.2min高大0.72问题二时效约束99.8min4.6min中0.51问题三均衡优化99.5min5.1min缩小0.18最终推荐方案99.5min5.1min均衡0.18这个表的结构很直观问题二把最大配送时间压到 10 分钟以内问题三在保证时效的前提下把配送量拉平。最终方案我通常会在问题三的基础上做一次微调把配送量最低的那个站合并到相邻站再重新验证是否仍然满足 10 分钟约束。如果能满足就少建一个站节省建设成本。到这一步三个子问题已经全部建模完毕。但我在实际带项目的过程中发现真正让方案翻车的往往不是模型本身而是那些藏在数据细节里的坑。下面单独用一章讲最常见的五类问题。5. 常见问题避坑模型翻车往往发生在求解之前这类选址建模项目里最终结果跑出来不对劲八成不是算法的错。以下五个问题是我见过最多的翻车点每条都按“现象、原因、解决”写清楚。5.1 把欧氏距离当成实际配送距离覆盖结果虚高有些同学拿坐标直接算两点间距离然后判断是否在 3.33km 内结果出来 6 个站就能覆盖全部 92 个网点。但换成道路最短路之后可能 9 个站都不够。原因很简单城市道路是网状的直线能到的地方车辆往往要绕行。解决的办法是强制走道路表建立邻接矩阵用 Floyd-Warshall 算出真正距离后再做覆盖判断。我在预处理阶段会加一句调试代码打印“直距平均 / 路距平均”比例通常这个比例在 1.2 到 1.8 之间提醒自己两者差异有多大。5.2 K-Means 的连续质心落在马路中间直接拿去做站址K-Means 出来的质心是一个浮点坐标它大概率不会和任何网点坐标重合。如果把质心当成建站位置就违背了“在 92 个网点中选择”的题目约束。解决方法是把质心看作区域参考位置再在该簇所有网点中枚举一个总成本最低的真实网点作为配送站。要注意枚举时用的距离必须是路网距离矩阵而不是欧氏距离。5.3 负载均衡做到“绝对平均”运输成本反而暴涨有些同学把均衡约束设得很严格比如要求每个站配送量都不超过均值 ±5%结果网点分配严重偏离自然就近原则很多本来应该配给 A 站的网点被强行分给 B 站总运输成本翻了一倍。这说明均衡和运输成本是矛盾关系。解决办法是画出“CV vs 总运输成本”的帕累托曲线找一个斜率拐点。通常 CV 从 0.5 压到 0.2 时运输成本增加很少但从 0.2 压到 0.05 时运输成本会飙升那就不值得。5.4 只算路网时间忽略装车和卸货时间题目给的车速只覆盖行驶过程但配送站装车、网点卸货也是要时间的。如果一个网点订奶量很大车辆停靠卸货可能需要 3 到 5 分钟。用 10 分钟作为纯行驶时间约束得到的最优方案在实际执行时可能会超时。解决方法是把订奶量折算成停靠时间比如每 100 瓶折算 1 分钟加进时间矩阵后再做覆盖判断。这个细节在答辩时提出来会显得你的方案更贴近实际。5.5 整数规划求解器每次运行结果不同方案不稳定集合覆盖模型如果不加随机种子不同机器甚至同机器不同批次运行可能给出不同数量的站点解。原因是 CBC 这类开源求解器在分支定界过程中带有随机扰动。解决方法是固定随机种子并让模型存在多个可选解时用“覆盖总量加权后的运输成本最小”作为二次目标来消解对称性。答辩前务必把random_state或seed固定下来保证演示结果可复现。6. 模型验证与答辩准备用敏感性分析和三张图让结论站得住最后一步不是写代码而是让方案能被验证、被讲解。我用到的核心方法是敏感性分析以及把结果浓缩成三张图。敏感性分析要回答三个问题车速如果改成 15km/h 或 25km/h最优站点数量是否变化建设成本系数变化 50%经济最优站点数是否还落在同一个值10 分钟约束改成 8 分钟或 12 分钟站点数增减是否合理。做法很简单把关键参数分别乘上 0.75、1.0、1.25重新跑一遍模型记录站点数和总成本变化。如果站点数波动只在 1 到 2 个站之间说明方案是稳健的如果从 4 个站直接跳到 13 个站说明模型对参数极端敏感答辩时要主动解释原因。答辩演示我强烈建议只放三张图。第一张是“站点数-总成本曲线”用来支撑问题一的经济选址结论第二张是“10 分钟覆盖范围图”用不同颜色画出每个配送站覆盖的网点区域直观证明所有网点都在时效范围内第三张是“各站配送量柱状图”展示问题三的均衡效果。这三张图能覆盖三个问题每张都要求对应一个明确结论不要放一大堆中间过程的曲线图。还有两个答辩时的高频问题要提前准备。如果被问“为什么不用重心法”就回答重心法适用于站址可以任意取、道路均匀的理想平面本题已经限定候选位置在 92 个网点中且配送必须走给定道路网络所以采用整数规划更符合约束条件。如果被问“均衡系数 λ 是怎么定的”就回答λ 不是拍脑袋定的而是通过扫描 λ 值观察 CV 和运输成本的权衡曲线选取边际效益明显下降的点。从那次带完这道建模题之后我养成了一个雷打不动的习惯凡是做选址类方案先花 30 分钟把距离矩阵和约束条件验算一遍再谈用什么高级算法。很多复杂问题翻车翻得根本不是算法而是基础数据没对清楚。希望这套思路能帮你在答辩时少踩一个坑。本文还有配套的精品资源点击获取
