简介这份PDF是2023年安徽建筑大学校内数学建模竞赛“鲜奶配送站点的最优化设置问题”赛题材料面向准备数学建模竞赛、练习选址优化与供应链建模的高校学生及指导教师。内容围绕92个网点的位置坐标、订奶量与配送道路数据展开依次讨论最经济的配送站选址、配送时间不超过10分钟且兼顾建设成本的多站点方案以及配送量均衡约束下的重新优化涉及设施选址、车辆路径和库存控制等模型思路。资源包共1个PDF文件大小约98KB篇幅紧凑便于打印、标注和赛前研读。已有3074人学习适合用作完整赛题复盘、建模方案对照、附件数据与约束条件理解以及论文写作练习的案例材料也可据此梳理选址、路径与均衡三类子问题的求解框架。1. 先破一个直觉这道选址题的得分点不在“算出几个站”而在三套约束的切换拿到鲜奶配送站点这道赛题八成队伍的第一步是打开坐标表跑一版 K-means看轮廓系数决定聚成几类。这条路走到第三问会彻底断掉——因为题目从头到尾都要求“在 92 个网点位置中选择”聚类中心是连续空间里的虚拟点压根不是可建站的位置第一处翻车就埋在这里。真正拉开差距的是三件事能不能把 10 分钟和 20km/h 换算成一条能写进约束的服务半径能不能把建设成本和运输成本折进同一个目标函数并说清量纲能不能在第三问把“均衡”从一句形容词变成可求解的数学表达式。这道题考的不是某个算法会不会背而是同一份 92 行数据在三种约束下重新建模的迁移能力。适合已经做过一两次建模、但一到“多问递进”就只会复制粘贴第一问代码的人。2. 考点分布92 个网点、10 分钟、20km/h三个数字撑起全部考点2.1 从题目文字反推考点三个数字各自对应一种建模动作题干里数字不多但每一个都不是随手写的。92 是规模决定了你能不能用精确求解——92 个候选点做 0-1 规划变量规模在八千多通用求解器几分钟内能出结果不需要一上来就上遗传算法而如果候选点变成 1000 个同样的模型就得换成贪心加局部搜索。这个规模判断是阅卷时“模型选择是否合理”的第一印象分。10 分钟和 20km/h 是一组乘出来就是服务半径20 km/h × (10/60) h ≈ 3.33 km。这行换算必须明明白白写在正文里它是第二问从“选址问题”变成“覆盖问题”的开关。很多队伍直接把 10 分钟写进目标函数当惩罚项方向就偏了——第二问问的是“在硬时限下最少要建几个站”这是约束不是目标。容易被跳过的还有附件里的“配送道路”。题干给了坐标、订货量还专门给了网点之间的道路数据这不是凑数的。它意味着两点之间的距离有两种算法直线欧氏距离或者沿路网的最短路径距离。用哪一种要在模型假设里交代清楚并且说明理由——小型物流车走的是路不是无人机。用路网距离的队伍结果通常比用直线距离的少建一到两个站这个差异就是论文里最漂亮的一段对比分析。提示坐标单位一定要先确认。如果附件给的是经纬度直接算欧氏距离得到的“度”没有任何物理意义必须先做投影换算成米或千米否则 3.33 km 这个阈值完全对不上。2.2 三问的模型骨架一张表看清递进关系三问不是三道独立的题是同一套决策变量上逐层加约束。把这张表默写下来赛场上就不会出现“第二问推倒重来”的情况。维度第一问最经济第二问10 分钟时限第三问配送量均衡决策变量是否建站 y_j、网点归属 x_ij同左同左另加负载变量目标函数建设成本 运输成本最小化建站数量成本相同则等价最小化最大站点负载或最小化负载方差核心约束每个网点恰好被一个站服务只有建了站才能被分配新增 d_ij ≤ 3.33 km新增单站配送量上下限典型模型无容量设施选址UFLP/ p-中位集合覆盖SCP带容量约束的设施选址CFLP 均衡求解难度NP-hard92 规模可精确求解可精确求解贪心可给上界带 min-max 目标仍需 0-1 规划第三问的“均衡”是最容易写虚的地方。它不是一个约束至少有两种写法一种是最小化最大负载属于 min-max 目标可以通过引入辅助变量 t 线性化另一种是最小化各站负载的方差属于二次目标规模大时求解器会明显变慢。选哪一种要看你论文里怎么定义“均衡度”——用变异系数标准差除以均值还是用最大最小负载比定义完再选模型顺序不能反。2.3 阅卷视角摘要、假设、结果检验三段各占多少印象分建模竞赛的评阅是先看摘要定档再翻正文找证据。摘要里如果只有“建立了数学模型并求解”这种话档位就定死了。真正有效的摘要句式是带数字的在建设成本为 X 元的假设下最优方案为 N 个站点总成本 Y 元平均配送距离 Z 公里最大单站负载率不超过 W%。模型假设部分写“假设道路畅通、车辆匀速”没问题但要紧接着说明这个假设会带来什么偏差、后文怎么处理。比如“假设匀速 20km/h实际早晚高峰会延长在途时间因此第五节的灵敏度分析中将服务半径下调 10% 做对照”。假设和后面的检验对上才叫闭环。结果检验是多数队伍的分水岭。只报一个最优解等于放弃了三分之一的分数。至少要给出两组曲线一是建设成本从低到高变化时最优站点数的台阶图二是服务半径从 2 km 扫到 5 km 时最少站点数的变化。两条曲线一画“为什么是 4 个站不是 3 个”这个问题自己就回答了。3. 高频考点精讲距离矩阵、p-中位、集合覆盖、负载均衡四个必会动作3.1 距离矩阵把 92 行坐标变成一张 92×92 的作战地图所有后续模型都建立在这张矩阵上它算错了后面全错。两种算法要都实现才能做对比。直连算法用欧氏距离一行代码搞定路网算法用 Floyd 或 Dijkstra输入是附件里的道路邻接表。注意道路数据往往不是完全图存在走不通的点对距离要设成无穷大并且在后续约束里显式跳过否则求解器会报不可行或者把网点分配到根本不连通的地方。import numpy as np import pandas as pd from scipy.spatial.distance import cdist # 附件读取网点坐标单位千米与日订货量单位吨 nodes pd.read_csv(nodes.csv) # 列id, x, y, demand coords nodes[[x, y]].to_numpy() # 形状 (92, 2) demand nodes[demand].to_numpy() # 形状 (92,) # 方案一直线欧氏距离矩阵形状 (92, 92) D_euclid cdist(coords, coords, metriceuclidean) # 方案二路网最短路径输入邻接矩阵 WW[i][j] 为边长不通为 inf n len(nodes) W np.full((n, n), np.inf) np.fill_diagonal(W, 0) for u, v, length in pd.read_csv(roads.csv)[[u, v, length]].to_numpy(): W[int(u), int(v)] W[int(v), int(u)] float(length) # 双向道路 D_road W.copy() for k in range(n): # Floyd 三重循环92 规模毫秒级 D_road np.minimum(D_road, D_road[:, k:k1] D_road[k:k1, :]) print(连通性检查, np.isinf(D_road).sum(), 个不可达点对)这段代码有两个关键点。第一路网矩阵初始化时对角线必须置 0、其余置无穷不能置 0否则 Floyd 会把所有点对压成 0。第二网点编号要转成从 0 开始的整数索引附件里如果是从 1 开始读进来先减一不然会数组越界。参数上唯一需要调的是距离度量方式其余都是数据。跑完之后建议打印一下两种矩阵的差异统计——平均路网距离与平均直线距离的比值通常在 1.2 到 1.5 之间如果你的结果偏离这个区间多半是道路数据读错了方向或者坐标单位没统一。注意如果某些网点在路网上不可达不要简单地把无穷大替换成直线距离那等于偷偷改了模型。正确做法是把这些点单独列出在论文里说明它们只能由直线距离最近的站点服务或者直接判定为需要单独建站。3.2 第一问无容量设施选址目标函数必须写清量纲第一问的决策是“建几个、建在哪”。设 y_j 表示在网点 j 建站x_ij 表示网点 i 由站 j 服务q_i 是日均订奶量d_ij 是距离则总成本可以写成两部分固定建设成本 F 乘以站点数加上单位运价 c 乘以运量再乘以距离。目标函数里最容易出问题的是量纲。F 的单位是元是一次性投入c·q·d 的单位是元每天是运营成本。两者直接相加在数学上没错但在论文里必须交代清楚口径——要么把 F 按投资回收期折算成元每天要么把运营成本按规划周期折算成总成本。不写这一句评阅老师一眼就能看出你的成本模型是拼凑的。import pulp n len(coords) F 8000.0 # 单个站点建设成本元/天已按回收期折算 c 2.5 # 单位运价元/(吨·公里) q demand # 日订货量吨 model pulp.LpProblem(FacilityLocation, pulp.LpMinimize) y [pulp.LpVariable(fy_{j}, catBinary) for j in range(n)] # 是否建站 x [[pulp.LpVariable(fx_{i}_{j}, catBinary) for j in range(n)] for i in range(n)] # 目标建设成本 运输成本 model F * pulp.lpSum(y) c * pulp.lpSum(q[i] * D_road[i][j] * x[i][j] for i in range(n) for j in range(n)) for i in range(n): model pulp.lpSum(x[i][j] for j in range(n)) 1 # 每个网点恰好归属一个站 for j in range(n): model x[i][j] y[j] # 未建站则不能分配 model.solve(pulp.PULP_CBC_CMD(msg0)) chosen [j for j in range(n) if y[j].value() 0.5] print(建站数量, len(chosen), 站点编号, chosen)这段是标准 UFLP约束只有两条每个网点恰好被服务一次以及“没建的站不能接活”。第二条约束看起来多余其实是整个模型的关键——没有它求解器会允许所有网点都由某个不存在的站服务目标函数直接趋近于零。F 是最值得调的参数。F 从 3000 扫到 20000每档跑一次把最优站点数记下来就是那条台阶图。你会看到某个 F 区间内站点数不变跨过一个临界值就跳一档这个临界值才是论文结论该说的话——“当单站日建设成本高于 1.1 万元时建两个站不再经济”。3.3 第二问10 分钟等于 3.33 公里把选址问题翻译成覆盖问题第二问的性质变了。第一问里远距离只是贵一点第二问里超过 3.33 km 是绝对不允许的。这就从“最小化成本”变成了“在覆盖约束下最小化站点数”也就是经典的集合覆盖。先构造覆盖矩阵 AA[i][j] 等于 1 表示站 j 能在时限内覆盖网点 i。然后让每个网点至少被一个选中的站覆盖目标是最小化被选中的站数量。这一步必须先做贪心给出上界再用整数规划求精确最优两个结果放一起论文才有说服力。R 20 * (10 / 60) # 服务半径 3.33 km A (D_road R 1e-9).astype(int) # 覆盖矩阵注意浮点容差 # 第一步贪心给上界 covered np.zeros(n, dtypebool) greedy [] while not covered.all(): gain A[~covered, :].sum(axis0) # 每个候选站能新覆盖多少未覆盖点 j int(np.argmax(gain)) if A[:, j][~covered].sum() 0: # 存在永远覆盖不到的点 print(存在孤立网点需要单独建站) break greedy.append(j) covered | (A[:, j] 1) print(贪心解站点数, len(greedy)) # 第二步整数规划求最优 scp pulp.LpProblem(SetCover, pulp.LpMinimize) y2 [pulp.LpVariable(fz_{j}, catBinary) for j in range(n)] scp pulp.lpSum(y2) for i in range(n): scp pulp.lpSum(A[i][j] * y2[j] for j in range(n)) 1 # 每点至少被覆盖一次 scp.solve(pulp.PULP_CBC_CMD(msg0)) best [j for j in range(n) if y2[j].value() 0.5] print(最优站点数, len(best), 站点编号, best)覆盖矩阵那一行的容差不能省。浮点运算里恰好等于 3.33 的距离会算成 3.3300000000000005直接比较就漏掉了一批边界网点最后站点数凭空多一个你还找不到原因这种玄学问题每届都有人踩。如果附件给出的各站建设成本不一样这个模型立刻升级成加权集合覆盖目标改成成本之和结构完全不用动。这一点写在论文里属于加分项说明你意识到“成本相同”是题目隐含的简化假设。3.4 第三问负载均衡的两种写法选完还要定义指标第三问的难点不在求解在定义。什么叫配送量均衡可以是最小化最大负载也可以是最小化负载方差还可以是让每个站的负载率落在某个区间内。min-max 写法最好求解引入变量 t约束每个站的负载都小于等于 t目标最小化 t。这是纯线性规划规模再大也扛得住。方差写法更“公平”但它是二次目标92 个点还好一旦网点数量翻倍求解时间会崩。考场上的折中办法是先用 min-max 求出理论最优的最大负载再把它放宽 5% 作为上限回头看能不能减少站点数两条曲线的转折点就是你要的方案。Q_min, Q_max 0.3, 1.5 # 单站日配送量上下限吨 bal pulp.LpProblem(BalancedFacility, pulp.LpMinimize) t pulp.LpVariable(t, lowBound0) # 最大单站负载 y3 [pulp.LpVariable(fu_{j}, catBinary) for j in range(n)] x3 [[pulp.LpVariable(fw_{i}_{j}, catBinary) for j in range(n)] for i in range(n)] bal F * pulp.lpSum(y3) t * 1000 # 成本项 均衡惩罚项 for i in range(n): bal pulp.lpSum(x3[i][j] for j in range(n)) 1 for j in range(n): bal x3[i][j] y3[j] for j in range(n): load_j pulp.lpSum(q[i] * x3[i][j] for i in range(n)) bal load_j t # 负载不超过 t bal load_j Q_max * y3[j] # 容量上限 bal load_j Q_min * y3[j] # 避免低负载浪费 bal.solve(pulp.PULP_CBC_CMD(msg0))这里有两处细节决定模型能不能跑通。第一负载上下限的约束必须乘上 y_j否则未建站的 j 会被强制要求负载大于 0模型直接不可行。第二目标函数里的 t 前面加了一个系数 1000作用是把“均衡”和“成本”放到同一量级不然求解器会觉得成本项主导一切均衡惩罚形同虚设。这个系数怎么定论文里要写一句说明属于参数标定的常规操作。解出来以后均衡度用变异系数衡量最直观各站负载的标准差除以均值数值越小越均衡。把第一问方案和第三问方案的变异系数放一张表里对比均衡换来了多少成本上升这就是完整的答案而不是一句“本方案更加均衡”。4. 真题演练四道典型小问的答题思路与可跑代码4.1 真题一给定坐标表怎么算出最少需要几个站题目原话是“配送时间不得超过 10 分钟物流车时速 20km/h求最优站点设置方案”。这道题的采分点是四步时限换算成半径、构造覆盖关系、求最小覆盖集、验证方案可行性。答题时不要一上来就写模型先说清换算10 分钟是 1/6 小时20 km/h 乘以 1/6 小时等于 3.33 km所以任何网点到其服务站的路网距离不得超过 3.33 km。这一步写出来评阅老师就知道你读懂了题意。然后是覆盖矩阵和求解代码见 3.3 节。求解结果要给出三项内容站点编号与坐标、每个站点服务的网点清单、所有被服务网点中的最大距离。第三项是自查如果最大距离超过 3.33 km说明代码里覆盖判定写错了。最后一定要补一句下界分析如果某个网点周围 3.33 km 内只有它自己那这个点必须单独建站这类“孤立点”的数量就是站点数的理论下界。最优解等于下界时可以直接宣称最优性这句话在论文里分量很重。4.2 真题二建设成本和运输成本怎么折成一个目标函数这是第一问的核心问法也是最容易被追问的地方。面试式的问法是“你凭什么把一次性的建设投入和每天的运费加在一起”标准答法分三层。第一层说清口径把建设成本按投资回收期 T 折算成日均成本 F/T这样两项都是元每天可以直接相加。第二层说清系数单位运价 c 从运输单价和车辆装载率估算给出估算依据哪怕只是量级估算也要写。第三层做灵敏度把 F 上下浮动 50%看站点数变不变不变就说明结论稳健。面试官最想听的不是公式而是“你有没有意识到这两项不同量纲”。谁主动把量纲问题拎出来讲谁就显得做过真东西。4.3 真题三配送量均衡怎么写进模型还能量化比较这道题的典型错误答法是写“我们通过调整使各站配送量尽量接近”然后没了。正确做法是三步定义指标、写进模型、给出对比。定义指标用变异系数 CV公式是标准差除以均值。写进模型用 min-max 或者容量上下限代码见 3.4 节。给出对比就是一张表列三行不均衡方案第一问结果、min-max 方案第三问结果、两者对比列站点数变化、总成本变化、CV 变化。一个常见的好结果是站点数从 4 个增加到 5 个总成本上升 8%但 CV 从 0.42 降到 0.11。这组数字本身就是结论——“用 8% 的成本换来了负载均衡度的大幅改善”比任何形容词都有说服力。提示如果 min-max 方案求出来发现某些站负载为 0那不是均衡是建了废站。这时候要回头检查是不是 y_j 没有正确约束或者容量下界设得太低。4.4 真题四面试式追问——网点从 92 个变成 1000 个怎么办这是建模答辩的经典追问考的是你有没有意识到算法的适用边界。92 个点用整数规划几分钟出结果1000 个点变量数量涨到百万级通用求解器直接卡死。答法要给出渐进方案小规模用精确求解保证最优性中大规模先做候选点筛选只在度数高、需求量大的网点里选建站位置把候选集从 1000 压到 100 以内再求解更大规模用贪心加局部搜索或者拉格朗日松弛给下界。三层方案说清楚提问的人就知道你不是只会调库。还可以补一句网点规模变大后均衡约束比距离约束更容易成为瓶颈因为负载差异会随规模放大建议把第三问的模型作为默认起点而不是附加项。5. 常见失分点五个把国奖写成成功参赛的错误答法5.1 用聚类中心当站点位置错在哪直接对 92 个坐标做 K-means把聚类中心当成建站地点结果坐标落在两个网点之间的空地上。为什么错题目白纸黑字写着“在 92 个网点位置中选择一个或多个点建设”连续空间的解根本不在可行域里属于答非所问。怎么答对如果想要聚类的思路用 K-medoids 或者把候选点限定在网点集合上的 p-中位模型本质是离散选址中心必须是真实网点。5.2 距离只用直线无视附件里的道路数据错在哪拿到坐标就 cdist把配送道路那个附件当成装饰。为什么错题目专门给了道路就是要你考虑车辆实际行驶路径用直线距离算出的 3.33 km 覆盖范围偏大站点数会少算。怎么答对两种距离都算用路网距离做主方案直线距离做对照在论文里给出“直线距离会低估约 X% 的在途时间”这样的量化结论。5.3 单位不统一10 分钟换算成 3.33 米错在哪坐标附件给的是米20 km/h 没换算成 km/min半径算出来差三个数量级覆盖矩阵全是 1最后结论是建一个站就够。为什么错物理量单位没统一这是最不该犯的错。怎么答对建模前先列一张单位表把所有量统一到千米、小时、吨写进假设部分代码里变量名带上单位后缀比如R_km、q_ton。5.4 第三问只加容量约束不做均衡错在哪看到“配送量过高会延误”就加了个每站负载上限然后宣称解决了均衡。为什么错容量约束只保证不超标不保证各站之间接近可能四个站里三个满载一个只用了三成这恰恰是题目要避免的资源浪费。怎么答对min-max 目标或者方差目标必须显式出现在目标函数里同时用变异系数给出量化对比。5.5 只交一个方案没有灵敏度分析错在哪算出一组站点编号配一张地图结束。为什么错选址模型对成本参数极其敏感只给一个解等于宣称自己的假设绝对正确评阅时会被直接质疑稳健性。怎么答对至少扫两个参数——建设成本和最大服务半径各画一条“参数取值—最优站点数”曲线指出解保持稳定的区间这比多写两页公式有用。6. 押题与打法三天复现一套能交卷的建模流程这类“选址 时限 均衡”的三问递进题近年出现频率很高变体无非是把鲜奶换成快递、把 10 分钟换成 30 分钟、把 92 个点换成 200 个点。押题不用押题面押的是这套骨架离散候选点、距离矩阵、覆盖约束、负载目标。四件事备齐换个场景直接套。具体打法我建议按三天排。第一天上午只做一件事把附件数据读干净画出 92 个点的散点图和道路网络图确认单位、确认连通性、确认有没有缺失值。下午把两种距离矩阵都算出来比较差异。这一步做扎实后面两天不会返工。第二天上午写第一问的 UFLP跑通成本扫描下午写第二问的集合覆盖贪心和整数规划各跑一遍对比站点数晚上写第三问的 min-max 模型把均衡度算出来。第三天上午补灵敏度分析和方案对比表下午只做一件事——写摘要摘要里的每个数字都必须能在正文里找到出处。工具选择上建模用 Python 加 PuLP 足够求解器用自带的 CBC92 个点的规模不用折腾商业求解器。画图用 matplotlib站点分布图、服务范围图、参数扫描曲线三张图必须清晰到能直接放进论文。地图绘制不用真实底图用散点加连线表达拓扑关系就够避免引入额外的数据依赖。有三个习惯是从翻车里长出来的。第一每个模型跑完先打印变量值和约束满足情况别等写论文时才发现某个网点没被分配。第二所有参数写在一个 cell 里不要散落在代码各处改一次参数要能重跑全流程。第三结果文件按“问题编号_参数组合”命名同一份数据跑十次不会覆盖。这些坑我基本都踩过一遍印象最深的一次是第一问交了三个站的方案第二问时限加上去之后发现必须四个站而第一问的代码是硬编码站点数的整段重写时间全浪费在重复劳动上。从那以后我每次做多问递进的题都强制走一遍“变量表—目标—约束—求解—灵敏度”这五步五步没走完不许动笔写论文。希望帮到你。配套整理的这份资料里三问的完整模型、可跑代码、参数表和一页论文骨架都在拿到手建议先别急着看结论用附件数据把 3.1 节的距离矩阵跑出来再对着 3.3 节的覆盖矩阵跑一遍贪心看看站点数和你手算的差多少——这一步走通了后面两问都是顺水推舟。本文还有配套的精品资源点击获取
