5G应急物资配送问题建模与求解：融合通信约束的VRPTW

简介这是一份针对2022年电工杯数学建模竞赛B题的完整参赛方案围绕5G网络环境下应急物资配送问题展开适合准备电工杯、国赛等数学建模竞赛的本科生和研究生参考。方案从配送车辆单独配送的VRP模型出发逐步引入无人机协同配送、车辆容量约束和物资集中点选址完整展示了问题转化、聚类分区、蚁群算法与迭代局部搜索求解的全过程。PDF全文详细给出了四个问题的建模思路、结果数据与算法实现细节包括最短路径582公里、最短配送时间6.32小时等关键结论以及k-means选址结果。资源共1个PDF文件压缩包大小2.11MB轻量便携便于直接阅读和对照复现已有5393人学习下载是学习应急物流路径优化和混合元启发式算法的优质范例。1. 5G网络环境下应急物资配送问题难的不是通信是信息与物流怎么耦合如果只看题目名字很多人会把2022数学建模电工杯B题当成一道通信题——“5G网络环境”六个字一放容易让人往基站覆盖、协议栈和峰值速率上靠。实际做下来你会发现这道题真正卡人的地方不是通信而是怎么把“5G带来的实时信息”变成一个能写进目标函数和约束的变量。应急物资配送本身是带时间窗的车辆路径问题叠加5G网络状态后它变成了动态、带通信约束的混合优化问题。这篇笔记适合两类人一类是准备数学建模竞赛、想知道B题怎么切入的人另一类是做应急物流调度的一线工程师想看看5G网络环境能给现有系统带来什么新约束和新解法。接下来我把建模思路、求解代码和踩过的坑一条条讲透。2. 应急物资配送问题怎么抽象5G网络环境改变了约束不改变问题骨架2.1 先拆题五个要素构成了一个动态化VRP数学建模电工杯B题的场景本质上是一个“应急物资从配送中心送到需求点”的调度问题。拿到题先别急着找数据先把题目里的要素拆出来需求点受灾区域或应急点每个点有物资需求量、位置坐标、期望送达时间窗。配送中心物资囤放点车辆从这里出发完成任务后返回。车辆数量有限、载重有限、速度受路网和通信状态影响。5G网络环境实时提供需求变化、路况和车辆位置数据但存在覆盖盲区、信号时延和带宽占用。决策目标多数情况下是“最小化总成本”或“最大化送达时效满意度”有时两者都写。用术语讲这是带时间窗的车辆路径问题VRPTW。5G的加入没有改变这个骨架而是把“需求信息”从静态表格改成了动态流你在t时刻做出的调度t1时刻可能就因为新需求或通信拥堵而作废。所以第一件事不是查5G协议栈有多复杂而是把问题重新定义为“动态需求下的VRPTW”。做竞赛题和做真实项目有一个通病容易把场景特效当成核心问题。5G在这里的核心影响有三个——数据采集更频繁、控制指令时延更低、车辆与调度中心的连接更稳定。但它在模型里不是一个“加一个超参数”的事。2.2 5G在模型里不是背景板覆盖半径、数据周期与时延三个参数我把5G网络环境对这个配送问题的影响压成了三个可量化参数覆盖半径R一辆车或一个需求点能否实时接入调度中心取决于所在位置是否有5G信号覆盖。没覆盖就别谈实时调度。数据更新周期T_d5G网络下需求信息和路况更新频率远高于4G但这个周期不是零。调度模型要用滚动时域接受新数据而不是一次性求解后不管。通信时延T_l指令从中心下发到车辆执行存在时延紧急加单、紧急避让这类操作会受时延影响。在模型里这三个参数分别作用在不同的地方。覆盖半径决定可行域——如果某个需求点没有5G覆盖车辆到达后无法回传状态那么这个点要么被安排为“盲区任务”要么需要另一个中转点接力。数据更新周期决定重调度的频率时延决定时间窗约束里要预留多少缓冲。很多队伍在这里犯的第一个错是把5G网络环境当成一个背景设定模型里一行注释就带过了。判卷人想看到的不是“因为5G很好所以配送更高效”而是“5G的某个具体指标进入约束导致最优解偏移”。2.3 目标函数和约束条件把时间满意度写进数学式竞赛题不像纯科研论文模型要能算出结果所以目标函数不宜太花哨。最常见的写法是双目标目标一最小化总配送成本包括车辆固定出动成本、行驶距离成本、时间窗惩罚成本。目标二最大化应急响应时效用时间满意度S(t)度量送达时间越早满意度越高。时间满意度函数一般取线性递减或S型递减。线性递减简单适合竞赛S型递减更接近真实应急场景但需要额外标定参数。我一般在论文里两个都写正文用线性灵敏度分析里用S型做对比。约束条件至少要有五条车辆载重约束每次出发装载的物资不能超过车辆容量Q。时间窗约束送达时间在需求点允许窗口内否则产生惩罚。8小时或12小时连续作业约束可以不管具体劳动法规但要保障车辆单日工作时长。5G覆盖约束目标点无覆盖时车辆需要在最近的有覆盖锚点处上报位置。需求量动态约束t时刻的需求量D_i(t) 初始需求量 累计新增变化量。这五条约束彼此咬合。覆盖约束如果写得不好模型会退化成普通VRPTW竞赛里就没有区分度。表 2-1 参数符号表以最小总成本为例符号含义取值建议N需求点数量视赛题数据而定K可调用车辆数按赛题车辆列表统计Q车辆最大载重以吨或箱为单位[a_i, b_i]需求点i的时间窗小时制精确到分钟r_i需求点i的5G覆盖半径由基站配置推算不能拍脑袋T_d数据更新周期建议设为5分钟或10分钟c1 / c2 / c3固定成本 / 单位距离成本 / 惩罚系数量纲需统一参数表看上去简单但它是后面所有算法和代码的地基。电子表格里的每一列最终都要映射到代码里的数据结构。3. 从0到1搭建配送模型用栅格覆盖判断和滚动时域把5G落进算式3.1 先把路网离散化用网格点和覆盖圆盘做可达域判断拿到题目数据后需求点一般是经纬度或平面坐标。第一件事不是直接跑路径优化而是做“可达域判断”——哪些点有5G信号哪些点没有哪些点之间能实时通信。常见做法是将整个配送区域栅格化再用基站位置和覆盖半径构成圆盘模型。圆盘模型是第一步近似足够比赛用。栅格边长我习惯取车辆平均速度乘以数据更新周期的二分之一这样单个栅格内的状态可以被一次回传覆盖。下面的代码生成栅格点并根据基站位置和覆盖半径做二值化覆盖判断import numpy as np # 配送区域范围单位千米 x_min, x_max, y_min, y_max 0, 50, 0, 50 grid_step 2 # 栅格边长2km兼顾精度和计算量 # 5G基站位置列表[[x1, y1, r1], [x2, y2, r2]] base_stations np.array([ [10, 10, 5], [30, 20, 6], [40, 40, 4], ]) # 生成栅格中心点 xs np.arange(x_min grid_step/2, x_max, grid_step) ys np.arange(y_min grid_step/2, y_max, grid_step) grid_x, grid_y np.meshgrid(xs, ys) # 判断每个栅格中心是否至少被一个基站覆盖 def is_covered(px, py, stations): for sx, sy, sr in stations[:, :3]: if (px - sx)**2 (py - sy)**2 sr**2: return True return False cover_map np.array([ [is_covered(gx, gy, base_stations) for gx, gy in zip(row_x, row_y)] for row_x, row_y in zip(grid_x, grid_y) ]) print(f栅格数量: {grid_x.size}) print(f5G覆盖栅格占比: {cover_map.mean():.2%})这段代码的核心逻辑是对每个栅格中心点遍历基站列表只要落在任意一个基站的圆盘半径内就认为这个点具备5G通信能力。参数grid_step和基站半径直接决定了覆盖占比。步长取太大覆盖边缘被吞掉取太小运算量翻倍。比赛阶段先用2到3公里做初步判断等路径算法稳定后再加密。覆盖判断的结果不要直接拿来当“能不能到达”的二元约束更稳妥的用法是生成一个“通信置信度”矩阵比如覆盖内置信度1.0覆盖外0.2再乘到时间窗惩罚系数上。这样模型不会在覆盖边界处出现不可解的硬断裂。3.2 动态需求怎么进模型滚动时域控制下的重调度框架动态需求是这道题和传统VRPTW的最大差异。5G环境下数据更新频率高意味着你每5分钟或10分钟就能获得一批新需求。如果每次都重新求解全局最优求解时间会爆炸而且新解会推翻上一轮的配送计划车辆实际执行时反而乱套。我采用的框架是滚动时域控制RHC。核心思想只在当前滚动窗口内求解部分问题窗口外的需求留到下一次更新时再考虑。具体步骤如下初始化读取当前已知需求点生成初始配送计划。执行车辆按当前计划出发但每过一个数据更新周期T_d收集最新状态。判断是否有新增需求、延迟需求或车辆故障。重调度只对受影响窗口内的需求点做局部重调度不重新优化全部路径。滚动窗口向前推进循环执行。在代码里滚动时域不需要复杂框架一个循环加一个规划函数就能表达import numpy as np # 模拟需求流每个时间窗产生新需求 all_demands [ [(x1, y1, qty1, due1), (x2, y2, qty2, due2)], # 第二个窗口的新增需求 [(x3, y3, qty3, due3)], ... ] def solve_window(known_demands, planned_routes): 对当前窗口已知需求做局部优化。 返回该窗口的新增路径与车辆任务追加列表。 # 这里接入下一章的GA或其他求解器 new_routes genetic_algorithm(known_demands, planned_routes) return new_routes # 滚动循环 rolling_window_size 3 # 3个数据更新周期 current_window 0 planned_routes [] while current_window len(all_demands): window_demands [] for i in range(rolling_window_size): idx current_window i if idx len(all_demands): window_demands all_demands[idx] planned_routes solve_window(window_demands, planned_routes) current_window 1参数rolling_window_size是关键。窗口太小每次只看到眼前的需求路径规划短视总里程明显偏高窗口太大又等于退化成全局重调度失去滚动意义。我一般取3个更新周期也就是15到30分钟的实际时间跨度兼顾实时性和路径稳定性。还有一个容易被忽略的细节滚动时域里的“已锁定的计划”要区分硬锁定和软锁定。已经出发且接近目的地的任务硬锁定不改只规划了一半的任务软锁定可以微调。这样能大幅减少车辆折返和客户满意度波动。3.3 参数表把赛题数据转换成算法输入前的三处校准代码写完后参数标定决定了模型是“看起来对”还是“真的能交”。我列出三个最值得花时间校准的地方。第一是时间窗的离散精度。日程表如果只给到“小时”你最少也要换算成分钟。把8:00到9:00这个窗口变成[480, 540]分钟。换算时注意5G的更新周期是分钟级时间窗精度不能比它粗否则模型永远感知不到实时性带来的优化空间。第二是车辆速度的设定。应急场景下车辆速度不能假设为恒定的30km/h或40km/h。5G环境下可以拿到实时路况速度应该是时变的。我在模型里取一个保守估计正常时段40km/h拥堵时段按系数0.6折算。系数不通过实测数据标定只靠官方数据那就在论文里说明取值依据并做灵敏度分析。第三是覆盖半径的校准。5G基站的覆盖能力受频段、发射功率、天线挂高影响比赛数据里如果只给基站坐标没给参数千万不要默认半径10公里。宏基站覆盖半径在城市环境通常只有200米到500米郊区可以达到1到3公里题目里的5G网络环境横跨城市和郊区R要区分场景。我一般会做一张“覆盖率-总成本”的敏感性表把所有R都跑一遍看模型结果对覆盖半径的敏感程度答辩时这个表是亮点。表 3-1 R取值对模型结果的影响示意覆盖半径R可实时通信需求点占比平均绕行距离总成本趋势0.5km32%高方案不稳定1.5km61%中中等3.0km89%低接近最优5.0km98%极低退化为普通VRP这个表的意义在于当R增大到一定程度后5G约束不再是瓶颈模型就回归到经典VRPTW。你要向读者和评委证明的是——你的方案在真实的“网络受限环境”下依然能跑出满意的解而不是仅仅在覆盖良好时有效。4. 求解方案怎么选精确算法算不动贪心初始化加遗传算法最稳4.1 精确算法在CVRPTW面前为什么撑不住题目一旦超过几十个需求点带时间窗的车辆路径问题CVRPTW的精确求解就非常吃力。分支定界法和动态规划可以求小规模最优解但复杂度是指数级。比如有30个需求点、5辆车可行解空间大概是这个量级每辆车可走的需求点序列组合是N!量级再叠加时间窗约束做剪枝。哪怕你只在论文里写“使用CPLEX求解”裁判也会追问规模到100个点时求解时间是多少。所以我从一开始就放弃纯精确算法把重点放在元启发式算法上。典型的选择有三个遗传算法GA、粒子群PSO和模拟退火SA。PSO在连续空间表现好但VRPTW是离散组合优化粒子编码麻烦SA收敛快但全局搜索能力弱于GAGA虽然调参敏感但它天然适合“车辆-需求点序列-时间窗”这种分段编码结构。我最终选了遗传算法为主、贪心算法做初始解、局部搜索做精细化的组合路线。4.2 用Python实现遗传算法的编码、选择、交叉与变异遗传算法的核心是染色体编码方式和操作算子设计。VRPTW里最常用的编码方式是双层结构第一层是车辆编号序列第二层是需求点访问顺序。但双层编码交叉起来容易产生不合法解——同一辆车的需求点数量变了载重可能超限。所以我用了一种更稳的单层编码把所有需求点排列成一个序列代表车辆1按顺序访问前几个点、车辆2访问后几个点用分隔符标记车辆切换点。下面的代码实现了这个思路的简化版import random import numpy as np # 需求点每个点有坐标、需求量、时间窗、服务时长 demands [ {id: 1, x: 5, y: 10, qty: 3, due_time: 120, service_time: 10}, {id: 2, x: 12, y: 18, qty: 4, due_time: 150, service_time: 15}, # 更多需求点... ] vehicle_capacity 20 n_vehicle 5 def chromosome_to_routes(chromosome, n_demands): 把单个需求点序列按容量切分成车辆路线 routes [] current_route [] current_load 0 for gene in chromosome: demand demands[gene] if current_load demand[qty] vehicle_capacity and current_route: routes.append(current_route) current_route [] current_load 0 current_route.append(gene) current_load demand[qty] if current_route: routes.append(current_route) # 车辆数不足时补空车 while len(routes) n_vehicle: routes.append([]) return routes[:n_vehicle] def fitness(chromosome): 适应度函数总时间惩罚越低适应度越高 routes chromosome_to_routes(chromosome, len(demands)) total_cost 0.0 for route in routes: current_time 0 for gene in route: d demands[gene] if current_time d[due_time]: total_cost 2 * (current_time - d[due_time]) # 迟到惩罚 current_time d[service_time] total_cost 30 # 车辆固定出动成本 return -total_cost # 负值最大化适应度 # 遗传算子顺序交叉OX、交换变异、锦标赛选择 def crossover(parent1, parent2, n_demands): start random.randint(0, n_demands - 2) end random.randint(start 1, n_demands - 1) child [-1] * n_demands child[start:end] parent1[start:end] p2_idx 0 for i in range(n_demands): if child[i] -1: while parent2[p2_idx] in child[start:end]: p2_idx 1 child[i] parent2[p2_idx] p2_idx 1 return child def mutate(chromosome): i, j random.sample(range(len(chromosome)), 2) chromosome[i], chromosome[j] chromosome[j], chromosome[i] return chromosome # 主循环 pop_size 80 n_generations 200 crossover_rate 0.85 mutation_rate 0.1 n_demands len(demands) population [random.sample(range(n_demands), n_demands) for _ in range(pop_size)] for gen in range(n_generations): # 计算适应度 scores [fitness(ind) for ind in population] # 锦标赛选择 new_population [] for _ in range(pop_size): competitors random.sample(list(zip(population, scores)), 3) parent max(competitors, keylambda x: x[1])[0] new_population.append(parent.copy()) # 交叉与变异 for i in range(0, pop_size, 2): if random.random() crossover_rate: c1 crossover(new_population[i], new_population[i1], n_demands) c2 crossover(new_population[i1], new_population[i], n_demands) new_population[i], new_population[i1] c1, c2 population [mutate(ind) if random.random() mutation_rate else ind for ind in new_population] # 返回最优解 best_chromosome max(population, keyfitness) best_routes chromosome_to_routes(best_chromosome, n_demands)这段代码的核心逻辑有四个点。第一染色体到路径的映射用的是“容量分段法”不显式编码车辆数只用载重自动分段。好处是交叉和变异后天然合法省去了修复非法解的代码。第二适应度函数用的是负惩罚成本越小成本越大适应度取值方便比较。第三锦标赛选择控制在3个竞争者避免选择压力过大导致早熟。第四顺序交叉OX专门保留父本中一段子序列的访问顺序其余位置按另一父本序补齐这种算子对序列型编码比较友好。参数里的pop_size、n_generations、crossover_rate、mutation_rate不是随便定的。种群80、迭代200代适合几十个需求点的问题如果需求点超过200建议把种群提到120代以上。交叉率太高优秀基因容易被拆散变异率太高算法退化为随机搜索一般保持在0.05到0.15之间。4.3 贪心初始解让收敛快起来的三个参数纯随机初始化的GA在前30代基本在“瞎试”。要想让收敛快我习惯把初始种群的三分之一换成贪心解附近扰动得到的个体。贪心初始化的逻辑很简单从配送中心出发每次选择距离当前点最近、且剩余容量能装下的需求点直到车辆满载再换下一辆。这个解的好处是总距离短坏处是时间窗表现差——只顾近不顾急。为了让时间窗也被纳入贪心决策我在选择下一个节点时改用加权评分距离权占0.4时间紧迫度权占0.4截止时间越近分数越高剩余容量匹配度占0.2贪心生成的解质量不差但多样性不够。处理办法是把最优贪心解做若干次随机的2-opt扰动生成一批“相似但不同”的个体填进初始种群。这样GA第一代就不至于太拉胯100代左右基本能收敛到稳定水平。此外精英保留策略建议每代保留前2到3个最优个体直接复制进下一代。不要把精英个体拿去交叉和变异否则最好的解可能在中途被破坏收敛曲线会像心电图一样上下跳。5. 避坑指南5G约束、动态重调度和时间窗处理里最容易翻车5.1 把5G当成一个常系数模型空有5G之名答辩一眼看穿现象论文里写着“考虑5G网络环境”模型和代码却只是在目标函数里乘了一个1.2的系数或者干脆只字不提5G参数。评委追问5G网络环境如何影响路径选择时答不上来。原因5G网络环境是题目给的情景关键词但很多人不知道怎么把它融进VRPTW。它不是一个常数也不是一句“5G带来信息实时性提升”的空话。解决把至少一个5G参数做成模型的显式约束或动态参数。最简单的做法是覆盖半径R影响需求点可达性约束复杂一点的做法是让数据更新周期T_d直接决定滚动时域的重调度间隔。哪怕是简化模型也要让5G有存在感。5.2 覆盖半径拍脑袋取大了所有节点都可达5G约束形同虚设现象覆盖半径设成10公里覆盖率达到100%模型变成了纯VRPTW。调试时发现结果特别好实际上是把题目里最关键的差异化条件删掉了。原因求“好结果”的本能让人下意识把覆盖半径调大用“全连通”掩盖模型的脆弱性。解决先从题目给的数据里找线索。如果只给基站位置没有给覆盖半径建议用两组对照一组取市区半径0.5公里一组取郊区半径2公里再统计可达需求点占比。如果覆盖率超过90%说明你的通信约束太松需要收紧或增加吞吐量限制。5.3 动态需求全量重调度晚上十点还在等求解结果现象每次收到新数据就对全局所有需求点重新调用GA迭代200代以上。耗时从几十秒变成几分钟车辆已经执行了一半计划新解下来推翻重来现场乱成一团。原因没有区分“已锁定任务”和“待规划任务”把滚动时域做成了全局重调度。解决建立任务锁定机制。已出发且剩余里程小于20%的任务直接锁定剩余里程大于50%的任务参与重调度但变更代价要加入惩罚。这样每次重调度的实际是窗口内的未执行任务求解时间控制在几秒内。5.4 时间窗按小时整点截断满意度曲线锯齿状结果没法落地现象时间窗按“小时”计算比如8:00-9:00作为[8, 9]但5G更新周期是5分钟模型里每5分钟就可能触发一次重调度时间窗粒度完全匹配不上。原因时间粒度粗导致模型的满意度函数不是平滑下降而是阶梯状跳变。车辆到达时间早5分钟可能满意度是1晚1分钟直接跌到0.8这种跳变会让优化算法无所适从。解决所有时间统一转换为分钟时间窗[8:00, 9:00]变成[480, 540]。满意度函数改用分段线性提前到达满意度1晚到不超过15分钟满意度从1线性降为0.5超过30分钟降为0。这个函数平滑GA梯度信息好惩罚系数也好调。5.5 只做车辆路径规划不做物资分配联动方案缺少应急味道现象整个方案就是“车怎么走”物资分配量是固定常量每辆车装多少货由容量自动决定。这样做出来的方案换成普通物流配送也说得通应急属性体现不出来。原因应急物资的特点是“需求会变化、资源会短缺”。如果完全假设供给充足那就不需要讨论了。解决把物资分配和路径规划做成两层耦合模型。先做一级分配——各需求点能拿多少物资再做二级路径——这些物资由谁在什么时间送达。分配阶段要考虑“迫切需要优先级”比如医疗物资和食品的紧迫度不同让GA的目标函数加一个加权满意度项权重向量来自应急优先级表。这样答辩时可以讲清楚你做的不是快递配送是应急资源调度。6. 进阶验证用灵敏度分析、对比基线和一套可复述的答辩逻辑6.1 三个灵敏度实验覆盖率、时延和需求波动模型跑出结果后不要急着写论文。先用灵敏度分析验证方案的鲁棒性这也是评委最关注的。我固定做三个实验第一个实验改变覆盖半径R从0.5到5公里看总成本变化曲线。如果曲线在R0.5到1.5之间急剧下降说明网络覆盖对配送效率影响显著你的论文就抓住了“5G网络环境”的核心。第二个实验改变数据更新周期T_d从2分钟到20分钟看重调度频率和总成本的权衡。更新太频繁计算量大但成本低更新太稀疏需求发生变化时响应慢成本反而飙升。第三个实验改变需求波动幅度在初始需求量的正负20%内随机扰动跑10次取均值和标准差。表 6-1 三个灵敏度实验的可视化输出建议实验对象横轴纵轴期望看到的结论覆盖半径R半径取值总成本成本随覆盖改善而下降后趋平更新周期T_d周期时长总成本与计算耗时存在最优区间需求波动波动幅度目标函数均值/方差方差不失控6.2 对比实验怎么设计贪心、纯GA、贪心GA三重对照论文要有说服力一个单算法结果不够。我建议做三重对照纯贪心算法、纯遗传算法随机初始化、贪心初始化GA。每组跑10次记录最优值、平均值和标准差。三组对比不仅证明你的方法有效还能让读者知道你改进的每一步贡献了什么。6.3 答辩时怎么把方案讲清楚一张图、两个参数、三个结论最后讲一个答辩技巧。不要从问题背景讲起评委听烦了。我通常直接从模型切入屏幕上放一张调度路线图和覆盖栅格图第一句话讲“我把5G网络环境压缩成覆盖半径R和数据更新周期T_d两个参数”第二句话讲“动态需求用三步滚动时域框架处理”第三句话讲“遗传算法求解和基线比有百分之多少的改进”。这三个结论要像“因为5G覆盖受限所以部分需求点需要等待或中转这导致总成本上升12%因为采用滚动时域动态需求下总成本比全量重调度下降8%”。有数字有因果才是让评委信服的逻辑链。我平时做这类问题有个习惯先把“最坏情况”跑一遍。覆盖半径设到最小需求波动设到最大看看算法是否还能给出可行解。如果最坏情况都能兜住那正常情况只是在这个兜底方案上做锦上添花。做应急配送方案稳定性和兜底能力永远比好看的最优解更重要。希望帮到你。本文还有配套的精品资源点击获取