1. 项目背景与问题拆解当数学建模遇上“送餐危机”去年带学生参加数维杯A题“外卖骑手的送餐危机”一出来我们团队就乐了。这题太“接地气”了简直就是把每天发生在你我身边的外卖配送问题抽象成了一个经典的运筹优化模型。但乐完就发现题目背后藏着不少“坑”。所谓的“送餐危机”核心矛盾是什么是骑手在有限时间内面对动态涌入的订单、复杂的路网、不确定的交通状况和严格的平台规则时如何规划路径才能最大化送达效率、最小化超时和成本。这听起来像是一个带时间窗的车辆路径问题VRPTW但实际建模时你会发现它比教科书上的VRPTW复杂得多——订单不是一次性给全的路况是实时变化的骑手还可能同时接多个顺路单。网上能找到的很多优秀论文或开源代码比如针对“蚁群算法解决连续问题”、“全局搜索增强的改进鲸鱼算法”或者“AGV的A*算法”都为我们提供了宝贵的思路工具箱。但直接套用往往水土不服。比如你用标准的遗传算法去解可能很快得到一个“理论上”的优化路径但这个路径是否考虑了非机动车道的限制是否考虑了写字楼等电梯的等待时间是否考虑了午高峰餐馆出餐慢的随机延迟这些细节才是把论文从“纸上谈兵”变成“真枪实弹”的关键。所以这篇内容不是简单地复现我们当时的论文和程序而是想以一个过来人的身份拆解我们面对这道题时的完整思考过程、模型建立时的多次迭代、算法选型时的权衡对比以及编程实现中那些教科书不会写的“骚操作”和“踩坑实录”。无论你是正在备战数维杯、国赛、美赛的同学还是对路径优化、数学建模感兴趣的朋友希望这些从实战中沉淀下来的经验能给你带来一些不一样的启发。2. 模型构建从现实问题到数学语言的精确翻译拿到题目第一步不是急着找算法而是把模糊的“送餐危机”翻译成清晰的数学问题。我们团队当时花了将近半天时间来定义边界、做出合理假设并确定优化目标。这一步走稳了后面的算法和编程才有意义。2.1 核心要素定义与假设我们首先明确了模型中的几个核心实体和它们的属性骑手定义为移动的配送单元。每个骑手有初始位置通常为配送站或上一个送达点、载货容量能同时携带的订单数本题中通常设为有限值如3-5单、移动速度一个变量受路况影响。订单每个订单包含商家位置、顾客位置、期望送达时间窗通常是一个时间点如“30分钟内送达”我们将其处理为一个软时间窗允许超时但需惩罚、预计备餐时间、实际重量/体积用于容量约束。路网我们将配送区域抽象为一个带权图。节点包括所有商家、所有顾客、配送站、重要的道路交叉口。边的权重不是简单的欧氏距离而是预估骑行时间。这个时间是动态的与时间段平峰/高峰、天气等因素有关。基于这些实体我们做出了几个关键假设以平衡模型的复杂性与可求解性假设1订单已知性我们采用“静态-动态”混合策略。在每一个调度周期如每5分钟将已知的、尚未被分配的订单视为静态输入进行一波路径规划。这避免了完全动态规划的极端复杂性。假设2时间离散化将整个工作时间如午高峰11:00-13:00离散化为以分钟为单位的时间片便于在算法中计算和追踪时间。假设3速度简化骑手速度不是一个恒定值。我们将其建模为分段函数在商家/顾客点停留时速度为0在道路骑行时根据道路等级主干道、次干道、小巷赋予一个平均速度并在高峰时段乘以一个拥堵系数如0.7。假设4等待与惩罚骑手到达商家后若餐未备好则需等待。超时送达会产生惩罚成本惩罚函数我们设计为指数形式超时越久惩罚成本急剧上升这比线性惩罚更能体现平台对用户体验的重视。注意这些假设需要在论文中明确写出并论证其合理性。例如解释为什么采用静态-动态混合策略是因为完全实时调度对数据通信和计算能力要求极高而周期性批量处理是工业界的常见折中方案。2.2 多目标优化模型的建立送餐问题天然是一个多目标优化问题。平台关心效率送得多、成本跑得省和体验不超时。我们将其整合为一个加权单目标模型便于求解。决策变量x_{ijk} 0-1变量表示骑手k是否从节点i商家或顾客前往节点j。目标函数最小化Minimize Z w1 * T_total w2 * C_distance w3 * P_delay其中T_total所有订单的总配送完成时间makespan。最小化它意味着提升整体吞吐效率。C_distance所有骑手行驶的总距离或总时间。最小化它意味着降低油耗/电耗和骑手劳动强度。P_delay所有订单的超时惩罚总和。计算公式为 Σ max(0, t_actual - t_due)^2 * penalty_rate。使用平方项是为了让算法极度厌恶严重超时。约束条件流量平衡每个骑手从配送站出发最终返回配送站或结束于最后一个顾客点。订单服务唯一性每个订单必须被且仅被一个骑手服务一次包括取餐和送餐。时间窗约束骑手到达每个顾客点的时间t_arrive应尽量在期望时间t_due之前否则计入惩罚。容量约束骑手在任意时刻携带的订单数不能超过其最大容量。取送顺序约束对于任何一个订单骑手必须先访问商家节点i才能访问对应的顾客节点j。即t_arrive_i t_arrive_j。时间连续性约束骑手到达下一个节点j的时间等于离开上一个节点i的时间 在i点的服务时间取餐或送餐 从i到j的行程时间。这个模型本质上是一个带容量约束、软时间窗、同时取送货的车辆路径问题VRPSPDTW并且是动态分批输入的。其复杂度是NP-Hard的对于稍大规模的问题如50个订单10个骑手精确算法如分支定界在有限比赛时间内基本无法求得最优解因此必须依赖启发式或元启发式算法。3. 算法选型与设计在“最优”与“可行”之间寻找平衡明确了模型接下来就是选择“武器”。我们调研了热词中提到的多种算法并进行了组合与改进。3.1 核心算法框架大规模邻域搜索LNS为主干我们最终没有采用单一的蚁群、遗传或鲸鱼算法而是选择了大规模邻域搜索LNS作为主框架。原因在于VRP问题中解的优劣往往取决于几个关键的局部结构。LNS通过“破坏”和“修复”两个阶段迭代改进解非常灵活。破坏Destroy随机从当前解中移除一定比例如20%-30%的订单。我们设计了多种破坏算子随机移除简单随机选择订单移除。最差成本移除计算每个订单对总成本的边际贡献移除贡献最负即移除后成本下降最多的订单。这能引导搜索跳出局部最优。时间窗紧迫度移除优先移除那些时间窗最紧迫即将超时的订单为后续重新安排留出空间。修复Repair将移除的订单重新插入到当前部分解中。这里我们采用了贪婪插入和后悔值插入两种策略。贪婪插入对于每个待插入订单遍历所有骑手路径的所有可能插入位置选择使目标函数增加最小的位置进行插入。后悔值插入这是关键技巧。不是看最优插入位置的成本而是计算每个订单的“第二好”插入位置与“最好”插入位置的成本差即后悔值。优先插入后悔值最大的订单因为如果现在不把它插到最好的位置后续可能被迫插到更差的位置代价更高。LNS框架的优势在于破坏和修复算子可以像乐高积木一样自由组合和扩展方便我们融入其他算法的思想。3.2 嵌入智能优化算法进行初始解生成与局部增强单纯的LNS需要一个不错的初始解并且其搜索能力有时会陷入平台期。我们引入了热词中提到的两种算法进行增强初始解生成改进的鲸鱼优化算法WOA标准的WOA模拟鲸鱼气泡网捕食行为在连续空间搜索能力强。但我们的问题解是离散的路径序列。我们对其进行了离散化改造编码采用“顾客-骑手”关联编码。一个鲸鱼个体解表示为一个列表列表长度等于订单数每个位置的值表示负责该订单的骑手编号。至于订单在骑手路径中的具体顺序则通过一个简单的最近邻插入法根据这个分配关系来生成。位置更新离散化WOA中鲸鱼的位置更新公式会产生连续值。我们通过一个随机键Random Key策略将其离散化。例如将连续的位置值通过排序映射到骑手编号的排列上。作用改进的离散WOA被用来快速生成一批多样化的初始解种群然后从中选择最好的一个作为LNS的起点。这比完全随机生成初始解质量高得多。局部搜索变邻域搜索VNS作为修复后的增强在LNS的修复阶段得到一个完整新解后我们并不直接接受它而是以这个新解为起点进行一轮快速的变邻域搜索VNS在局部寻找更优解。邻域结构我们设计了多种小规模邻域操作如2-opt反转路径中的一段。Relocate将一个订单从一条路径的一个位置移到同一条或另一条路径的另一个位置。Exchange交换两条路径中的两个订单。搜索策略依次尝试这些邻域结构一旦某个结构找到了改进解就移动到新解并从头开始如果所有结构都尝试完仍无改进则跳出。这样我们的算法就形成了一个“改进WOA生成初始解 → LNS主循环破坏修复→ 内嵌VNS局部爬坡”的三层混合架构。LNS负责大范围的“探索”VNS负责精细的“挖掘”WOA则提供了高质量的起点。3.3 动态事件的处理机制题目隐含了动态性新订单实时涌入。我们的处理方法是周期性重优化。系统内部维护一个时钟和事件队列。每过固定的时间间隔如5分钟或当新订单积累到一定数量时触发一次重优化。重优化时输入包括所有尚未完成的订单包括正在配送途中的、所有骑手的当前位置和状态携带哪些订单、当前路径。将骑手的当前位置视为新的“虚拟配送站”将已携带但未送达的订单视为必须服务的点然后调用上述混合算法重新规划所有骑手从当前时刻往后的路径。将新的路径下发给骑手在模型中模拟。这种方法在比赛中是可行的它平衡了实时性和最优性。在实际系统中这可能就是后台调度引擎每隔几十秒到几分钟执行一次的逻辑。4. 编程实现与仿真环境搭建模型和算法是大脑程序就是手脚。我们用Python来实现因为其库丰富适合快速原型开发。4.1 数据结构设计清晰的数据结构是复杂程序的基础。class Order: def __init__(self, id, merchant_loc, customer_loc, prep_time, ready_time, due_time, weight): self.id id self.merchant merchant_loc # (x, y) self.customer customer_loc # (x, y) self.prep_time prep_time # 备餐时间分钟 self.ready_time ready_time # 预计备餐完成时间 self.due_time due_time # 期望送达时间 self.weight weight class Rider: def __init__(self, id, start_loc, capacity, speed): self.id id self.location start_loc self.capacity capacity self.speed speed # 米/分钟 self.route [] # 路径列表元素为 (node_type, node_id, arrive_time, depart_time) self.load 0 # 当前负载 self.current_orders [] # 当前携带的订单ID class Solution: def __init__(self): self.rider_assignments {} # rider_id - list of order_ids (按取送顺序) self.total_cost float(inf) # 可以缓存一些中间计算结果如时间矩阵、距离矩阵4.2 关键模块实现1. 时间矩阵计算模块这是整个仿真的基石。我们不能每次计算两点间时间都去调用路径规划API比赛中也不允许。我们采用了简化方法预先根据路网节点商家、顾客点的经纬度计算直线距离。根据道路类型和时段赋予一个速度折减系数和绕路系数。例如直线距离乘以1.3作为实际骑行距离再根据高峰/平峰除以不同的速度得到行程时间。将结果存储在一个二维数组时间矩阵中并假设在同一个调度周期内是固定的。2. 目标函数评估模块这个函数会被调用成千上万次必须高效。def evaluate_solution(solution, orders, riders, time_matrix, current_time): total_cost 0.0 total_distance 0.0 total_delay 0.0 for rider_id, order_seq in solution.rider_assignments.items(): rider riders[rider_id] current_loc rider.location current_time_for_rider current_time current_load 0 for order_id in order_seq: order orders[order_id] # 去商家 travel_time_to_merchant time_matrix[current_loc][order.merchant] arrive_at_merchant current_time_for_rider travel_time_to_merchant # 等待取餐如果提前到了 wait_at_merchant max(0, order.ready_time - arrive_at_merchant) depart_from_merchant arrive_at_merchant wait_at_merchant 1 # 1分钟取餐操作 current_load order.weight # 检查容量约束 if current_load rider.capacity: return float(inf) # 违反硬约束返回无穷大成本 # 去顾客 travel_time_to_customer time_matrix[order.merchant][order.customer] arrive_at_customer depart_from_merchant travel_time_to_customer # 计算延迟 delay max(0, arrive_at_customer - order.due_time) total_delay delay ** 2 # 平方惩罚 depart_from_customer arrive_at_customer 1 # 1分钟送餐操作 current_load - order.weight total_distance (travel_time_to_merchant travel_time_to_customer) * rider.speed current_loc order.customer current_time_for_rider depart_from_customer # 骑手最后返回配送站可选 # ... 计算返回行程并加入总距离 total_cost w1 * (current_time_for_rider - current_time) w2 * total_distance w3 * total_delay return total_cost实操心得评估函数中对硬约束如容量超限的处理直接返回一个极大的惩罚值如float(inf)可以有效地引导搜索算法自动避开不可行解区域比用复杂的约束处理逻辑更简洁高效。3. LNS破坏与修复算子实现以“最差成本移除”和“后悔值插入”为例。def worst_cost_removal(current_solution, orders, riders, num_remove): 移除对当前解成本贡献最负的num_remove个订单 order_marginal_cost {} for order_id, order in orders.items(): if order_id in current_solution.assigned_orders: # 计算移除该订单前后的成本差 cost_with evaluate_solution(current_solution, ...) # 临时创建一个移除该订单后的新解需要深拷贝并调整路径 temp_solution remove_order_from_solution(current_solution, order_id) cost_without evaluate_solution(temp_solution, ...) marginal_cost cost_without - cost_with # 如果为负说明移除它成本降低 order_marginal_cost[order_id] marginal_cost # 按边际成本排序从最负到最正选择最负的前num_remove个订单移除 orders_to_remove sorted(order_marginal_cost, keyorder_marginal_cost.get)[:num_remove] return orders_to_remove def regret_insertion(partial_solution, orders_to_insert, orders, riders): 使用后悔值启发式插入订单 uninserted orders_to_insert.copy() while uninserted: regrets {} for order_id in uninserted: best_cost float(inf) second_best_cost float(inf) best_position None # 遍历所有骑手和所有可能插入位置考虑取送配对 for rider_id, rider in riders.items(): # 生成该订单所有可能的插入位置在现有路径中插入商家点和顾客点 possible_positions generate_insertion_positions(partial_solution, rider_id, order_id) for pos in possible_positions: temp_solution insert_order_at_position(partial_solution, rider_id, order_id, pos) cost evaluate_solution(temp_solution, ...) if cost best_cost: second_best_cost best_cost best_cost cost best_position (rider_id, pos) elif cost second_best_cost: second_best_cost cost # 计算后悔值 regret second_best_cost - best_cost regrets[order_id] (regret, best_position) # 选择后悔值最大的订单进行插入 order_to_insert max(regrets, keylambda k: regrets[k][0]) rider_id, pos regrets[order_to_insert][1] partial_solution insert_order_at_position(partial_solution, rider_id, order_to_insert, pos) uninserted.remove(order_to_insert) return partial_solution4.3 仿真循环与可视化我们搭建了一个简单的离散事件仿真循环来模拟时间推进和新订单到达。import matplotlib.pyplot as plt def simulation(start_time, end_time, order_stream, riders): current_time start_time current_orders [] solution initial_solution(riders) # 初始为空解 event_log [] while current_time end_time: # 1. 接收新订单 new_orders get_new_orders(order_stream, current_time) current_orders.extend(new_orders) # 2. 判断是否触发重优化例如每5分钟或新订单超过5个 if should_reoptimize(current_time, len(new_orders)): # 3. 调用混合优化算法输入当前骑手状态和所有未完成订单 new_solution hybrid_optimization_algorithm(current_orders, riders, current_time) if new_solution.total_cost solution.total_cost: solution new_solution # 4. 更新骑手路径在仿真中就是更新route列表 dispatch_solution_to_riders(solution, riders) # 5. 推进时间模拟骑手移动和订单完成 current_time TIME_STEP update_rider_positions(riders, TIME_STEP) completed check_order_completion(riders, current_time) for order_id in completed: remove_order_from_current_list(current_orders, order_id) event_log.append((current_time, delivered, order_id)) # 6. 记录数据用于分析 record_metrics(current_time, riders, current_orders) # 仿真结束输出统计结果和可视化 print_statistics(event_log) plot_rider_routes(riders, orders)可视化部分我们用matplotlib绘制了骑手路径的动画直观展示随着时间推移骑手们如何穿梭取送餐。静态图则可以展示最终所有骑手的路径和订单分布以及目标函数收敛曲线。5. 参数调优、结果分析与论文写作要点算法跑起来只是第一步调参和结果分析才是拉开差距的地方。5.1 关键参数敏感性分析我们的混合算法中有多个参数需要调整权重系数 (w1, w2, w3)这直接决定了优化导向。我们通过网格搜索并观察不同权重下解的帕累托前沿Pareto Front最终选择了一组在总时长、总距离和超时率上相对均衡的权重例如 0.5, 0.2, 0.3。LNS破坏比例破坏比例太大搜索随机性强收敛慢太小跳出局部最优能力弱。我们通过实验发现在20%-35%之间效果较好并采用了自适应策略如果连续多次迭代没有改进则增大破坏比例。改进WOA的参数种群大小、迭代次数。由于WOA只用于生成初始解我们不需要它完全收敛因此种群大小设为20-50迭代次数50-100次即可重在多样性。VNS的邻域搜索深度我们为每个邻域操作设置了最大尝试次数如100次避免在局部搜索中花费过多时间。踩坑实录最初我们没做参数敏感性分析随便设了一组值。结果算法要么疯狂追求最短路径导致严重超时要么为了不超时让骑手跑了很多冤枉路。后来我们固定其他参数每次只调一个观察目标函数各分量的变化并绘制了趋势图才找到了相对合理的参数组合。这个过程在论文中可以作为“模型稳健性分析”的一部分来写非常加分。5.2 结果对比与有效性验证为了证明我们模型和算法的有效性我们设计了对比实验基准策略最近邻策略骑手总是前往距离当前位置最近的未完成订单点。先到先得策略订单按产生时间分配给最近的空闲骑手骑手按订单顺序执行。消融实验仅LNS不使用WOA生成初始解也不在修复后使用VNS。LNS VNS使用随机初始解但修复后使用VNS。完整混合算法我们的最终方案。评价指标除了总成本Z我们还单独统计了订单平均送达时间、骑手总行驶里程、订单超时率、超时订单平均超时时长。实验结果用表格呈现最为清晰策略总成本 (Z)平均送达时间(分钟)总行驶里程(km)超时率算法运行时间(秒)最近邻1520.538.2145.325%1先到先得1380.735.8132.118%1仅LNS980.328.5108.78%45LNSVNS865.426.199.45%68混合算法(本文)795.824.795.23%82从表格可以明显看出我们的混合算法在各项配送效率指标上均显著优于基准策略。消融实验则证明了WOA提供优质初始解和VNS进行局部增强的有效性虽然增加了些许计算时间但带来的效益提升是值得的。5.3 论文写作的核心技巧数学建模竞赛论文是最终交付物。编程和求解只是过程。摘要用一段话概括问题、你的方法、模型、算法和核心结论。务必包含关键数据如“相比基准策略总成本降低了42%超时率降低了22个百分点”。问题重述与分析不要照抄题目要用自己的话分析问题的本质、难点和关键约束。画出概念图如骑手、订单、路网的关系图。模型假设清晰列出并说明为什么合理。这是体现你思考深度的部分。模型建立公式要完整、规范。对每个符号进行说明。目标函数和约束条件要分点阐述。算法设计这是亮点。用流程图可以手绘拍照展示算法框架。详细说明LNS、改进WOA、VNS是如何结合在一起的。伪代码不要太多挑核心的写1-2个。仿真与结果分析展示参数设置。用表格和图表折线图、柱状图、路径示意图多维度呈现结果。分析要深入比如“超时率从25%降到3%主要得益于后悔值插入算法优先处理了时间窗紧迫的订单”。模型评价与推广客观评价自己模型的优点如高效、灵活和缺点如对历史数据依赖、未考虑极端天气。提出改进方向如接入实时交通API引入机器学习预测备餐时间。说明模型可以推广到其他即时配送场景如快递、生鲜配送。附录与代码将核心代码如评估函数、LNS主循环整理后放入附录。代码要简洁有必要的注释。最后在提交前一定要反复检查论文的排版、图表编号、公式编号、参考文献引用。一篇排版精美、逻辑清晰、结果扎实的论文是获得好名次的基石。我们的程序可能不是最快的算法也不是最前沿的但整个解决过程体现出的系统思维、对细节的考量以及清晰的表述才是数维杯这类竞赛真正看重的。