鲜奶配送站点选址优化：从经验决策到整数规划与K-medoids建模

简介鲜奶配送站点的最优化设置问题常作为供应链管理与运筹学交叉的典型赛题。这份PDF收录2023年安徽建筑大学校内数学建模竞赛原题面向数学建模参赛者、物流优化学习者及运筹学爱好者内容从实际场景出发适合备赛与课程拓展。赛题以某牛奶公司92个网点坐标、订奶量与配送道路数据为背景要求分三问设计配送站选址方案先综合考虑配送速度、运输与建设成本求得最经济选址再加入10分钟配送时限及20km/h车速约束确定需增设的站点数量与位置最后兼顾各配送站点的配送量均衡避免资源浪费或延误由此引出设施选址、路径规划与库存控制的综合建模。资源为单份PDF文档体积仅98KB包含完整赛题正文、附件数据表字段说明与三个子问题的建模指向可帮助读者理解FLP、VRP及库存控制模型的应用逻辑。已有3073人浏览学习适合作为数学建模练手、课程设计或物流优化入门参考。1. 鲜奶配送站点的最优化设置从「拍脑袋定数量」到「算清楚建在哪」凌晨三点半配送车从站点出发要在早上七点前把鲜奶铺到几十个小区和便利店晚到一小时那一车货的剩余货架期就不够卖了。这事落到运营上就是一句话站点建几个、建在哪、每个站覆盖哪些需求点。标题里的「最优化设置」看着像课程论文实际是个标准的设施选址问题只不过约束条件换成鲜奶特有的时效和冷链。本文要做的就是把这个决策从「按经验拍板」变成可复现的计算流程给出模型、代码和参数让做物流规划、运筹算法或生鲜零售运营的读者能直接上手算第一版方案。先给结论这个问题的难点不在求解算法而在把现实约束翻译成参数那一步。2. 把「最优化设置」翻译成数学语言目标函数与约束怎么定2.1 决策变量、成本结构与三个常见目标鲜奶配送与普通日用品配送最大的区别是「不可等待」。日用品晚半天顶多算时效不达标鲜奶在常温或冷链中断的环境里多待一小时损耗率就肉眼可见地上升。所以选址模型里必须出现「时间」而且这个时间要同时出现在目标函数和约束条件里。先说决策变量。站点选址问题通常只有两类变量一类是「这个候选位置是否启用站点」记作 x_j另一类是「需求点 i 是否由站点 j 服务」记作 y_ij。需求点可以是小区自提点、便利店、商超也可以是社区团购的分拣点。真正干活时你会发现需求点数量从几十到几百不等候选站点也不是凭空生成的一般来自「现有可租门面、已建冷库、配送车场」这份清单。成本结构要拆细不然算出来的方案没法跟财务对账。常见的做法是拆成三块建站固定成本装修、冷柜、货架、证照按运营周期摊到每天、运输成本司机工时、车辆折旧、油耗通常折算成每小时或每公里的费用、损耗成本。损耗成本很难直接建进目标函数更实用的做法是用「新鲜度时限」把它约束住——超时的那部分需求直接判为不可服务而不是给它算一笔罚款。冷藏电费一般并入固定成本不单独拆项。目标函数有三种常见选法实际项目中按主次关系取舍目标表达式含义适用场景备注总成本最小固定成本 运输成本 损耗折价长期稳定运营最常用其余目标转约束覆盖率最大被服务需求量 / 总需求量新市场开拓约束改为至少覆盖 95% 需求量最大配送时间最小min(max 配送时长)极短保质的应急补货鲜奶场景少用因为成本会失控我一般会把「总成本最小」当主目标把覆盖率和时限全部写成约束。道理很简单鲜奶的利润薄成本多一块就是亏的覆盖率不足会直接丢点位这个用约束卡住比在目标里加权更可控。2.2 建立整数规划模型一个可以落地的表达式把上一节的内容符号化就得到一个可以直接写代码的模型。先确认输入数据I需求点集合共 n_demand 个J候选站点集合共 n_candidate 个w_i需求点 i 的日均鲜奶需求量箱/件F_j候选点 j 的日摊固定成本租金 设备折旧 人员工资c_ij从候选点 j 到需求点 i 的单位运输成本通常按「单件·每小时的运输费率」算t_ij从候选点 j 到需求点 i 的配送耗时含装卸时间T_max新鲜度时限从站点出发到需求点完成交付的最大允许时长Q_j站点 j 的日处理上限卸货月台数、冷库容量共同决定目标函数就这么写min Σ_j F_j·x_j Σ_i Σ_j c_ij·w_i·y_ij第一项是所有启用站点的固定成本第二项是运输成本。注意运输成本里乘了需求量 w_i意思是需求量大的点对运输成本的敏感度更高算法会自动把大需求点往站点附近拉。约束有四条Σ_j y_ij 1每个需求点只分配给一个站点保证不漏不重。y_ij ≤ x_j需求点只能分配到已启用的站点这是 Link 约束。t_ij·y_ij ≤ T_max任何分配都必须满足新鲜度时限超时的分配直接非法。Σ_i w_i·y_ij ≤ Q_j站点处理量不能超过实际接货能力。这套模型是整数规划里的经典设施选址UFLP加容量约束和时间窗约束。规模不大候选点 30 个以内、需求点 200 个以内时用现成的开源求解器或商业求解器都能在几分钟内拿到最优解。规模再大就得用启发式算法下一章展开讲。2.3 先用模型跑通模拟数据Python 最小实现数据准备模型空谈没用先造一份模拟数据把流程跑通。代码里用 numpy 生成 60 个需求点和 15 个候选站点坐标落在 10km×10km 的区域内这大概对应一个小城区或者一个大型社区集群的规模。import numpy as np rng np.random.default_rng(42) n_demand 60 # 需求点小区、便利店、商超 n_candidate 15 # 候选站点可租仓库、停车场改建点 demand_points rng.uniform(0, 10, (n_demand, 2)) # 需求点坐标 candidate_points rng.uniform(0, 10, (n_candidate, 2)) # 候选点坐标 demand_vol rng.randint(20, 100, n_demand) # 日均需求量箱 # 配送时间矩阵欧氏距离 / 平均车速 每站装卸时间 speed 25.0 # 市区平均车速 km/h含红绿灯等待 load_time 10.0 / 60.0 # 每站装卸耗时 10 分钟转成小时 dist_matrix np.sqrt(((demand_points[:, None, :] - candidate_points[None, :, :]) ** 2).sum(-1)) time_matrix dist_matrix / speed load_time print(配送时间矩阵形状:, time_matrix.shape) # (60, 15) print(最小单程配送时长: %.2f h % time_matrix.min()) print(最大单程配送时长: %.2f h % time_matrix.max())这里有两个参数要解释车速取 25km/h 不是随手写的市区配送含红绿灯、找车位、等电梯实际平均车速经常不到 30装卸时间每站 10 分钟是按「一箱箱搬下来放到冷藏柜」的工作量估的如果需求点是大型商超整托板交接可以压到 5 分钟以内这个参数要按运营实际改。time_matrix 的每一行代表一个需求点每一列代表一个候选站点后面所有算法都基于这个矩阵计算不再重复读坐标。3. 求解器之外用 K-medoids 与局部搜索算出站点位置3.1 为什么不用暴力枚举组合爆炸的直观计算可能有人觉得候选点才 15 个站点选 5 个C(15,5)3003 种组合全枚举一遍也很快。但真实项目里候选点不会只有 15 个。一个地级市的核心城区光「可租门面 有冷库的仓库 现有配送车场」就能筛出四五十个候选点如果站点要选 10 个C(50,10) 已经超过 100 亿种组合——而这还是没考虑「每个需求点分配给哪个站点」这件事。一旦需求点有 100 个暴力枚举直接在指数级爆炸中退出赛场。所以实际工程里分两步走规模小候选点 ≤ 20、需求点 ≤ 100用精确求解器拿最优解做基准规模大用启发式算法求「足够好」的解。对鲜奶站点这个场景启发式算法完全够用因为输入参数本身就有噪声——需求预测、车速、装卸时间全是估计值追求数学最优没有工程意义稳定且可解释的次优解更重要。3.2 K-medoids 选址把站点选在需求的重心附近K-medoids 是解决「从候选点里选 K 个站点」的天然算法。它的思路与 K-means 类似但有个关键区别K-medoids 的中心必须是真实存在的候选点而不是坐标平均出来的虚拟点。这正好匹配选址场景——站点必须落在可用房源上。实现上分三步随机选 K 个候选点当初始站点把每个需求点分配给配送时间最短的站点对每个簇在全部候选点里重新挑一个「簇内总配送时间最小」的点当新站点迭代到站点集合不再变化。def kmedoids(time_matrix, k, vol, max_iter100, seed0): n_demand, n_cand time_matrix.shape rng np.random.default_rng(seed) # 初始化随机选 k 个候选点作为站点 sites sorted(rng.choice(n_cand, k, replaceFalse)) for _ in range(max_iter): # 分配每个需求点找配送时间最短的站点 assign np.argmin(time_matrix[:, sites], axis1) new_sites [] for s in range(k): cluster np.where(assign s)[0] # 属于当前站点的需求点 if len(cluster) 0: new_sites.append(sites[s]) # 空簇保留原站点 continue # 加权时间成本需求量大的点权重高 cost_to_j time_matrix[cluster, :] * vol[cluster, None] best_j int(np.argmin(cost_to_j.sum(axis0))) new_sites.append(best_j) # 去重不同簇可能选到同一个候选点导致站点数不足 new_sites sorted(set(new_sites)) while len(new_sites) k: remain [j for j in range(n_cand) if j not in new_sites] new_sites.append(remain[int(rng.integers(len(remain)))]) if new_sites sites: break sites new_sites return sites, assign注意第 18 行的空簇判断和处理算法迭代中某个站点可能因为「抢不过」其他站点而分不到需求点如果不保留原站点后面会出现站点数量不足的问题。另一个坑是不同簇可能同时选同一个候选点为最优所以我用了 set 去重再随机补位。加权系数 vol 让大需求点对站点位置的「拉力」更大这也是鲜奶场景的特殊处理——一个日需求 100 箱的商超理应比日需求 20 箱的小区离站点更近。3.3 局部搜索与换入换出打破局部最优的位移K-medoids 的缺点是强依赖初始随机站点容易陷在局部最优里。工程上最有效的补救办法是加一轮「换入换出」局部搜索依次尝试把一个已选站点替换成某个未选候选点如果替换后总成本下降就接受这次替换直到没有单点替换能改善结果为止。def total_cost(sites, time_matrix, vol, fixed_cost, t_rate, T_max): 计算站点方案的总成本超时方案直接判为无穷大成本 assign np.argmin(time_matrix[:, sites], axis1) cost fixed_cost * len(sites) for i, s in enumerate(assign): j sites[s] t time_matrix[i, j] if t T_max: return np.inf # 超时限方案不可行 cost t * vol[i] * t_rate return cost def local_search(sites, time_matrix, vol, fixed_cost800.0, t_rate12.0, T_max2.0): n_cand time_matrix.shape[1] improved True while improved: improved False best_cost total_cost(sites, time_matrix, vol, fixed_cost, t_rate, T_max) for idx_old, old_site in enumerate(list(sites)): for new_site in [j for j in range(n_cand) if j not in sites]: candidate sites.copy() candidate[idx_old] new_site c total_cost(candidate, time_matrix, vol, fixed_cost, t_rate, T_max) if c best_cost: sites candidate best_cost c improved True break if improved: break return sites, best_cost这里 total_cost 有两个关键设定。一是超时直接返回无穷大让算法自动丢弃不可行方案二是固定成本乘站点数意味着每多一个站点就要多付一笔钱算法会在「多建站省运输费」和「少建站省固定成本」之间找平衡。t_rate 是每小时运输费率12 元/小时表示单车每小时的机会成本——如果实际用的是冷链车这个值要往上调到 20 以上站点数量会跟着变多因为冷链车贵缩短运输距离更划算。跑完这一轮你就有了「给定 K 个站点时的低成本方案」。剩下的事是回答「K 到底取多少」。4. 参数怎么设影响站点方案的五个关键参数与扫描曲线4.1 五个参数最影响结果固定成本、时限、候选点密度、需求权重、冷藏费率模型跑通只是第一步参数标定才是决定方案能不能落地的关键。我常用的经验是一份参数表先按运营实际情况填再逐个做敏感性分析。下面这五个参数对结果的影响最大参数含义调大时的连锁反应取值建议固定成本 F_j站点日摊成本租金设备人工站点变少单站覆盖变大配送变远按年度合同总成本除 365时限 T_max站点到需求点的最大配送时长放宽则站点变少收紧则站点加密按品控给的冷鲜时限再打 8 折候选点数量位置集合的丰富度越多越容易找到好位置求解变慢先筛到 30 个以内再进模型需求权重 w_i需求点的日均订单量大需求点会把站点「拉」向自己用近 30 天日均 早高峰加权运输费率 t_rate每小时运输成本费率越高站点越密用司机工时车辆折旧油耗实算这五个参数里最容易拍脑袋的是 F_j 和 T_max。F_j 如果只看装修和设备、漏了租金和人员工资算出来的站点数量会系统性偏多T_max 如果直接用品控给的极限值站点数量又会偏少因为极限值没有留出天气、堵车、装卸排队的安全余量。4.2 对「建几个站点」做一维扫描总成本曲线怎么读没有一种数学方法能一步算出「最优站点数」但有一个可靠的工程做法对 K 从 1 扫到 10每个 K 都跑一轮 K-medoids 局部搜索把总成本画成曲线看它在哪里出现拐点。拐点之后成本下降变缓或者开始回升那个位置就是经济上最合理的站点数。import matplotlib.pyplot as plt fixed_cost 800.0 # 每站每天固定成本元 t_rate 12.0 # 每小时运输费率元/小时 T_max 2.0 # 鲜奶时限小时 ks range(1, 11) costs [] for k in ks: sites, _ kmedoids(time_matrix, k, demand_vol) sites, cost local_search(sites, time_matrix, demand_vol, fixed_cost, t_rate, T_max) costs.append(cost) plt.plot(ks, costs, markero) plt.xlabel(站点数量 K) plt.ylabel(总日成本元) plt.title(站点数量与总成本的肘部曲线) plt.grid(True) plt.show()读这条曲线有一个常见误区不是找「最低点」而是找「拐点」。因为曲线经常在某个 K 之后下降幅度突然变小从 K4 到 K5 每多一站只省 50 元但从 K2 到 K3 每多一站省 300 元那 K3 就是性价比临界点。想多留安全余量就再加一站想控成本就停在拐点。如果曲线在某处直接回升说明固定成本已经压过运输节省之后再加站纯属浪费。4.3 新鲜度约束下的配送半径算一个可用的经验上限在跑正式模型之前我习惯先用一个手算公式估算配送半径上限用来提前筛掉明显不合理的候选点。假设站点到需求点全程冷链配送耗时 路途时间 装卸时间那么以站点为圆心、在时限内能覆盖的直线半径约等于speed 25.0 # 平均车速 km/h load_time 10.0 / 60 # 每站装卸 10 分钟 T_max 2.0 # 从站点出发到交付完成 2 小时 radius_km (T_max - load_time) * speed print(理论直线半径上限: %.1f km % radius_km) # 城市路网绕行系数一般取 1.3~1.5 radius_road radius_km / 1.4 print(考虑路网后的实际半径上限: %.1f km % radius_road)算出来理论直线半径是 47 公里左右但这是理想值。城市路网绕行系数取 1.4 后实际可服务半径只剩 33.6 公里。这个数字的意义是候选站点如果离主要需求群超过 30 公里直接排除不用浪费时间进模型。注意这是单站点直送的上限如果采用「站点在城市边缘、干线运输到前置仓再分拨」的模式这个公式不适用那就变成了两层网络设计复杂度完全不同。5. 鲜奶站点优化的五个常见坑现象、原因、解决模型和代码只是骨架真正让方案翻车的全是数据清洗和参数设计环节的细节。我把反复踩过的坑汇总成五条每条按「现象 → 原因 → 解决」讲透。5.1 坑一用直线距离代替路网时间结果全偏现象模型算出来的站点位置在几何中心各需求点到站点的配送时长看着都不超过 1.5 小时实际运营时早高峰有几条线路跑了 50 分钟还到不了鲜奶到店就剩半天货架期。原因代码里 time_matrix 用的是欧氏距离除以车速完全没考虑道路走向、单行道、跨河桥梁和早高峰拥堵。几何中心附近可能刚好是绕行系数最高的老城区。解决至少给欧氏距离乘一个绕行系数 1.3~1.5系数按城区拥堵程度取。预算允许就让运营部门导一份真实 OD 时间矩阵用地图 API 批量算「候选点→需求点」的预计行车时长直接替换 time_matrix。这是方案能不能落地的分水岭。5.2 坑二需求全天平均化早高峰直接击穿现象方案建设时按「日均订单量」设计站点容量上线后发现每天早上 6 到 9 点订单占比超过全天 50%站点收货区排长队最后一趟车晚发两个小时。原因鲜奶需求高度集中在早餐时段把 24 小时需求平均到每个小时会让容量设计严重偏松。模型里用的 w_i 是日总量配送时间是按线路时长算的没考虑同时段发车能力的限制。解决把需求拆成「早高峰订单集」和「非高峰订单集」早高峰的时限 T_max 单独收紧 20%并且把站点 Q_j 设置成「早高峰 3 小时可处理量」而不是全天处理量。一个站一天能处理 3000 箱早上 3 小时能处理 1500 箱容量上限就按 1500 写。5.3 坑三只算建站成本漏了场地运营成本现象算法推荐的位置全是核心商圈附近的临街铺面单站月租金顶三个普通位置总成本一算反而比分散建站贵得多。原因固定成本 F_j 只填了装修、冷柜、证照分摊没把租金和长期人员工资摊进去。算法看到「固定成本很低」自然倾向于多建站、建在贵的地方。解决F_j 必须按「年度总成本 / 365」填全包括租金、冷柜电费、店内人员薪资、损耗预留。等候选点在模型里跑完第一轮还要抽查两三个站点拿真实租金和人工回填参数重新迭代一轮。5.4 坑四没有站点容量上限最优解停在纸面现象模型把 40 个需求点分给同一个小站点总成本确实最低但那个站点只有一个卸货月台实际每天最多接 20 个点的货。原因模型里漏写了容量约束 Q_j或者写了但没进目标函数和可行性判断。算法只看成本不考虑接不接得住于是把单子全堆给成本最低的站点。解决在 total_cost 里加容量检查站点承接的需求量总和超过 Q_j 直接判为不可行更稳妥的做法是把 Q_j 的超出部分按每箱罚款算进成本让算法自己权衡「多设一站」还是「超容量罚款」。后者更平滑不会因为硬约束导致候选解骤减。5.5 坑五用全年平均需求做单情景淡旺季两头失衡现象站点数和位置按全年平均需求量定了以后夏季旺季爆仓冬季淡季三个站点在空转冷库电费照付。原因输入数据只有一组平均需求模型输出一套静态方案没考虑需求波动。鲜奶需求有明显的季节性和促销波动单情景优化得到的是「平均状态最优」而不是「全年综合最优」。解决按旺季、淡季、平季做三组需求数据目标函数改成三个情景的总成本加权求和权重按各情景天数占比设。这样出来的站点方案会兼顾两头旺季不至于爆仓淡季也不至于养太多闲置站点。6. 进阶从静态选址到连带配送的联合优化6.1 联合优化选完址再排路线会高估成本前面这套流程是「先选站点、再按站点分配需求点」的两阶段做法优点是模型简单、可解释性强。但它的弱点在于站点定死了以后每天配送车的行驶路线是被迫接受的总里程会偏高。更好的方向是把选址和车辆路径放进同一个目标里迭代——站点候选方案变动时重新生成车辆路线两者交替优化两到三轮能得到比两阶段更低的总成本。常见做法是先跑两阶段出初版再用联合优化对初版做微调只调整边界上的站点。6.2 用离散事件仿真验证选址方案算法给出的站点方案上线前一定要用仿真验证别直接投运。我习惯按下面这张表逐项核对验证维度统计口径通过标准早高峰站点排队时长车辆到达站点到完成装货的平均等待≤ 15 分钟订单超时率交付时间超过 T_max 的订单占比≤ 2%冷柜利用率站点冷柜存放量 / 额定容量70% ~ 90%鲜奶损耗率过期报废量 / 总配送量≤ 1%仿真不需要重型引擎用离散事件模拟的思路写个 Python 脚本把订单按到达时间采样、车辆按路线表发车就能跑出一组排队和超时数据。头两版方案通常死在早高峰排队时长上调整方向也简单给排队严重的站点减量或把部分订单移到相邻站点。回头看我做过的几个模拟项目凡是顺利落地的全是在「参数标定」上花了比算法本身更多时间——T_max 反复跟运营对口径Q_j 从单站容量反推回来绕行系数拿真实行车记录验算。模型再精巧喂进去的参数是拍的结果就是一张精致的废纸。希望这篇能让你在参数上少踩几个坑把鲜奶站点这个决策从「大概齐」变成「算得清、讲得明」。希望帮到你。本文还有配套的精品资源点击获取