简介这份PDF是2023年安徽建筑大学校内数学建模竞赛的鲜奶配送站点最优化设置赛题面向数学建模参赛者、供应链管理及运筹优化方向的学习者。内容完整呈现赛题背景与附件中92个网点的位置坐标、订奶量及配送道路数据并将问题系统拆解为最经济选址、10分钟配送时限约束下的站点配置、各站点配送量均衡三个子问题分别对应设施选址、车辆路径与库存控制等典型数学模型思路便于读者理解从问题分析到模型构建的完整链条。资源为单个PDF文件压缩包仅约98KB内容精炼适合打印阅读或反复推敲。目前已有3073人学习下载对于备战数学建模竞赛或研究城市生鲜配送选址问题的读者具有直接参考价值。通过研读该赛题可以掌握多目标优化、时间窗约束处理和配送均衡性分析等实用建模方法有助于提升解决实际物流难题的能力。1. 鲜奶配送站点最优化三道小题分别考什么模型鲜奶配送站点的最优化设置问题是近几年数学建模竞赛里出场率很高的一道综合性赛题。很多人第一眼以为它只是算个最短路径实际拆开看这三道小题分别对应设施选址、集合覆盖、负载均衡三个完全不同的运筹学模型每一问的评阅点都不一样。凡是拿到高分的队伍都有一个共同习惯先花半小时把 92 个网点的坐标、订奶量、配送道路数据读对再谈算法创新。这篇笔记把这道题的考点分布、高频建模方法、真题答题思路和最容易丢分的细节拆开讲适合准备参加数学建模竞赛的同学直接拿来对思路、背模型、练代码。2. 考点分布三问三模型前置数据处理决定上限2.1 题目考什么从最后一公里到设施选址赛题本身讲的是生鲜配送的最后一公里瓶颈。鲜奶配送站每天早晨要用非冷链小型物流车把当天的鲜奶送到片区内各个网点。因为鲜奶保鲜要求高配送在途时间必须尽量短同时建站成本和配送成本也要平衡。题目给出 92 个网点的位置坐标、订奶量以及网点之间的配送道路要求回答三个递进的问题。考点对应关系非常清晰问题1是在 92 个网点中选择一个或多个点建配送站目标是最经济这属于设施选址问题常用 p-中位模型或 p-中心模型问题2加上配送时间不得超过 10 分钟的硬约束同时考虑建设成本这属于集合覆盖或最大覆盖问题问题3要求各配送站点的配送量均衡防止某个站配送量过低造成资源浪费、过高延误配送这属于带容量约束的设施选址问题。子问题核心诉求对应模型常用求解手段问题1总成本最低的建站方案p-中位模型 / 重心法0-1 整数规划、枚举扫描 k问题2满足 10 分钟送达的最小建站数集合覆盖模型贪心初始解 整数规划问题3配送量均衡的再优化容量约束设施选址均衡度指标 局部调整这里要特别提醒备赛者三道题不是三个孤立的小问而是同一条逻辑链。问题1选出的站点集合是问题2的初始候选集问题2在时间约束下压缩出的站点集合又是问题3做均衡调整的基础。评阅老师很看重这种递进关系论文里如果没有体现联动分数会明显受影响。2.2 数据预处理92 个网点、订奶量、道路表怎么读这道题的数据部分通常包含三张表网点坐标表、网点订奶量表、配送道路数据表。很多队伍跳过道路表直接用坐标算欧氏距离这是一个很常见的翻车点。题目明确给出了网点之间的配送道路说明实际配送必须沿着道路走而不是直线飞过去。数据预处理的正确顺序应当是先读坐标、算距离矩阵再通过道路表修正距离矩阵得到真正的路网最短距离。如果坐标表里 92 个网点中有部分网点之间没有直接道路连接处理方式是用一个较大的惩罚值填充不可达项再调用最短路算法求出每对网点之间的最短路径距离。这样得到的最短距离矩阵才是后续所有模型的距离输入。杂交的做法是把道路数据扔掉、纯用坐标评阅老师一眼就能看出数据没有用全模型可信度直接打折。2.3 第一步操作用道路距离替换直线距离下面这段代码演示了数据预处理的核心流程先读坐标计算欧氏距离作为兜底再读道路表把有道路连接的网点对的距离替换成实际路径距离最后用弗洛伊德算法补全不可达路径。实际比赛中可以把网点间距离存入二维数组D[j][k]后续所有模型都调用这个数组。import pandas as pd import numpy as np # 读取坐标与订奶量 coords pd.read_excel(附件_网点坐标.xlsx) # 字段网点编号, x, y demand pd.read_excel(附件_订奶量.xlsx) # 字段网点编号, 订奶量 N len(coords) xy coords[[x, y]].values # 1. 先用坐标算欧氏距离作为不可达时的兜底 D np.zeros((N, N)) for i in range(N): D[i] np.sqrt(((xy - xy[i]) ** 2).sum(axis1)) # 2. 读入道路表直接相连的网点对用道路距离覆盖欧氏距离 roads pd.read_excel(附件_配送道路.xlsx) # 字段起点编号, 终点编号, 道路长度 for _, r in roads.iterrows(): u, v, dist int(r[起点编号]), int(r[终点编号]), r[道路长度] D[u, v] min(D[u, v], dist) D[v, u] min(D[v, u], dist) # 3. 不可达的网点对设为一个大数然后跑最短路补全 INF 1e9 D[D 0] INF np.fill_diagonal(D, 0) for k in range(N): D np.minimum(D, D[:, [k]] D[[k], :])这段代码里最关键的是第二步用道路长度去覆盖欧氏距离。min的作用是保留两者中更短的值防止道路表中给出的长度反而比直线距离长导致异常。第三步的弗洛伊德算法复杂度为 O(n³)对 92 个网点来说完全跑得动不需要换成更复杂的堆优化 Dijkstra。数据预处理做完后先检查对角线是否为 0、不可达项是否仍为 INF确认无误再进入建模。很多队伍后面模型解不出来回头排查发现是最短路矩阵里残留了 0导致所有网点距离都是 0这个细节务必留意。3. 问题1最经济建站方案——p-中位模型与成本曲线3.1 为什么选 p-中位模型而不是重心法问题1要求在 92 个网点中选择一个或多个点建设配送站综合考虑配送速度、配送成本和建设成本给出最经济的方案。这里有两个候选思路重心法适合连续型选址但本题配送站只能在网点位置上选属于离散选址所以重心法天然不合适更贴合的是 p-中位模型也就是从 N 个候选点中选 p 个设施使所有需求点到最近设施的距离与需求量的加权和最小。p-中位模型的核心逻辑是每建一个站覆盖一片区域配送成本等于各网点订奶量乘以到所属配送站的距离。建设成本体现为固定成本项配送成本体现为距离加权项两者之和就是总成本。这里需要强调一个考点题里没有直接给出建设成本的具体数值通常需要自行假设一个量级并在论文里做敏感性分析。常见做法是设单站建设成本为一个常数 C分别取 C 的不同量级观察最终选址结果是否稳定。3.2 0-1 整数规划怎么写变量、目标、约束用整数规划表达 p-中位模型时需要定义两组决策变量x[i]表示网点 i 是否建设配送站取值 0 或 1y[i][j]表示网点 j 是否由网点 i 处的配送站服务取值 0 或 1。目标函数是建设成本与配送成本之和的最小化约束条件有三个每个网点必须分配给一个配送站未建配送站的网点不能承接任何分配资源约束即建站总数限制。from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpBinary prob LpProblem(p_median_model, LpMinimize) # x[i] 1 表示在网点 i 建站y[i][j] 1 表示 j 由 i 配送 x {i: LpVariable(fx_{i}, catLpBinary) for i in range(N)} y {(i, j): LpVariable(fy_{i}_{j}, catLpBinary) for i in range(N) for j in range(N)} build_cost [C] * N # 单站建设成本C 需要按题目假设后做敏感性分析 dist D # 上一步预处理得到的路网最短距离矩阵 weight demand[订奶量].values # 目标建设成本 配送成本 prob lpSum(x[i] * build_cost[i] for i in range(N)) \ lpSum(y[i, j] * dist[i][j] * weight[j] for i in range(N) for j in range(N)) # 约束1每个网点且只能由一个配送站服务 for j in range(N): prob lpSum(y[i, j] for i in range(N)) 1 # 约束2只有建了站的位置才能提供服务 for i in range(N): for j in range(N): prob y[i, j] x[i] # 约束3建站总数不超过 p p 5 prob lpSum(x[i] for i in range(N)) p目标函数里dist[i][j] * weight[j]的含义是网点 j 的订奶量乘以到配送站 i 的路网距离等价于运输的吨公里成本。如果把配送成本视作与距离线性相关这个目标函数就是总物流成本。约束 2 是一个典型的逻辑约束它保证了服务关系只能指向已建站节点如果没有这一条整数规划会把所有网点分配到成本最接近 0 的未建站节点结果完全失真。直接求解 92 个网点、92 个候选站的完整 0-1 规划变量数会接近 8500 个看起来吓人但对 CBC 这类开源求解器来说规模并不大通常几秒到几十秒就能出结果。3.3 真题演练扫描候选站数量 k 并画成本曲线p-中位模型中 p 是未知数题目没有限定建站数量所以正确的答题思路是让 p 从 1 开始逐步增加到 10 或 15每取一个 p 就求解一次最短路记录对应的最小配送成本再叠加建设成本观察总成本曲线的变化趋势。总成本通常是先下降后上升的 U 形曲线最低点对应最优建站数 k。这个扫描 k 画成本曲线的做法是问题1最标准、最容易被评阅认可的呈现方式。results [] best_total float(inf) best_p None for p in range(1, 16): # 每次只需把上面整数规划里的约束3改为 x 的总和 p # 求解后得到最小配送成本 delivery_cost 和建站数量 p total_cost C * p delivery_cost results.append((p, total_cost)) if total_cost best_total: best_total total_cost best_p p print(f最优建站数量: {best_p}, 最小总成本: {best_total:.2f})扫描完成之后论文里应当放一张表列出 p 取 1 到 15 时各自的配送成本、建设成本、总成本并标出最优方案。评阅老师最想看到的是你解释清楚为什么成本最低点是 p而不是只贴一行结果。注意如果建设成本 C 取得很小成本曲线可能单调下降最优解就是建满 92 个网点这明显不合理这时候需要回头调整 C 的量级或者补充一个最低建站数量的限制。这类问题在赛题里通常不会给足参数所以要把参数假设 敏感性分析写进论文才算把这一问答完整。4. 问题2与问题310 分钟硬约束下的覆盖选址和配送量均衡4.1 10 分钟限制的换算3.33 公里半径问题2新增了两个条件配送站点到网点的配送时间不得超过 10 分钟物流车时速为 20km/h。很多人在这里急着建模却忘了先做单位换算。20km/h 等于每分钟 1/3 公里10 分钟对应的最大配送距离约为 3.33 公里。也就是说任何一个配送站只能服务路网距离在 3.33 公里以内的网点。超过这个距离的网点不可达必须在论文里明确说明这一点。这里有两个细节值得注意第一距离必须用道路距离不是直线距离所以问题2的可行性判断要基于第 2 章预处理得到的最短距离矩阵第二3.33 公里半径是理论极限实际配送还有装车时间、卸货时间、红绿灯等待如果论文里能加一个实际运行时间系数比如打 0.85 折扣把有效半径压缩到约 2.8 公里这个细节会让模型的工程合理性明显提升。这属于一类非常讨喜的加分操作因为它体现的不是算法难度而是对实际业务的理解。4.2 集合覆盖的贪心初始解与整数规划最优解在 3.33 公里的半径约束下问题2的目标变成至少建几个配送站才能让所有 92 个网点都能在 10 分钟内被覆盖到。这是一个标准的集合覆盖问题。每个候选配送站都有一个覆盖集合也就是它 3.33 公里半径内能到达的全部网点。选择最少数量的配送站使这些覆盖集合的并集等于全部网点。求解集合覆盖最直观的方法是贪心算法每次选择覆盖未覆盖网点数量最多的候选站直到所有网点都被覆盖。贪心得到的站点数通常已经比较接近最优值可以作为初始解再用 0-1 整数规划验证最优性。R 3.33 # 10分钟配送半径单位 km # cover[i] 为网点 i 作为配送站时能覆盖的网点集合 cover [] for i in range(N): cover.append({j for j in range(N) if D[i][j] R}) # 贪心每次挑能覆盖最多未覆盖网点的候选站 uncovered set(range(N)) selected [] while uncovered: best None best_gain -1 for i in range(N): gain len(uncovered cover[i]) if gain best_gain: best_gain gain best i selected.append(best) uncovered - cover[best] print(贪心选择的配送站:, selected) print(未覆盖网点数:, len(uncovered))贪心算法的优点是快缺点是可能选到局部最优。比如有两个站点分别能覆盖 30 和 28 个网点贪心先选第一个结果第二个站点被迫与另一个站点大量重复覆盖最终反而需要更多站点。所以贪心结果只能作为上界真正的答题思路应当是用贪心结果确定最优站点数的范围然后固定 p 为这个值再用集合覆盖的整数规划求解验证是否存在更少的站数。论文中要把贪心和整数规划两者都写上并注明贪心作为初始启发式整数规划负责最优性验证这个表述非常加分。4.3 配送量均衡容量约束与均衡度指标问题3是整个赛题里最容易答偏的一问。题目说的是一个配送站的鲜奶配送量过低会造成资源浪费配送量过高则会延误配送需要重新给出考虑配送量均衡的最优配送站设置方案。注意题目没有给出每个配送站的容量上限数值所以这一问的考点不是在约束里写死一个容量值而是设计一个合理的均衡度指标然后让模型去优化这个指标。常用的均衡度指标有三个各配送站配送量的方差、变异系数、峰均比。峰均比定义为最大站配送量除以平均站配送量越接近 1 表示越均衡。建模时可以在问题2得到的站址基础上重新对网点做分配使得每个站的配送量尽量接近总配送量除以站数的平均值同时保证 3.33 公里的时间约束不破坏。这个过程本质上是把原来的就近分配改成带容量均衡的分配属于容量约束设施选址问题。4.4 真题演练均衡度计算代码第三问建议先做一次就近分配算出每个站点的配送量再用均衡度指标判断是否需要调整。下面这段代码演示了均衡度计算的全过程先模拟一个分配结果再输出各站配送量和两个核心指标。import numpy as np # assignment[j] 表示网点 j 被分配到哪个配送站编号来自问题(2)的选址结果 station_demand np.zeros(len(selected_stations)) for j in range(N): station_demand[assignment[j]] demand[订奶量].values[j] max_load station_demand.max() avg_load station_demand.mean() cv station_demand.std() / avg_load # 变异系数 cr max_load / avg_load # 峰均比 print(各配送站配送量:, station_demand) print(f峰值配送量: {max_load:.2f}) print(f平均配送量: {avg_load:.2f}) print(f峰均比: {cr:.2f}) print(f变异系数: {cv:.2f})如果峰均比超过 1.5或者变异系数超过 0.3就可以认为配送量明显不均衡需要把高负荷站的某些网点重新分配给低负荷站。具体做法是先对低收入的服务网店按需求量从大到小排序依次尝试挪到仍满足 3.33 公里约束的邻近低负荷配送站每挪一次就重新计算均衡度指标直到指标进入合理区间。把这个过程写成伪代码放进论文配合前后均衡度指标对比第三问的答题完整度就很高。5. 易错点这道题最常丢分的五个细节5.1 时间单位换算翻车10 分钟不是 10 公里错在哪直接把10 分钟当作配送距离或者把 20 除以 10 得出 2 公里再或者干脆不换算建模时用时间当距离。原因车速 20km/h 这个条件给了但容易被忽略。正确做法是先把 10 分钟换成 1/6 小时再乘以 20km/h得到 3.33 公里。任何用到这个数值的覆盖判断、半径设置、距离矩阵筛选都必须以 3.33 公里为准。这类题只要结果表里出现超过 3.33 公里的配送弧段评阅老师就知道换算错了。5.2 忽略配送道路直接把坐标当距离错在哪只用网点坐标算欧氏距离建模型配送道路表完全没读。原因坐标表看起来最直观道路表读起来要额外处理很多队伍图省事就跳过了。正确做法是必须先用道路表生成邻接矩阵跑最短路得到真正的路网距离。如果网点之间道路数据确实不完整可以退一步用欧氏距离但要在论文里明确说明本文由于道路数据缺失使用欧氏距离作为近似这比默默忽略要诚实得多。只要道路表存在就应当优先使用道路距离。5.3 三问不联动第三问从零开始做错在哪问题1自己建一套模型问题2又从头来一遍问题3再换一套方法三个结果之间没有任何关系。原因没意识到这三问是同一批数据的递进深化。正确做法是把问题1的选址结果作为问题2的候选站点集问题2的站址作为问题3的初始分配基础。论文里建议画一张模型递进关系的说明明确写出问题2以问题1最优建站数为上界问题3以问题2的站址为初始解做均衡调整这一句话就能让评阅老师看明白你的整体思路。5.4 均衡只做定性描述不给量化指标错在哪在论文里写各配送站配送量基本均衡相差不大就结束了没有数据支撑。原因很多队伍不知道怎么量化均衡或者觉得图表能说明问题就不用写指标。正确做法是至少给出三个数值各配送站配送量的列表、峰均比、变异系数。如果优化后峰均比从 2.1 降到了 1.2这会成为第三问最有说服力的成果。没有量化指标的均衡分析在评阅时几乎等同无效内容。5.5 建站成本口径不清总成本还是单站成本错在哪假设建站成本时一会儿当作所有站点总预算一会儿当作每个站点单独成本导致目标函数数值乱套。原因赛题没有直接给建设成本具体数值需要自行假设假设过程没有写清楚。正确做法是论文里明确规定设单站建设成本为 C总建设成本等于 C 乘以建站数量。然后对 C 取不同量级做敏感性分析比如 C 取 100、500、1000 三档观察最优建站数量是否变化。这样既避免了口径混乱又主动做了评阅老师爱看的敏感性分析。6. 答题技巧一套可靠的建模交付流程6.1 每道题的标准答题链这道题的高分套路其实非常固定每道小题都按问题转化 → 模型选择 → 决策变量与目标约束 → 求解 → 结果表 → 敏感性分析六步走。问题1用 p-中位整数规划加扫描曲线问题2先把时间换成 3.33 公里半径再用贪心加整数规划验证问题3先算均衡度指标再做容量均衡的重新分配。每一步都要在论文里说清楚为什么选这个模型而不是只说我用了什么算法。答题时间上建议按 3-2-1 分配3 小时用在数据预处理和三个模型构建上2 小时用于求解和画图1 小时写论文核心部分。这道题建站成本参数是开放的所以论文最后务必留 20 分钟做参数敏感性分析这是拉分的关键。6.2 论文呈现的三个硬要求第一结果表必须完整每个问题的站点编号、覆盖网点数、配送量都要有列表或图表。第二代码不能只贴不用关键求解代码要配合文字说明决策变量的含义。第三要做到三问结论联动问题2的站址是问题1结果的收窄问题3的均衡结果是问题2的优化。如果论文能明确写出这种递进评阅老师会认为整篇文章是一个整体工程而不是三道拼凑的题。我从这道题里学到的最大教训是数学建模竞赛高分的核心不是算法有多炫而是数据读得全、单位换得对、模型选得准、结果讲得清。从那以后我每次拿到赛题都会强制走一遍单位换算 → 数据预处理 → 模型递进 → 量化指标 → 敏感性分析的流程五分钟内就能把题目拆完后面的路就顺了。希望帮到你。本文还有配套的精品资源点击获取
简介这份PDF是2023年安徽建筑大学校内数学建模竞赛的鲜奶配送站点最优化设置赛题面向数学建模参赛者、供应链管理及运筹优化方向的学习者。内容完整呈现赛题背景与附件中92个网点的位置坐标、订奶量及配送道路数据并将问题系统拆解为最经济选址、10分钟配送时限约束下的站点配置、各站点配送量均衡三个子问题分别对应设施选址、车辆路径与库存控制等典型数学模型思路便于读者理解从问题分析到模型构建的完整链条。资源为单个PDF文件压缩包仅约98KB内容精炼适合打印阅读或反复推敲。目前已有3073人学习下载对于备战数学建模竞赛或研究城市生鲜配送选址问题的读者具有直接参考价值。通过研读该赛题可以掌握多目标优化、时间窗约束处理和配送均衡性分析等实用建模方法有助于提升解决实际物流难题的能力。1. 鲜奶配送站点最优化三道小题分别考什么模型鲜奶配送站点的最优化设置问题是近几年数学建模竞赛里出场率很高的一道综合性赛题。很多人第一眼以为它只是算个最短路径实际拆开看这三道小题分别对应设施选址、集合覆盖、负载均衡三个完全不同的运筹学模型每一问的评阅点都不一样。凡是拿到高分的队伍都有一个共同习惯先花半小时把 92 个网点的坐标、订奶量、配送道路数据读对再谈算法创新。这篇笔记把这道题的考点分布、高频建模方法、真题答题思路和最容易丢分的细节拆开讲适合准备参加数学建模竞赛的同学直接拿来对思路、背模型、练代码。2. 考点分布三问三模型前置数据处理决定上限2.1 题目考什么从最后一公里到设施选址赛题本身讲的是生鲜配送的最后一公里瓶颈。鲜奶配送站每天早晨要用非冷链小型物流车把当天的鲜奶送到片区内各个网点。因为鲜奶保鲜要求高配送在途时间必须尽量短同时建站成本和配送成本也要平衡。题目给出 92 个网点的位置坐标、订奶量以及网点之间的配送道路要求回答三个递进的问题。考点对应关系非常清晰问题1是在 92 个网点中选择一个或多个点建配送站目标是最经济这属于设施选址问题常用 p-中位模型或 p-中心模型问题2加上配送时间不得超过 10 分钟的硬约束同时考虑建设成本这属于集合覆盖或最大覆盖问题问题3要求各配送站点的配送量均衡防止某个站配送量过低造成资源浪费、过高延误配送这属于带容量约束的设施选址问题。子问题核心诉求对应模型常用求解手段问题1总成本最低的建站方案p-中位模型 / 重心法0-1 整数规划、枚举扫描 k问题2满足 10 分钟送达的最小建站数集合覆盖模型贪心初始解 整数规划问题3配送量均衡的再优化容量约束设施选址均衡度指标 局部调整这里要特别提醒备赛者三道题不是三个孤立的小问而是同一条逻辑链。问题1选出的站点集合是问题2的初始候选集问题2在时间约束下压缩出的站点集合又是问题3做均衡调整的基础。评阅老师很看重这种递进关系论文里如果没有体现联动分数会明显受影响。2.2 数据预处理92 个网点、订奶量、道路表怎么读这道题的数据部分通常包含三张表网点坐标表、网点订奶量表、配送道路数据表。很多队伍跳过道路表直接用坐标算欧氏距离这是一个很常见的翻车点。题目明确给出了网点之间的配送道路说明实际配送必须沿着道路走而不是直线飞过去。数据预处理的正确顺序应当是先读坐标、算距离矩阵再通过道路表修正距离矩阵得到真正的路网最短距离。如果坐标表里 92 个网点中有部分网点之间没有直接道路连接处理方式是用一个较大的惩罚值填充不可达项再调用最短路算法求出每对网点之间的最短路径距离。这样得到的最短距离矩阵才是后续所有模型的距离输入。杂交的做法是把道路数据扔掉、纯用坐标评阅老师一眼就能看出数据没有用全模型可信度直接打折。2.3 第一步操作用道路距离替换直线距离下面这段代码演示了数据预处理的核心流程先读坐标计算欧氏距离作为兜底再读道路表把有道路连接的网点对的距离替换成实际路径距离最后用弗洛伊德算法补全不可达路径。实际比赛中可以把网点间距离存入二维数组D[j][k]后续所有模型都调用这个数组。import pandas as pd import numpy as np # 读取坐标与订奶量 coords pd.read_excel(附件_网点坐标.xlsx) # 字段网点编号, x, y demand pd.read_excel(附件_订奶量.xlsx) # 字段网点编号, 订奶量 N len(coords) xy coords[[x, y]].values # 1. 先用坐标算欧氏距离作为不可达时的兜底 D np.zeros((N, N)) for i in range(N): D[i] np.sqrt(((xy - xy[i]) ** 2).sum(axis1)) # 2. 读入道路表直接相连的网点对用道路距离覆盖欧氏距离 roads pd.read_excel(附件_配送道路.xlsx) # 字段起点编号, 终点编号, 道路长度 for _, r in roads.iterrows(): u, v, dist int(r[起点编号]), int(r[终点编号]), r[道路长度] D[u, v] min(D[u, v], dist) D[v, u] min(D[v, u], dist) # 3. 不可达的网点对设为一个大数然后跑最短路补全 INF 1e9 D[D 0] INF np.fill_diagonal(D, 0) for k in range(N): D np.minimum(D, D[:, [k]] D[[k], :])这段代码里最关键的是第二步用道路长度去覆盖欧氏距离。min的作用是保留两者中更短的值防止道路表中给出的长度反而比直线距离长导致异常。第三步的弗洛伊德算法复杂度为 O(n³)对 92 个网点来说完全跑得动不需要换成更复杂的堆优化 Dijkstra。数据预处理做完后先检查对角线是否为 0、不可达项是否仍为 INF确认无误再进入建模。很多队伍后面模型解不出来回头排查发现是最短路矩阵里残留了 0导致所有网点距离都是 0这个细节务必留意。3. 问题1最经济建站方案——p-中位模型与成本曲线3.1 为什么选 p-中位模型而不是重心法问题1要求在 92 个网点中选择一个或多个点建设配送站综合考虑配送速度、配送成本和建设成本给出最经济的方案。这里有两个候选思路重心法适合连续型选址但本题配送站只能在网点位置上选属于离散选址所以重心法天然不合适更贴合的是 p-中位模型也就是从 N 个候选点中选 p 个设施使所有需求点到最近设施的距离与需求量的加权和最小。p-中位模型的核心逻辑是每建一个站覆盖一片区域配送成本等于各网点订奶量乘以到所属配送站的距离。建设成本体现为固定成本项配送成本体现为距离加权项两者之和就是总成本。这里需要强调一个考点题里没有直接给出建设成本的具体数值通常需要自行假设一个量级并在论文里做敏感性分析。常见做法是设单站建设成本为一个常数 C分别取 C 的不同量级观察最终选址结果是否稳定。3.2 0-1 整数规划怎么写变量、目标、约束用整数规划表达 p-中位模型时需要定义两组决策变量x[i]表示网点 i 是否建设配送站取值 0 或 1y[i][j]表示网点 j 是否由网点 i 处的配送站服务取值 0 或 1。目标函数是建设成本与配送成本之和的最小化约束条件有三个每个网点必须分配给一个配送站未建配送站的网点不能承接任何分配资源约束即建站总数限制。from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpBinary prob LpProblem(p_median_model, LpMinimize) # x[i] 1 表示在网点 i 建站y[i][j] 1 表示 j 由 i 配送 x {i: LpVariable(fx_{i}, catLpBinary) for i in range(N)} y {(i, j): LpVariable(fy_{i}_{j}, catLpBinary) for i in range(N) for j in range(N)} build_cost [C] * N # 单站建设成本C 需要按题目假设后做敏感性分析 dist D # 上一步预处理得到的路网最短距离矩阵 weight demand[订奶量].values # 目标建设成本 配送成本 prob lpSum(x[i] * build_cost[i] for i in range(N)) \ lpSum(y[i, j] * dist[i][j] * weight[j] for i in range(N) for j in range(N)) # 约束1每个网点且只能由一个配送站服务 for j in range(N): prob lpSum(y[i, j] for i in range(N)) 1 # 约束2只有建了站的位置才能提供服务 for i in range(N): for j in range(N): prob y[i, j] x[i] # 约束3建站总数不超过 p p 5 prob lpSum(x[i] for i in range(N)) p目标函数里dist[i][j] * weight[j]的含义是网点 j 的订奶量乘以到配送站 i 的路网距离等价于运输的吨公里成本。如果把配送成本视作与距离线性相关这个目标函数就是总物流成本。约束 2 是一个典型的逻辑约束它保证了服务关系只能指向已建站节点如果没有这一条整数规划会把所有网点分配到成本最接近 0 的未建站节点结果完全失真。直接求解 92 个网点、92 个候选站的完整 0-1 规划变量数会接近 8500 个看起来吓人但对 CBC 这类开源求解器来说规模并不大通常几秒到几十秒就能出结果。3.3 真题演练扫描候选站数量 k 并画成本曲线p-中位模型中 p 是未知数题目没有限定建站数量所以正确的答题思路是让 p 从 1 开始逐步增加到 10 或 15每取一个 p 就求解一次最短路记录对应的最小配送成本再叠加建设成本观察总成本曲线的变化趋势。总成本通常是先下降后上升的 U 形曲线最低点对应最优建站数 k。这个扫描 k 画成本曲线的做法是问题1最标准、最容易被评阅认可的呈现方式。results [] best_total float(inf) best_p None for p in range(1, 16): # 每次只需把上面整数规划里的约束3改为 x 的总和 p # 求解后得到最小配送成本 delivery_cost 和建站数量 p total_cost C * p delivery_cost results.append((p, total_cost)) if total_cost best_total: best_total total_cost best_p p print(f最优建站数量: {best_p}, 最小总成本: {best_total:.2f})扫描完成之后论文里应当放一张表列出 p 取 1 到 15 时各自的配送成本、建设成本、总成本并标出最优方案。评阅老师最想看到的是你解释清楚为什么成本最低点是 p而不是只贴一行结果。注意如果建设成本 C 取得很小成本曲线可能单调下降最优解就是建满 92 个网点这明显不合理这时候需要回头调整 C 的量级或者补充一个最低建站数量的限制。这类问题在赛题里通常不会给足参数所以要把参数假设 敏感性分析写进论文才算把这一问答完整。4. 问题2与问题310 分钟硬约束下的覆盖选址和配送量均衡4.1 10 分钟限制的换算3.33 公里半径问题2新增了两个条件配送站点到网点的配送时间不得超过 10 分钟物流车时速为 20km/h。很多人在这里急着建模却忘了先做单位换算。20km/h 等于每分钟 1/3 公里10 分钟对应的最大配送距离约为 3.33 公里。也就是说任何一个配送站只能服务路网距离在 3.33 公里以内的网点。超过这个距离的网点不可达必须在论文里明确说明这一点。这里有两个细节值得注意第一距离必须用道路距离不是直线距离所以问题2的可行性判断要基于第 2 章预处理得到的最短距离矩阵第二3.33 公里半径是理论极限实际配送还有装车时间、卸货时间、红绿灯等待如果论文里能加一个实际运行时间系数比如打 0.85 折扣把有效半径压缩到约 2.8 公里这个细节会让模型的工程合理性明显提升。这属于一类非常讨喜的加分操作因为它体现的不是算法难度而是对实际业务的理解。4.2 集合覆盖的贪心初始解与整数规划最优解在 3.33 公里的半径约束下问题2的目标变成至少建几个配送站才能让所有 92 个网点都能在 10 分钟内被覆盖到。这是一个标准的集合覆盖问题。每个候选配送站都有一个覆盖集合也就是它 3.33 公里半径内能到达的全部网点。选择最少数量的配送站使这些覆盖集合的并集等于全部网点。求解集合覆盖最直观的方法是贪心算法每次选择覆盖未覆盖网点数量最多的候选站直到所有网点都被覆盖。贪心得到的站点数通常已经比较接近最优值可以作为初始解再用 0-1 整数规划验证最优性。R 3.33 # 10分钟配送半径单位 km # cover[i] 为网点 i 作为配送站时能覆盖的网点集合 cover [] for i in range(N): cover.append({j for j in range(N) if D[i][j] R}) # 贪心每次挑能覆盖最多未覆盖网点的候选站 uncovered set(range(N)) selected [] while uncovered: best None best_gain -1 for i in range(N): gain len(uncovered cover[i]) if gain best_gain: best_gain gain best i selected.append(best) uncovered - cover[best] print(贪心选择的配送站:, selected) print(未覆盖网点数:, len(uncovered))贪心算法的优点是快缺点是可能选到局部最优。比如有两个站点分别能覆盖 30 和 28 个网点贪心先选第一个结果第二个站点被迫与另一个站点大量重复覆盖最终反而需要更多站点。所以贪心结果只能作为上界真正的答题思路应当是用贪心结果确定最优站点数的范围然后固定 p 为这个值再用集合覆盖的整数规划求解验证是否存在更少的站数。论文中要把贪心和整数规划两者都写上并注明贪心作为初始启发式整数规划负责最优性验证这个表述非常加分。4.3 配送量均衡容量约束与均衡度指标问题3是整个赛题里最容易答偏的一问。题目说的是一个配送站的鲜奶配送量过低会造成资源浪费配送量过高则会延误配送需要重新给出考虑配送量均衡的最优配送站设置方案。注意题目没有给出每个配送站的容量上限数值所以这一问的考点不是在约束里写死一个容量值而是设计一个合理的均衡度指标然后让模型去优化这个指标。常用的均衡度指标有三个各配送站配送量的方差、变异系数、峰均比。峰均比定义为最大站配送量除以平均站配送量越接近 1 表示越均衡。建模时可以在问题2得到的站址基础上重新对网点做分配使得每个站的配送量尽量接近总配送量除以站数的平均值同时保证 3.33 公里的时间约束不破坏。这个过程本质上是把原来的就近分配改成带容量均衡的分配属于容量约束设施选址问题。4.4 真题演练均衡度计算代码第三问建议先做一次就近分配算出每个站点的配送量再用均衡度指标判断是否需要调整。下面这段代码演示了均衡度计算的全过程先模拟一个分配结果再输出各站配送量和两个核心指标。import numpy as np # assignment[j] 表示网点 j 被分配到哪个配送站编号来自问题(2)的选址结果 station_demand np.zeros(len(selected_stations)) for j in range(N): station_demand[assignment[j]] demand[订奶量].values[j] max_load station_demand.max() avg_load station_demand.mean() cv station_demand.std() / avg_load # 变异系数 cr max_load / avg_load # 峰均比 print(各配送站配送量:, station_demand) print(f峰值配送量: {max_load:.2f}) print(f平均配送量: {avg_load:.2f}) print(f峰均比: {cr:.2f}) print(f变异系数: {cv:.2f})如果峰均比超过 1.5或者变异系数超过 0.3就可以认为配送量明显不均衡需要把高负荷站的某些网点重新分配给低负荷站。具体做法是先对低收入的服务网店按需求量从大到小排序依次尝试挪到仍满足 3.33 公里约束的邻近低负荷配送站每挪一次就重新计算均衡度指标直到指标进入合理区间。把这个过程写成伪代码放进论文配合前后均衡度指标对比第三问的答题完整度就很高。5. 易错点这道题最常丢分的五个细节5.1 时间单位换算翻车10 分钟不是 10 公里错在哪直接把10 分钟当作配送距离或者把 20 除以 10 得出 2 公里再或者干脆不换算建模时用时间当距离。原因车速 20km/h 这个条件给了但容易被忽略。正确做法是先把 10 分钟换成 1/6 小时再乘以 20km/h得到 3.33 公里。任何用到这个数值的覆盖判断、半径设置、距离矩阵筛选都必须以 3.33 公里为准。这类题只要结果表里出现超过 3.33 公里的配送弧段评阅老师就知道换算错了。5.2 忽略配送道路直接把坐标当距离错在哪只用网点坐标算欧氏距离建模型配送道路表完全没读。原因坐标表看起来最直观道路表读起来要额外处理很多队伍图省事就跳过了。正确做法是必须先用道路表生成邻接矩阵跑最短路得到真正的路网距离。如果网点之间道路数据确实不完整可以退一步用欧氏距离但要在论文里明确说明本文由于道路数据缺失使用欧氏距离作为近似这比默默忽略要诚实得多。只要道路表存在就应当优先使用道路距离。5.3 三问不联动第三问从零开始做错在哪问题1自己建一套模型问题2又从头来一遍问题3再换一套方法三个结果之间没有任何关系。原因没意识到这三问是同一批数据的递进深化。正确做法是把问题1的选址结果作为问题2的候选站点集问题2的站址作为问题3的初始分配基础。论文里建议画一张模型递进关系的说明明确写出问题2以问题1最优建站数为上界问题3以问题2的站址为初始解做均衡调整这一句话就能让评阅老师看明白你的整体思路。5.4 均衡只做定性描述不给量化指标错在哪在论文里写各配送站配送量基本均衡相差不大就结束了没有数据支撑。原因很多队伍不知道怎么量化均衡或者觉得图表能说明问题就不用写指标。正确做法是至少给出三个数值各配送站配送量的列表、峰均比、变异系数。如果优化后峰均比从 2.1 降到了 1.2这会成为第三问最有说服力的成果。没有量化指标的均衡分析在评阅时几乎等同无效内容。5.5 建站成本口径不清总成本还是单站成本错在哪假设建站成本时一会儿当作所有站点总预算一会儿当作每个站点单独成本导致目标函数数值乱套。原因赛题没有直接给建设成本具体数值需要自行假设假设过程没有写清楚。正确做法是论文里明确规定设单站建设成本为 C总建设成本等于 C 乘以建站数量。然后对 C 取不同量级做敏感性分析比如 C 取 100、500、1000 三档观察最优建站数量是否变化。这样既避免了口径混乱又主动做了评阅老师爱看的敏感性分析。6. 答题技巧一套可靠的建模交付流程6.1 每道题的标准答题链这道题的高分套路其实非常固定每道小题都按问题转化 → 模型选择 → 决策变量与目标约束 → 求解 → 结果表 → 敏感性分析六步走。问题1用 p-中位整数规划加扫描曲线问题2先把时间换成 3.33 公里半径再用贪心加整数规划验证问题3先算均衡度指标再做容量均衡的重新分配。每一步都要在论文里说清楚为什么选这个模型而不是只说我用了什么算法。答题时间上建议按 3-2-1 分配3 小时用在数据预处理和三个模型构建上2 小时用于求解和画图1 小时写论文核心部分。这道题建站成本参数是开放的所以论文最后务必留 20 分钟做参数敏感性分析这是拉分的关键。6.2 论文呈现的三个硬要求第一结果表必须完整每个问题的站点编号、覆盖网点数、配送量都要有列表或图表。第二代码不能只贴不用关键求解代码要配合文字说明决策变量的含义。第三要做到三问结论联动问题2的站址是问题1结果的收窄问题3的均衡结果是问题2的优化。如果论文能明确写出这种递进评阅老师会认为整篇文章是一个整体工程而不是三道拼凑的题。我从这道题里学到的最大教训是数学建模竞赛高分的核心不是算法有多炫而是数据读得全、单位换得对、模型选得准、结果讲得清。从那以后我每次拿到赛题都会强制走一遍单位换算 → 数据预处理 → 模型递进 → 量化指标 → 敏感性分析的流程五分钟内就能把题目拆完后面的路就顺了。希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
