数学建模实战：混合优化算法求解外卖配送路径规划问题

1. 项目背景与问题拆解：当数学建模遇上“送餐危机”

去年带学生参加数维杯，A题“外卖骑手的送餐危机”一出来，我们团队就乐了。这题太“接地气”了，简直就是把每天发生在你我身边的外卖配送问题，抽象成了一个经典的运筹优化模型。但乐完就发现，题目背后藏着不少“坑”。所谓的“送餐危机”，核心矛盾是什么？是骑手在有限时间内，面对动态涌入的订单、复杂的路网、不确定的交通状况和严格的平台规则时，如何规划路径才能最大化送达效率、最小化超时和成本。这听起来像是一个带时间窗的车辆路径问题（VRPTW），但实际建模时，你会发现它比教科书上的VRPTW复杂得多——订单不是一次性给全的，路况是实时变化的，骑手还可能同时接多个顺路单。

网上能找到的很多优秀论文或开源代码，比如针对“蚁群算法解决连续问题”、“全局搜索增强的改进鲸鱼算法”或者“AGV的A*算法”，都为我们提供了宝贵的思路工具箱。但直接套用往往水土不服。比如，你用标准的遗传算法去解，可能很快得到一个“理论上”的优化路径，但这个路径是否考虑了非机动车道的限制？是否考虑了写字楼等电梯的等待时间？是否考虑了午高峰餐馆出餐慢的随机延迟？这些细节，才是把论文从“纸上谈兵”变成“真枪实弹”的关键。

所以，这篇内容不是简单地复现我们当时的论文和程序，而是想以一个过来人的身份，拆解我们面对这道题时的完整思考过程、模型建立时的多次迭代、算法选型时的权衡对比，以及编程实现中那些教科书不会写的“骚操作”和“踩坑实录”。无论你是正在备战数维杯、国赛、美赛的同学，还是对路径优化、数学建模感兴趣的朋友，希望这些从实战中沉淀下来的经验，能给你带来一些不一样的启发。

2. 模型构建：从现实问题到数学语言的精确翻译

拿到题目，第一步不是急着找算法，而是把模糊的“送餐危机”翻译成清晰的数学问题。我们团队当时花了将近半天时间来定义边界、做出合理假设，并确定优化目标。这一步走稳了，后面的算法和编程才有意义。

2.1 核心要素定义与假设

我们首先明确了模型中的几个核心实体和它们的属性：

1. 骑手：定义为移动的配送单元。每个骑手有初始位置（通常为配送站或上一个送达点）、载货容量（能同时携带的订单数，本题中通常设为有限值，如3-5单）、移动速度（一个变量，受路况影响）。
2. 订单：每个订单包含商家位置、顾客位置、期望送达时间窗（通常是一个时间点，如“30分钟内送达”，我们将其处理为一个软时间窗，允许超时但需惩罚）、预计备餐时间、实际重量/体积（用于容量约束）。
3. 路网：我们将配送区域抽象为一个带权图。节点包括：所有商家、所有顾客、配送站、重要的道路交叉口。边的权重不是简单的欧氏距离，而是预估骑行时间。这个时间是动态的，与时间段（平峰/高峰）、天气等因素有关。

基于这些实体，我们做出了几个关键假设，以平衡模型的复杂性与可求解性：

• 假设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。使用平方项是为了让算法极度厌恶严重超时。

约束条件：

1. 流量平衡：每个骑手从配送站出发，最终返回配送站（或结束于最后一个顾客点）。
2. 订单服务唯一性：每个订单必须被且仅被一个骑手服务一次（包括取餐和送餐）。
3. 时间窗约束：骑手到达每个顾客点的时间t_arrive应尽量在期望时间t_due之前，否则计入惩罚。
4. 容量约束：骑手在任意时刻携带的订单数不能超过其最大容量。
5. 取送顺序约束：对于任何一个订单，骑手必须先访问商家节点i，才能访问对应的顾客节点j。即t_arrive_i < t_arrive_j。
6. 时间连续性约束：骑手到达下一个节点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需要一个不错的初始解，并且其搜索能力有时会陷入平台期。我们引入了热词中提到的两种算法进行增强：

1. 初始解生成：改进的鲸鱼优化算法（WOA）标准的WOA模拟鲸鱼气泡网捕食行为，在连续空间搜索能力强。但我们的问题解是离散的（路径序列）。我们对其进行了离散化改造：

   • 编码：采用“顾客-骑手”关联编码。一个鲸鱼个体（解）表示为一个列表，列表长度等于订单数，每个位置的值表示负责该订单的骑手编号。至于订单在骑手路径中的具体顺序，则通过一个简单的最近邻插入法根据这个分配关系来生成。
   • 位置更新离散化：WOA中鲸鱼的位置更新公式会产生连续值。我们通过一个随机键（Random Key）策略将其离散化。例如，将连续的位置值通过排序，映射到骑手编号的排列上。
   • 作用：改进的离散WOA被用来快速生成一批多样化的初始解（种群），然后从中选择最好的一个作为LNS的起点。这比完全随机生成初始解质量高得多。

2. 局部搜索：变邻域搜索（VNS）作为修复后的增强在LNS的修复阶段得到一个完整新解后，我们并不直接接受它，而是以这个新解为起点，进行一轮快速的变邻域搜索（VNS），在局部寻找更优解。

   • 邻域结构：我们设计了多种小规模邻域操作，如：
     • 2-opt：反转路径中的一段。
     • Relocate：将一个订单从一条路径的一个位置移到同一条或另一条路径的另一个位置。
     • Exchange：交换两条路径中的两个订单。
   • 搜索策略：依次尝试这些邻域结构，一旦某个结构找到了改进解，就移动到新解并从头开始；如果所有结构都尝试完仍无改进，则跳出。

这样，我们的算法就形成了一个“改进WOA生成初始解 → LNS主循环（破坏+修复）→ 内嵌VNS局部爬坡”的三层混合架构。LNS负责大范围的“探索”，VNS负责精细的“挖掘”，WOA则提供了高质量的起点。

3.3 动态事件的处理机制

题目隐含了动态性（新订单实时涌入）。我们的处理方法是周期性重优化。

1. 系统内部维护一个时钟和事件队列。
2. 每过固定的时间间隔（如5分钟），或当新订单积累到一定数量时，触发一次重优化。
3. 重优化时，输入包括：所有尚未完成的订单（包括正在配送途中的）、所有骑手的当前位置和状态（携带哪些订单、当前路径）。
4. 将骑手的当前位置视为新的“虚拟配送站”，将已携带但未送达的订单视为必须服务的点，然后调用上述混合算法，重新规划所有骑手从当前时刻往后的路径。
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, key=order_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, key=lambda 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_solution

4.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 结果对比与有效性验证

为了证明我们模型和算法的有效性，我们设计了对比实验：

1. 基准策略：
   • 最近邻策略：骑手总是前往距离当前位置最近的未完成订单点。
   • 先到先得策略：订单按产生时间分配给最近的空闲骑手，骑手按订单顺序执行。
2. 消融实验：
   • 仅LNS：不使用WOA生成初始解，也不在修复后使用VNS。
   • LNS + VNS：使用随机初始解，但修复后使用VNS。
   • 完整混合算法：我们的最终方案。
3. 评价指标：除了总成本Z，我们还单独统计了订单平均送达时间、骑手总行驶里程、订单超时率、超时订单平均超时时长。

实验结果用表格呈现最为清晰：

从表格可以明显看出，我们的混合算法在各项配送效率指标上均显著优于基准策略。消融实验则证明了WOA提供优质初始解和VNS进行局部增强的有效性，虽然增加了些许计算时间，但带来的效益提升是值得的。

5.3 论文写作的核心技巧

数学建模竞赛，论文是最终交付物。编程和求解只是过程。

• 摘要：用一段话概括问题、你的方法、模型、算法和核心结论。务必包含关键数据，如“相比基准策略，总成本降低了42%，超时率降低了22个百分点”。
• 问题重述与分析：不要照抄题目，要用自己的话分析问题的本质、难点和关键约束。画出概念图（如骑手、订单、路网的关系图）。
• 模型假设：清晰列出，并说明为什么合理。这是体现你思考深度的部分。
• 模型建立：公式要完整、规范。对每个符号进行说明。目标函数和约束条件要分点阐述。
• 算法设计：这是亮点。用流程图（可以手绘拍照）展示算法框架。详细说明LNS、改进WOA、VNS是如何结合在一起的。伪代码不要太多，挑核心的写1-2个。
• 仿真与结果分析：展示参数设置。用表格和图表（折线图、柱状图、路径示意图）多维度呈现结果。分析要深入，比如“超时率从25%降到3%，主要得益于后悔值插入算法优先处理了时间窗紧迫的订单”。
• 模型评价与推广：客观评价自己模型的优点（如高效、灵活）和缺点（如对历史数据依赖、未考虑极端天气）。提出改进方向（如接入实时交通API，引入机器学习预测备餐时间）。说明模型可以推广到其他即时配送场景（如快递、生鲜配送）。
• 附录与代码：将核心代码（如评估函数、LNS主循环）整理后放入附录。代码要简洁，有必要的注释。

最后，在提交前，一定要反复检查论文的排版、图表编号、公式编号、参考文献引用。一篇排版精美、逻辑清晰、结果扎实的论文，是获得好名次的基石。我们的程序可能不是最快的，算法也不是最前沿的，但整个解决过程体现出的系统思维、对细节的考量以及清晰的表述，才是数维杯这类竞赛真正看重的。