1. 问题引入当无人机飞入数学建模赛场五一数学建模联赛的B题每年都是兵家必争之地。今年题目把目光投向了物流配送这个既传统又充满科技感的领域并且引入了一个关键变量无人机。题目叫“具有无人机的物流配送问题”这短短几个字背后是运筹学、图论、优化算法和现实物流场景的复杂交织。我猜很多队伍拿到题的第一反应是兴奋紧接着可能就是一阵头疼——无人机怎么建模和传统车辆配送怎么结合目标函数到底该怎么设这绝不是一道简单的“车辆路径问题VRP”变种。传统的VRP我们考虑的是卡车从配送中心出发访问一系列客户点后返回目标是总路程最短或成本最低。但加入了无人机游戏规则就变了。无人机续航有限、载重小但它能“飞直线”不受复杂路网限制还能和卡车协同作业。这就引出了一个核心的“卡车-无人机协同配送”模型Truck-Drone Collaborative Delivery。想象一下一辆卡车作为移动的“母舰”和补给站搭载多架无人机。卡车行驶到某个区域后释放无人机去服务周边的客户点无人机完成任务后返回卡车可能是在另一个汇合点然后卡车带着无人机前往下一个区域。这种模式能极大地提升在拥堵城市或地形复杂地区的“最后一公里”配送效率。所以这道题的核心就是如何为这种“卡车无人机”的混合车队设计一套最优的配送方案。方案需要决定卡车怎么走无人机什么时候释放、去服务哪些客户、在哪里与卡车汇合最终我们要最小化什么是总完成时间Makespan还是总行驶成本或者是某种加权和题目没有明说但这正是建模时需要首先厘清的关键。从历年赛题和实际研究来看最小化总完成时间即从出发到所有客户都被服务完、所有设备返回仓库的时间是一个很常见且合理的目标它直接对应着配送服务的效率。2. 模型基石如何抽象现实世界面对这样一个问题第一步不是急着写代码而是要把杂乱的实际场景抽象成严谨的数学模型。这一步走对了后面的算法设计才有坚实的根基。2.1 关键假设与问题定义首先我们必须做出一些合理的假设来简化问题否则模型将无法处理。这些假设也是论文中“模型假设”部分的核心内容配送网络我们将所有地点抽象为一个完全图。节点集合包括一个配送中心Depot编号为0、N个客户点。任意两点之间的距离是已知的且满足三角不等式。对于卡车距离是实际道路距离对于无人机距离是两点间的直线欧氏距离通常小于或等于卡车距离。设备特性卡车容量无限或足够大速度较慢但续航长可以访问所有节点。无人机载重量小通常一次只能服务一个客户续航时间有限由最大飞行距离或最大飞行时间约束飞行速度通常快于卡车。无人机必须从卡车上发射也必须返回卡车上进行电池更换或充电才能进行下一次飞行。作业模式我们采用“并行作业”模式。即卡车在行驶过程中可以释放无人机去服务客户同时卡车继续前往下一个节点或汇合点。无人机服务完客户后飞往指定的汇合点与卡车重新汇合。一个客户只能被服务一次由卡车或无人机完成。目标最小化整个配送任务的总完成时间Makespan。这是指从时刻0所有设备从配送中心出发到最后一台设备无论是卡车还是无人机返回配送中心的时刻。基于以上我们可以将问题定义为一个带时间窗和同步约束的混合车辆路径问题Hybrid VRP with Synchronization Constraints。说人话就是我们需要规划一条卡车路径以及嵌入在这条路径上的若干次无人机飞行任务并且要保证无人机和卡车在汇合点的时间必须匹配同步最终让总时间最短。2.2 决策变量与数学模型框架接下来我们用数学语言来描述它。这里我给出一个常见的混合整数规划MIP模型框架思路。注意完全精确的MIP模型对于大规模问题可能难以直接求解但它是我们理解问题结构和设计启发式算法的蓝图。集合V: 所有节点的集合{0, 1, 2, ..., N}其中0是配送中心。C: 客户节点集合{1, 2, ..., N}。K: 无人机集合假设有m架无人机{1, 2, ..., m}。参数d_ij_truck: 卡车从节点i到节点j的行驶时间。d_ij_drone: 无人机从节点i到节点j的飞行时间通常d_ij_drone d_ij_truck。E: 无人机的最大续航时间或距离。service_time: 在每个客户点的服务时间假设为常数可设为0简化。决策变量核心x_ij: 二进制变量卡车是否直接从节点i行驶到节点j。y_ik: 二进制变量客户i是否由无人机k服务。t_i: 连续变量卡车到达节点i的时间。s_ik: 连续变量无人机k开始服务客户i的时间如果该客户由无人机k服务。r_ik: 连续变量无人机k在服务完客户i后返回卡车的汇合点时间。约束条件流量守恒卡车路径必须形成一个从配送中心出发并回到配送中心的回路。每个客户点最多被访问一次要么被卡车访问要么被某架无人机访问。Σ_j x_0j 1 卡车从中心出发 Σ_i x_i0 1 卡车返回中心 对于每个客户点 i: Σ_j x_ji Σ_k y_ik 1 每个客户被访问一次无人机任务可行性如果无人机k从卡车在节点a释放去服务客户i然后到节点b与卡车汇合那么必须满足无人机飞行时间约束d_ai_drone d_ib_drone E。时间同步约束卡车到达汇合点b的时间t_b必须大于等于无人机返回时间r_ik。同时无人机释放时间即卡车在节点a的离开时间必须早于无人机开始服务客户i的时间s_ik。这个关系需要引入额外的辅助变量来刻画无人机任务与卡车路径的关联是模型中最复杂的部分。时间连续性卡车到达节点j的时间等于到达前一个节点i的时间加上行驶时间和服务时间。t_j t_i d_ij_truck service_time - M*(1 - x_ij)其中M是一个很大的正数。目标函数 最小化max( t_0_return, max_over_all_drones( return_time ) )即最小化所有设备返回配送中心的最晚时间。这个MIP模型清晰地刻画了问题但直接求解即使用CPLEX、Gurobi等求解器只适用于客户点很少比如N20的情况。对于竞赛规模N可能50我们必须转向更高效的启发式或元启发式算法。3. 算法核心从精确求解到智能启发既然精确算法走不通我们就要设计“足够好”的智能算法。这类问题的算法通常分层先构造一个可行的初始解再对这个解进行迭代优化。3.1 初始解构造分而治之的思维一个直观的构造方法是“先聚类后路由”。步骤一客户聚类根据客户的地理位置将他们分成若干簇。每个簇对应一个由卡车访问的“锚点”区域。聚类的依据可以是距离中心远近将距离配送中心较远的客户优先考虑用无人机服务因为无人机飞直线优势更大。空间密度将位置密集的客户聚成一类适合卡车一次性访问将位置分散或偏离主干道的客户单独列出适合无人机从主干道上的卡车点出发进行服务。无人机可达性以配送中心或预设的卡车路径关键点为圆心以无人机最大航程为半径画圆落在圆内且彼此孤立的客户点天然适合作为同一个无人机任务的服务对象。我们可以使用K-Means、层次聚类等简单方法但需要结合对无人机航程的考量。一个更实用的方法是先为卡车生成一条不考虑无人机的、粗略的最近邻路径TSP路径然后沿着这条路径判断哪些客户点适合“甩”给无人机。步骤二生成卡车骨架路径将聚类后的簇中心点以及必须由卡车访问的客户点如需求量大的点作为卡车必须访问的节点。在这些节点上运行经典的TSP求解器如LKH算法、OR-Tools或简单的最近邻插入法生成一条卡车的初步路径。这条路径就是无人机任务的“发射台”和“回收站”序列。步骤三分配无人机任务对于每个不适合卡车访问或从卡车路径上分离出来能节省时间的客户点我们尝试将其分配给无人机。具体操作为遍历卡车路径上连续的两个节点i, j卡车将从i行驶到j。对于一个待分配的客户点c检查是否满足飞行时间(i-c) 飞行时间(c-j) 无人机续航E。如果满足则评估将c插入为无人机任务对总时间的影响。影响包括无人机任务本身的时间t_ic t_cj以及它是否会导致卡车在汇合点j等待无人机产生空闲时间。选择能使卡车等待时间最小、或总完成时间预估减少最多的客户点进行分配。一个无人机架次可以服务一个客户题目常见设定也可以服务多个如果续航允许这需要在建模时明确。通过以上三步我们就能得到一个“卡车路径 附着在上面的无人机任务”的初始可行方案。3.2 优化迭代局部搜索与元启发式初始解通常质量不高需要优化。这里就是各种智能算法大显身手的地方。3.2.1 局部搜索算子设计一些针对本问题结构的邻域操作在当前解附近寻找更好的解客户点重分配将一个由卡车服务的客户点尝试改为由某个可行的无人机任务服务或者反过来将一个无人机服务的客户点改为由卡车服务。无人机任务迁移将一个无人机任务从一个卡车段i-j迁移到另一个卡车段k-l上。卡车路径2-opt对卡车的访问节点序列进行经典的2-opt操作反转一段路径同时需要检查附着在受影响节点上的无人机任务是否仍然可行如果不可行则需要调整或移除。无人机任务交换交换两个无人机任务所服务的客户点。3.2.2 元启发式算法框架将上述局部搜索算子嵌入到一个更高级的算法框架中以避免陷入局部最优模拟退火以一定概率接受比当前解差的解初期概率高后期逐渐降低。非常适合本题。算法流程可以是从初始解开始随机选择一个上述的邻域操作产生新解计算新解的总时间。如果新解更优则接受如果更差则以概率exp(-ΔT / current_temperature)接受。然后缓慢降低“温度”。变邻域搜索定义一组强度递增的邻域操作例如先尝试客户点重分配再尝试路径2-opt最后尝试大规模扰动。在当前邻域找不到更好解时自动切换到下一个更大的邻域进行搜索。遗传算法如何编码染色体是个挑战。一种编码方式是染色体分为两部分第一部分是卡车路径的节点序列排列第二部分是每个客户点的服务模式0表示卡车1表示无人机如果是无人机还需关联其起降点信息。交叉和变异算子需要精心设计以保证解的有效性。在实际竞赛中模拟退火因其实现相对简单、调参直观、效果稳定往往是首选。你需要调试的关键参数有初始温度、降温系数、每个温度下的迭代次数、终止温度。实操心得不要试图在算法初期就追求完美的模型和复杂的算法。一个“构造模拟退火”的组合拳往往能快速得到一个不错的可行解这比纠结于一个无法实现的完美模型要实惠得多。先把流程跑通得到第一个可行解和目标函数值这是稳定军心的关键一步。4. 实现细节与代码踩坑指南理论很美代码很残酷。下面我结合常见的实现平台如Python分享一些关键的实现细节和容易踩的坑。4.1 数据结构设计良好的数据结构是高效算法的基础。建议定义几个核心类class Node: def __init__(self, id, x, y, demand0): self.id id # 节点ID0为配送中心 self.x x self.y y self.demand demand # 如果需要考虑载重 class Truck: def __init__(self): self.route [0] # 路径节点ID列表从0开始 self.time 0.0 # 当前时间 # 可以记录到达每个节点的时间 class Drone: def __init__(self, id, endurance, speed): self.id id self.endurance endurance # 最大续航时间 self.speed speed self.missions [] # 任务列表每个任务格式 (launch_node, customer_node, rendezvous_node) class Solution: def __init__(self): self.truck Truck() self.drones [] # Drone对象列表 self.total_time 0.0 # 还需要一个映射customer_id - (served_by, serve_time, ...)4.2 核心函数时间计算与可行性校验这是算法中最频繁调用的部分必须高效且正确。import math def euclidean_distance(node1, node2): 计算两点间欧氏距离用于无人机飞行时间估算。 return math.sqrt((node1.x - node2.x)**2 (node1.y - node2.y)**2) def truck_travel_time(node1, node2, speed1.0): 计算卡车行驶时间。这里简化用欧氏距离乘以一个系数1模拟道路距离。 road_factor 1.3 # 假设道路距离是直线距离的1.3倍 return euclidean_distance(node1, node2) * road_factor / speed def is_drone_mission_feasible(launch_node, customer_node, rendezvous_node, drone): 判断一个无人机任务是否可行。 可行性1. 飞行总距离/时间不超过续航2. 时间同步上可能初步检查。 flight_time (euclidean_distance(launch_node, customer_node) euclidean_distance(customer_node, rendezvous_node)) / drone.speed if flight_time drone.endurance: return False # 更精细的检查卡车从launch到rendezvous的时间必须大于无人机飞行时间服务时间 # 这个检查在完整方案评估中做更合适 return True def evaluate_solution(solution, all_nodes): 评估一个完整方案的总完成时间。 这是最核心的函数需要模拟整个时间线。 # 初始化时间线 truck_time_at_node {0: 0.0} # 卡车在节点的时间 # ... 模拟卡车沿着route行驶计算到达每个节点的时间 # ... 模拟每个无人机任务的开始和结束时间 # ... 关键处理卡车在汇合点的等待。如果卡车先到就等无人机如果无人机先到就等卡车。 # ... 最终总完成时间是卡车返回0点的时间和所有无人机返回0点的时间的最大值。 # 这个函数实现较为复杂需要仔细处理时间同步逻辑。 return total_makespan4.3 模拟退火主循环框架import random import copy def simulated_annealing(initial_solution, all_nodes, max_iter10000): current_sol copy.deepcopy(initial_solution) best_sol copy.deepcopy(initial_solution) current_cost evaluate_solution(current_sol, all_nodes) best_cost current_cost T 1000.0 # 初始温度 T_min 1e-3 # 终止温度 alpha 0.995 # 降温系数 while T T_min: for i in range(100): # 每个温度迭代次数 # 1. 产生邻域新解 new_sol generate_neighbor(current_sol, all_nodes) # 需要实现 # 2. 评估新解 new_cost evaluate_solution(new_sol, all_nodes) delta new_cost - current_cost # 3. Metropolis准则 if delta 0 or random.random() math.exp(-delta / T): current_sol new_sol current_cost new_cost # 4. 更新最优解 if current_cost best_cost: best_sol copy.deepcopy(current_sol) best_cost current_cost # 降温 T * alpha return best_sol, best_cost4.4 必踩的坑与调试技巧时间同步逻辑错误这是最容易出错的地方。你的evaluate_solution函数必须精确模拟时间线。建议为卡车和每个无人机维护一个“时间线”队列按事件到达节点、离开节点、开始服务、结束服务顺序推进。特别注意汇合点无人机到达汇合点时如果卡车还没到无人机需要等待反之亦然。总时间是所有设备最后一个事件的时间。邻域操作产生无效解generate_neighbor函数必须生成“可行”的邻域解。例如移动一个无人机任务后必须立即检查续航约束。如果不可行要么拒绝这次移动要么设计一个修复函数例如为这个无人机任务寻找最近的可行起降点。一个简单的策略是先尝试操作操作后立即调用可行性检查如果无效则返回原解或进行小幅修复。计算效率低下evaluate_solution会被调用成千上万次必须高效。避免在每次评估时都重新计算所有距离。可以预计算所有节点间的卡车行驶时间矩阵和无人机飞行时间矩阵。在评估时只做查表和加法。初始解质量太差如果初始解离最优解太远模拟退火可能要在很差的区域徘徊很久。花点时间设计一个更好的构造算法。例如先用最近邻法生成纯卡车路径然后贪心地将路径上那些“绕路”严重的客户点尝试用无人机服务只要能节省时间就分配。参数调优模拟退火的参数初始温度、降温系数对结果影响很大。没有银弹需要针对你的问题规模进行测试。一个经验是初始温度设置应使得在初期比当前解差10%左右的解被接受的概率大约在0.5左右。降温系数通常在0.9到0.999之间越接近1搜索越细致但耗时越长。踩坑实录我在第一次实现时忽略了无人机在汇合点等待卡车的时间。我的评估函数只计算了飞行时间导致算法总是倾向于把无人机任务安排得特别紧凑结果在模拟时间线时发现无人机早早飞到了汇合点卡车却还在路上实际的完成时间被卡车的行程拖得很长算法却自以为找到了好解。修正后目标函数值立刻变得合理优化方向也正确了。所以时间线的精确模拟是模型的灵魂偷不得懒。5. 论文写作与结果呈现要点数学建模竞赛三分靠模型七分靠写作。一个清晰的论文结构能让你的工作脱颖而出。5.1 论文核心结构问题重述与分析不要照抄题目要用自己的话提炼问题的核心、难点同步约束、续航约束、目标优化和创新点协同配送。模型假设与符号说明将我们在第二部分做的假设清晰列出。符号说明用三线表清晰美观。模型建立这是重中之重。先给出问题的一般性数学模型MIP模型展示你对问题本质的理解。然后明确指出由于问题规模大、属于NP-Hard精确模型无法直接求解因此提出“基于聚类的两阶段启发式算法”或“模拟退火算法”进行求解。这样逻辑就顺畅了。算法设计详细描述你的算法流程。最好配上流程图。分小节讲解5.1 初始解生成策略聚类路径构造5.2 局部搜索算子设计具体哪几种操作5.3 模拟退火/变邻域搜索框架5.4 算法复杂度分析简要说明算例分析与结果数据如果题目没给数据需要自己生成。说明生成规则如客户点随机分布在某个区域配送中心在中心等。可以设计不同规模N2050100的算例。对比基准为了体现你模型算法的优越性必须设置对比基准。常见的基准有纯卡车配送即不考虑无人机用经典TSP或VRP求解。简单贪婪算法例如始终让无人机服务最近的可达客户。评价指标主要就是总完成时间Makespan。还可以对比卡车总行程、无人机利用率、计算时间等。结果表格与可视化用表格呈现不同算法在不同规模算例下的目标函数值和计算时间。用路径图进行可视化这是最大的亮点。用不同颜色和线型绘制卡车的路径、无人机的飞行轨迹。在图中清晰标释放点、客户点、汇合点。一张好的路径图胜过千言万语。灵敏度分析讨论关键参数变化对结果的影响。例如无人机续航时间E增加或减少10%、20%总完成时间如何变化无人机与卡车的速度比变化会如何影响任务分配策略客户点分布密度变化集中 vs 分散对算法效果的影响。 这部分能体现你对模型理解的深度。模型评价与推广客观评价自己模型的优点效率高、可扩展性好和缺点假设较理想、未考虑动态交通。提出可能的改进方向如考虑充电时间、多车型、动态需求等。5.2 可视化让你的论文“会说话”在结果部分务必进行可视化。整体路径规划图使用matplotlib绘制。import matplotlib.pyplot as plt def plot_solution(solution, nodes): plt.figure(figsize(10, 8)) # 1. 画所有节点 xs [n.x for n in nodes] ys [n.y for n in nodes] plt.scatter(xs, ys, cblack, markero, labelCustomer, zorder5) plt.scatter(nodes[0].x, nodes[0].y, cred, markers, s200, labelDepot, zorder10) # 2. 画卡车路径红色实线 truck_x [nodes[i].x for i in solution.truck.route] truck_y [nodes[i].y for i in solution.truck.route] plt.plot(truck_x, truck_y, r-, linewidth2, labelTruck Route) # 3. 画无人机任务蓝色虚线 for drone in solution.drones: for mission in drone.missions: launch, cust, rend mission # 画 launch - customer - rendezvous 的折线 pts_x [nodes[launch].x, nodes[cust].x, nodes[rend].x] pts_y [nodes[launch].y, nodes[cust].y, nodes[rend].y] plt.plot(pts_x, pts_y, b--, linewidth1.5, alpha0.7) # 在客户点上做个标记 plt.scatter(nodes[cust].x, nodes[cust].y, cblue, edgecolorsblue, s100, zorder6) plt.legend() plt.grid(True, linestyle--, alpha0.5) plt.title(Truck-Drone Collaborative Delivery Solution) plt.xlabel(X Coordinate) plt.ylabel(Y Coordinate) plt.axis(equal) plt.show()性能对比柱状图用柱状图对比不同算法在不同算例下的总完成时间。灵敏度分析折线图展示续航E变化时目标函数值的变化趋势。一张精心绘制的路径图能直观展示你算法中“卡车-无人机”的协同模式是论文最有力的证据之一。6. 进阶思考与扩展方向如果你还有余力或者题目有进一步的要求可以考虑以下扩展方向这能让你的论文更有深度。6.1 多目标优化现实中企业可能不仅关心时间最短还关心成本最低油耗、人力、无人机折旧。这就成了一个多目标优化问题。你可以将目标函数设为最小化总完成时间和总行驶成本距离的加权和。通过调整权重可以得到一系列“帕累托最优解”并绘制帕累托前沿图分析时间与成本之间的权衡关系。6.2 动态与随机性更贴近现实的场景是动态和随机的客户订单可能随时到来动态无人机的飞行时间可能受风速影响随机卡车的行驶时间可能受交通状况影响随机。这时问题就变成了随机规划或动态规划。你可以引入场景树或采用滚动时域优化策略每当新订单到达或状态更新时重新快速运行一次你的启发式算法对剩余任务进行重新规划。6.3 异质车队与充电约束你的模型可以进一步复杂化车队中有多种型号的卡车容量不同、速度不同和无人机载重不同、续航不同。无人机可能需要在中途的充电站充电而不是返回卡车。这就需要引入更复杂的资源分配和时间约束模型。对于竞赛而言能把基础的单目标、静态、同质车队的模型做扎实算法实现稳定结果分析透彻就已经能拿到很高的分数了。这些扩展方向可以作为你论文“模型评价与推广”部分的内容展示你对问题更深入的理解和思考。最后想说的是数学建模比赛是一个系统工程从审题、建模、编程到写作环环相扣。这道B题的关键在于理解“协同”二字的含义并把它转化为数学上的“同步约束”。算法上不必追求最新最炫稳定、健壮、能出结果的算法就是好算法。写作上务必清晰、直观、有逻辑。祝你在比赛中能高效协作把这一套方法用起来顺利拿下这道充满挑战的无人机物流配送题。 卡车-无人机协同配送建模与优化：从VRP到混合车队路径规划
1. 问题引入当无人机飞入数学建模赛场五一数学建模联赛的B题每年都是兵家必争之地。今年题目把目光投向了物流配送这个既传统又充满科技感的领域并且引入了一个关键变量无人机。题目叫“具有无人机的物流配送问题”这短短几个字背后是运筹学、图论、优化算法和现实物流场景的复杂交织。我猜很多队伍拿到题的第一反应是兴奋紧接着可能就是一阵头疼——无人机怎么建模和传统车辆配送怎么结合目标函数到底该怎么设这绝不是一道简单的“车辆路径问题VRP”变种。传统的VRP我们考虑的是卡车从配送中心出发访问一系列客户点后返回目标是总路程最短或成本最低。但加入了无人机游戏规则就变了。无人机续航有限、载重小但它能“飞直线”不受复杂路网限制还能和卡车协同作业。这就引出了一个核心的“卡车-无人机协同配送”模型Truck-Drone Collaborative Delivery。想象一下一辆卡车作为移动的“母舰”和补给站搭载多架无人机。卡车行驶到某个区域后释放无人机去服务周边的客户点无人机完成任务后返回卡车可能是在另一个汇合点然后卡车带着无人机前往下一个区域。这种模式能极大地提升在拥堵城市或地形复杂地区的“最后一公里”配送效率。所以这道题的核心就是如何为这种“卡车无人机”的混合车队设计一套最优的配送方案。方案需要决定卡车怎么走无人机什么时候释放、去服务哪些客户、在哪里与卡车汇合最终我们要最小化什么是总完成时间Makespan还是总行驶成本或者是某种加权和题目没有明说但这正是建模时需要首先厘清的关键。从历年赛题和实际研究来看最小化总完成时间即从出发到所有客户都被服务完、所有设备返回仓库的时间是一个很常见且合理的目标它直接对应着配送服务的效率。2. 模型基石如何抽象现实世界面对这样一个问题第一步不是急着写代码而是要把杂乱的实际场景抽象成严谨的数学模型。这一步走对了后面的算法设计才有坚实的根基。2.1 关键假设与问题定义首先我们必须做出一些合理的假设来简化问题否则模型将无法处理。这些假设也是论文中“模型假设”部分的核心内容配送网络我们将所有地点抽象为一个完全图。节点集合包括一个配送中心Depot编号为0、N个客户点。任意两点之间的距离是已知的且满足三角不等式。对于卡车距离是实际道路距离对于无人机距离是两点间的直线欧氏距离通常小于或等于卡车距离。设备特性卡车容量无限或足够大速度较慢但续航长可以访问所有节点。无人机载重量小通常一次只能服务一个客户续航时间有限由最大飞行距离或最大飞行时间约束飞行速度通常快于卡车。无人机必须从卡车上发射也必须返回卡车上进行电池更换或充电才能进行下一次飞行。作业模式我们采用“并行作业”模式。即卡车在行驶过程中可以释放无人机去服务客户同时卡车继续前往下一个节点或汇合点。无人机服务完客户后飞往指定的汇合点与卡车重新汇合。一个客户只能被服务一次由卡车或无人机完成。目标最小化整个配送任务的总完成时间Makespan。这是指从时刻0所有设备从配送中心出发到最后一台设备无论是卡车还是无人机返回配送中心的时刻。基于以上我们可以将问题定义为一个带时间窗和同步约束的混合车辆路径问题Hybrid VRP with Synchronization Constraints。说人话就是我们需要规划一条卡车路径以及嵌入在这条路径上的若干次无人机飞行任务并且要保证无人机和卡车在汇合点的时间必须匹配同步最终让总时间最短。2.2 决策变量与数学模型框架接下来我们用数学语言来描述它。这里我给出一个常见的混合整数规划MIP模型框架思路。注意完全精确的MIP模型对于大规模问题可能难以直接求解但它是我们理解问题结构和设计启发式算法的蓝图。集合V: 所有节点的集合{0, 1, 2, ..., N}其中0是配送中心。C: 客户节点集合{1, 2, ..., N}。K: 无人机集合假设有m架无人机{1, 2, ..., m}。参数d_ij_truck: 卡车从节点i到节点j的行驶时间。d_ij_drone: 无人机从节点i到节点j的飞行时间通常d_ij_drone d_ij_truck。E: 无人机的最大续航时间或距离。service_time: 在每个客户点的服务时间假设为常数可设为0简化。决策变量核心x_ij: 二进制变量卡车是否直接从节点i行驶到节点j。y_ik: 二进制变量客户i是否由无人机k服务。t_i: 连续变量卡车到达节点i的时间。s_ik: 连续变量无人机k开始服务客户i的时间如果该客户由无人机k服务。r_ik: 连续变量无人机k在服务完客户i后返回卡车的汇合点时间。约束条件流量守恒卡车路径必须形成一个从配送中心出发并回到配送中心的回路。每个客户点最多被访问一次要么被卡车访问要么被某架无人机访问。Σ_j x_0j 1 卡车从中心出发 Σ_i x_i0 1 卡车返回中心 对于每个客户点 i: Σ_j x_ji Σ_k y_ik 1 每个客户被访问一次无人机任务可行性如果无人机k从卡车在节点a释放去服务客户i然后到节点b与卡车汇合那么必须满足无人机飞行时间约束d_ai_drone d_ib_drone E。时间同步约束卡车到达汇合点b的时间t_b必须大于等于无人机返回时间r_ik。同时无人机释放时间即卡车在节点a的离开时间必须早于无人机开始服务客户i的时间s_ik。这个关系需要引入额外的辅助变量来刻画无人机任务与卡车路径的关联是模型中最复杂的部分。时间连续性卡车到达节点j的时间等于到达前一个节点i的时间加上行驶时间和服务时间。t_j t_i d_ij_truck service_time - M*(1 - x_ij)其中M是一个很大的正数。目标函数 最小化max( t_0_return, max_over_all_drones( return_time ) )即最小化所有设备返回配送中心的最晚时间。这个MIP模型清晰地刻画了问题但直接求解即使用CPLEX、Gurobi等求解器只适用于客户点很少比如N20的情况。对于竞赛规模N可能50我们必须转向更高效的启发式或元启发式算法。3. 算法核心从精确求解到智能启发既然精确算法走不通我们就要设计“足够好”的智能算法。这类问题的算法通常分层先构造一个可行的初始解再对这个解进行迭代优化。3.1 初始解构造分而治之的思维一个直观的构造方法是“先聚类后路由”。步骤一客户聚类根据客户的地理位置将他们分成若干簇。每个簇对应一个由卡车访问的“锚点”区域。聚类的依据可以是距离中心远近将距离配送中心较远的客户优先考虑用无人机服务因为无人机飞直线优势更大。空间密度将位置密集的客户聚成一类适合卡车一次性访问将位置分散或偏离主干道的客户单独列出适合无人机从主干道上的卡车点出发进行服务。无人机可达性以配送中心或预设的卡车路径关键点为圆心以无人机最大航程为半径画圆落在圆内且彼此孤立的客户点天然适合作为同一个无人机任务的服务对象。我们可以使用K-Means、层次聚类等简单方法但需要结合对无人机航程的考量。一个更实用的方法是先为卡车生成一条不考虑无人机的、粗略的最近邻路径TSP路径然后沿着这条路径判断哪些客户点适合“甩”给无人机。步骤二生成卡车骨架路径将聚类后的簇中心点以及必须由卡车访问的客户点如需求量大的点作为卡车必须访问的节点。在这些节点上运行经典的TSP求解器如LKH算法、OR-Tools或简单的最近邻插入法生成一条卡车的初步路径。这条路径就是无人机任务的“发射台”和“回收站”序列。步骤三分配无人机任务对于每个不适合卡车访问或从卡车路径上分离出来能节省时间的客户点我们尝试将其分配给无人机。具体操作为遍历卡车路径上连续的两个节点i, j卡车将从i行驶到j。对于一个待分配的客户点c检查是否满足飞行时间(i-c) 飞行时间(c-j) 无人机续航E。如果满足则评估将c插入为无人机任务对总时间的影响。影响包括无人机任务本身的时间t_ic t_cj以及它是否会导致卡车在汇合点j等待无人机产生空闲时间。选择能使卡车等待时间最小、或总完成时间预估减少最多的客户点进行分配。一个无人机架次可以服务一个客户题目常见设定也可以服务多个如果续航允许这需要在建模时明确。通过以上三步我们就能得到一个“卡车路径 附着在上面的无人机任务”的初始可行方案。3.2 优化迭代局部搜索与元启发式初始解通常质量不高需要优化。这里就是各种智能算法大显身手的地方。3.2.1 局部搜索算子设计一些针对本问题结构的邻域操作在当前解附近寻找更好的解客户点重分配将一个由卡车服务的客户点尝试改为由某个可行的无人机任务服务或者反过来将一个无人机服务的客户点改为由卡车服务。无人机任务迁移将一个无人机任务从一个卡车段i-j迁移到另一个卡车段k-l上。卡车路径2-opt对卡车的访问节点序列进行经典的2-opt操作反转一段路径同时需要检查附着在受影响节点上的无人机任务是否仍然可行如果不可行则需要调整或移除。无人机任务交换交换两个无人机任务所服务的客户点。3.2.2 元启发式算法框架将上述局部搜索算子嵌入到一个更高级的算法框架中以避免陷入局部最优模拟退火以一定概率接受比当前解差的解初期概率高后期逐渐降低。非常适合本题。算法流程可以是从初始解开始随机选择一个上述的邻域操作产生新解计算新解的总时间。如果新解更优则接受如果更差则以概率exp(-ΔT / current_temperature)接受。然后缓慢降低“温度”。变邻域搜索定义一组强度递增的邻域操作例如先尝试客户点重分配再尝试路径2-opt最后尝试大规模扰动。在当前邻域找不到更好解时自动切换到下一个更大的邻域进行搜索。遗传算法如何编码染色体是个挑战。一种编码方式是染色体分为两部分第一部分是卡车路径的节点序列排列第二部分是每个客户点的服务模式0表示卡车1表示无人机如果是无人机还需关联其起降点信息。交叉和变异算子需要精心设计以保证解的有效性。在实际竞赛中模拟退火因其实现相对简单、调参直观、效果稳定往往是首选。你需要调试的关键参数有初始温度、降温系数、每个温度下的迭代次数、终止温度。实操心得不要试图在算法初期就追求完美的模型和复杂的算法。一个“构造模拟退火”的组合拳往往能快速得到一个不错的可行解这比纠结于一个无法实现的完美模型要实惠得多。先把流程跑通得到第一个可行解和目标函数值这是稳定军心的关键一步。4. 实现细节与代码踩坑指南理论很美代码很残酷。下面我结合常见的实现平台如Python分享一些关键的实现细节和容易踩的坑。4.1 数据结构设计良好的数据结构是高效算法的基础。建议定义几个核心类class Node: def __init__(self, id, x, y, demand0): self.id id # 节点ID0为配送中心 self.x x self.y y self.demand demand # 如果需要考虑载重 class Truck: def __init__(self): self.route [0] # 路径节点ID列表从0开始 self.time 0.0 # 当前时间 # 可以记录到达每个节点的时间 class Drone: def __init__(self, id, endurance, speed): self.id id self.endurance endurance # 最大续航时间 self.speed speed self.missions [] # 任务列表每个任务格式 (launch_node, customer_node, rendezvous_node) class Solution: def __init__(self): self.truck Truck() self.drones [] # Drone对象列表 self.total_time 0.0 # 还需要一个映射customer_id - (served_by, serve_time, ...)4.2 核心函数时间计算与可行性校验这是算法中最频繁调用的部分必须高效且正确。import math def euclidean_distance(node1, node2): 计算两点间欧氏距离用于无人机飞行时间估算。 return math.sqrt((node1.x - node2.x)**2 (node1.y - node2.y)**2) def truck_travel_time(node1, node2, speed1.0): 计算卡车行驶时间。这里简化用欧氏距离乘以一个系数1模拟道路距离。 road_factor 1.3 # 假设道路距离是直线距离的1.3倍 return euclidean_distance(node1, node2) * road_factor / speed def is_drone_mission_feasible(launch_node, customer_node, rendezvous_node, drone): 判断一个无人机任务是否可行。 可行性1. 飞行总距离/时间不超过续航2. 时间同步上可能初步检查。 flight_time (euclidean_distance(launch_node, customer_node) euclidean_distance(customer_node, rendezvous_node)) / drone.speed if flight_time drone.endurance: return False # 更精细的检查卡车从launch到rendezvous的时间必须大于无人机飞行时间服务时间 # 这个检查在完整方案评估中做更合适 return True def evaluate_solution(solution, all_nodes): 评估一个完整方案的总完成时间。 这是最核心的函数需要模拟整个时间线。 # 初始化时间线 truck_time_at_node {0: 0.0} # 卡车在节点的时间 # ... 模拟卡车沿着route行驶计算到达每个节点的时间 # ... 模拟每个无人机任务的开始和结束时间 # ... 关键处理卡车在汇合点的等待。如果卡车先到就等无人机如果无人机先到就等卡车。 # ... 最终总完成时间是卡车返回0点的时间和所有无人机返回0点的时间的最大值。 # 这个函数实现较为复杂需要仔细处理时间同步逻辑。 return total_makespan4.3 模拟退火主循环框架import random import copy def simulated_annealing(initial_solution, all_nodes, max_iter10000): current_sol copy.deepcopy(initial_solution) best_sol copy.deepcopy(initial_solution) current_cost evaluate_solution(current_sol, all_nodes) best_cost current_cost T 1000.0 # 初始温度 T_min 1e-3 # 终止温度 alpha 0.995 # 降温系数 while T T_min: for i in range(100): # 每个温度迭代次数 # 1. 产生邻域新解 new_sol generate_neighbor(current_sol, all_nodes) # 需要实现 # 2. 评估新解 new_cost evaluate_solution(new_sol, all_nodes) delta new_cost - current_cost # 3. Metropolis准则 if delta 0 or random.random() math.exp(-delta / T): current_sol new_sol current_cost new_cost # 4. 更新最优解 if current_cost best_cost: best_sol copy.deepcopy(current_sol) best_cost current_cost # 降温 T * alpha return best_sol, best_cost4.4 必踩的坑与调试技巧时间同步逻辑错误这是最容易出错的地方。你的evaluate_solution函数必须精确模拟时间线。建议为卡车和每个无人机维护一个“时间线”队列按事件到达节点、离开节点、开始服务、结束服务顺序推进。特别注意汇合点无人机到达汇合点时如果卡车还没到无人机需要等待反之亦然。总时间是所有设备最后一个事件的时间。邻域操作产生无效解generate_neighbor函数必须生成“可行”的邻域解。例如移动一个无人机任务后必须立即检查续航约束。如果不可行要么拒绝这次移动要么设计一个修复函数例如为这个无人机任务寻找最近的可行起降点。一个简单的策略是先尝试操作操作后立即调用可行性检查如果无效则返回原解或进行小幅修复。计算效率低下evaluate_solution会被调用成千上万次必须高效。避免在每次评估时都重新计算所有距离。可以预计算所有节点间的卡车行驶时间矩阵和无人机飞行时间矩阵。在评估时只做查表和加法。初始解质量太差如果初始解离最优解太远模拟退火可能要在很差的区域徘徊很久。花点时间设计一个更好的构造算法。例如先用最近邻法生成纯卡车路径然后贪心地将路径上那些“绕路”严重的客户点尝试用无人机服务只要能节省时间就分配。参数调优模拟退火的参数初始温度、降温系数对结果影响很大。没有银弹需要针对你的问题规模进行测试。一个经验是初始温度设置应使得在初期比当前解差10%左右的解被接受的概率大约在0.5左右。降温系数通常在0.9到0.999之间越接近1搜索越细致但耗时越长。踩坑实录我在第一次实现时忽略了无人机在汇合点等待卡车的时间。我的评估函数只计算了飞行时间导致算法总是倾向于把无人机任务安排得特别紧凑结果在模拟时间线时发现无人机早早飞到了汇合点卡车却还在路上实际的完成时间被卡车的行程拖得很长算法却自以为找到了好解。修正后目标函数值立刻变得合理优化方向也正确了。所以时间线的精确模拟是模型的灵魂偷不得懒。5. 论文写作与结果呈现要点数学建模竞赛三分靠模型七分靠写作。一个清晰的论文结构能让你的工作脱颖而出。5.1 论文核心结构问题重述与分析不要照抄题目要用自己的话提炼问题的核心、难点同步约束、续航约束、目标优化和创新点协同配送。模型假设与符号说明将我们在第二部分做的假设清晰列出。符号说明用三线表清晰美观。模型建立这是重中之重。先给出问题的一般性数学模型MIP模型展示你对问题本质的理解。然后明确指出由于问题规模大、属于NP-Hard精确模型无法直接求解因此提出“基于聚类的两阶段启发式算法”或“模拟退火算法”进行求解。这样逻辑就顺畅了。算法设计详细描述你的算法流程。最好配上流程图。分小节讲解5.1 初始解生成策略聚类路径构造5.2 局部搜索算子设计具体哪几种操作5.3 模拟退火/变邻域搜索框架5.4 算法复杂度分析简要说明算例分析与结果数据如果题目没给数据需要自己生成。说明生成规则如客户点随机分布在某个区域配送中心在中心等。可以设计不同规模N2050100的算例。对比基准为了体现你模型算法的优越性必须设置对比基准。常见的基准有纯卡车配送即不考虑无人机用经典TSP或VRP求解。简单贪婪算法例如始终让无人机服务最近的可达客户。评价指标主要就是总完成时间Makespan。还可以对比卡车总行程、无人机利用率、计算时间等。结果表格与可视化用表格呈现不同算法在不同规模算例下的目标函数值和计算时间。用路径图进行可视化这是最大的亮点。用不同颜色和线型绘制卡车的路径、无人机的飞行轨迹。在图中清晰标释放点、客户点、汇合点。一张好的路径图胜过千言万语。灵敏度分析讨论关键参数变化对结果的影响。例如无人机续航时间E增加或减少10%、20%总完成时间如何变化无人机与卡车的速度比变化会如何影响任务分配策略客户点分布密度变化集中 vs 分散对算法效果的影响。 这部分能体现你对模型理解的深度。模型评价与推广客观评价自己模型的优点效率高、可扩展性好和缺点假设较理想、未考虑动态交通。提出可能的改进方向如考虑充电时间、多车型、动态需求等。5.2 可视化让你的论文“会说话”在结果部分务必进行可视化。整体路径规划图使用matplotlib绘制。import matplotlib.pyplot as plt def plot_solution(solution, nodes): plt.figure(figsize(10, 8)) # 1. 画所有节点 xs [n.x for n in nodes] ys [n.y for n in nodes] plt.scatter(xs, ys, cblack, markero, labelCustomer, zorder5) plt.scatter(nodes[0].x, nodes[0].y, cred, markers, s200, labelDepot, zorder10) # 2. 画卡车路径红色实线 truck_x [nodes[i].x for i in solution.truck.route] truck_y [nodes[i].y for i in solution.truck.route] plt.plot(truck_x, truck_y, r-, linewidth2, labelTruck Route) # 3. 画无人机任务蓝色虚线 for drone in solution.drones: for mission in drone.missions: launch, cust, rend mission # 画 launch - customer - rendezvous 的折线 pts_x [nodes[launch].x, nodes[cust].x, nodes[rend].x] pts_y [nodes[launch].y, nodes[cust].y, nodes[rend].y] plt.plot(pts_x, pts_y, b--, linewidth1.5, alpha0.7) # 在客户点上做个标记 plt.scatter(nodes[cust].x, nodes[cust].y, cblue, edgecolorsblue, s100, zorder6) plt.legend() plt.grid(True, linestyle--, alpha0.5) plt.title(Truck-Drone Collaborative Delivery Solution) plt.xlabel(X Coordinate) plt.ylabel(Y Coordinate) plt.axis(equal) plt.show()性能对比柱状图用柱状图对比不同算法在不同算例下的总完成时间。灵敏度分析折线图展示续航E变化时目标函数值的变化趋势。一张精心绘制的路径图能直观展示你算法中“卡车-无人机”的协同模式是论文最有力的证据之一。6. 进阶思考与扩展方向如果你还有余力或者题目有进一步的要求可以考虑以下扩展方向这能让你的论文更有深度。6.1 多目标优化现实中企业可能不仅关心时间最短还关心成本最低油耗、人力、无人机折旧。这就成了一个多目标优化问题。你可以将目标函数设为最小化总完成时间和总行驶成本距离的加权和。通过调整权重可以得到一系列“帕累托最优解”并绘制帕累托前沿图分析时间与成本之间的权衡关系。6.2 动态与随机性更贴近现实的场景是动态和随机的客户订单可能随时到来动态无人机的飞行时间可能受风速影响随机卡车的行驶时间可能受交通状况影响随机。这时问题就变成了随机规划或动态规划。你可以引入场景树或采用滚动时域优化策略每当新订单到达或状态更新时重新快速运行一次你的启发式算法对剩余任务进行重新规划。6.3 异质车队与充电约束你的模型可以进一步复杂化车队中有多种型号的卡车容量不同、速度不同和无人机载重不同、续航不同。无人机可能需要在中途的充电站充电而不是返回卡车。这就需要引入更复杂的资源分配和时间约束模型。对于竞赛而言能把基础的单目标、静态、同质车队的模型做扎实算法实现稳定结果分析透彻就已经能拿到很高的分数了。这些扩展方向可以作为你论文“模型评价与推广”部分的内容展示你对问题更深入的理解和思考。最后想说的是数学建模比赛是一个系统工程从审题、建模、编程到写作环环相扣。这道B题的关键在于理解“协同”二字的含义并把它转化为数学上的“同步约束”。算法上不必追求最新最炫稳定、健壮、能出结果的算法就是好算法。写作上务必清晰、直观、有逻辑。祝你在比赛中能高效协作把这一套方法用起来顺利拿下这道充满挑战的无人机物流配送题。