卡车与无人机协同配送建模：从VRP变体到两阶段启发式算法求解

1. 问题拆解当卡车遇上无人机物流配送的协同博弈五一数学建模竞赛的C题每年都是兵家必争之地因为它往往聚焦于一个具体、前沿且复杂的现实问题。今年的题目“具有无人机的物流配送问题”直接把“卡车无人机”的协同配送模式推到了我们面前。这绝不是一个简单的路径规划问题而是一个典型的“车辆路径问题”的复杂变体业内通常称之为“车辆与无人机协同配送问题”。我参加过不少这类竞赛也研究过不少实际案例深知这个题目的魅力与挑战在于它要求我们在一个动态的、多约束的系统中找到全局最优的“协同策略”而不仅仅是“最短路径”。简单来说题目场景可以这样理解你有一个配送中心一批需要送达的客户点一辆大卡车和若干架搭载在卡车上的无人机。卡车容量大、续航长但速度慢、受路网限制无人机灵活、能直线飞行、速度可能更快但载重小、续航短。核心矛盾就出来了如何让卡车和无人机分工合作在满足各自物理限制如无人机电量、卡车容量的前提下用最短的总时间或总成本完成所有配送任务这背后涉及几个必须理清的关键点也是我们建模的基石协同模式是卡车作为移动仓库释放和回收无人机“卡车发射-回收”模式还是卡车和无人机从仓库独立出发在客户点会合“会合点”模式题目通常会指定或隐含一种这直接决定了模型的拓扑结构。时间耦合无人机飞出去送货卡车不能干等着。卡车需要继续行驶去下一个无人机回收点或者去服务其他客户。无人机送完货后必须能追上卡车或在指定地点被回收。这里存在严格的时间窗口约束是模型中最精妙也最容易出错的部分。资源约束卡车的容量能携带的包裹和无人机数量、无人机的最大航程电量、每架无人机的载货量通常为1件这些硬性限制构成了模型的边界条件。优化目标是最小化总完工时间Makespan还是最小化总行驶距离或是加权总成本目标函数引导着整个优化方向。看到网络上很多人在搜“数学建模算法”、“路径规划算法”恨不得马上套用遗传算法、蚁群算法。但在我来看第一步永远不是选算法而是把上述问题逻辑用数学语言清晰地定义出来。模型建得漂亮算法只是求解工具模型逻辑有漏洞再高级的算法也出不来好结果。2. 模型构建从概念到数学公式的精确翻译基于上面的拆解我们可以着手构建数学模型。这里我以一个典型的“卡车作为移动母舰”的场景为例展示如何将问题转化为数学规划模型。假设我们有集合配送中心0客户点集合C {1, 2, ..., n}卡车T无人机集合D {1, 2, ..., m}。参数d_ij_t: 卡车从点i到点j的行驶时间。d_ij_d: 无人机从点i到点j的飞行时间通常为直线距离除以速度。E_max: 无人机的最大续航时间电量。Q_t: 卡车的载货容量。Q_d: 无人机的载货容量通常为1。service_time: 在每个点的服务时间装卸货。核心决策变量x_ij_t: 二进制变量卡车是否从点i行驶到点j。x_ij_dk: 二进制变量无人机k是否从点i飞往点j。a_i: 卡车到达点i的时间。b_i: 无人机离开点i的时间对于被无人机服务的点。l_i_t: 卡车离开点i时的负载。l_i_dk: 无人机k离开点i时的负载。模型框架以最小化总完工时间为例目标函数 MinimizeT_total总完成时间约束条件流平衡约束确保每个客户点都被访问一次被卡车或无人机。对于每个客户点i卡车或无人机的访问流之和为1。卡车路径约束卡车从仓库出发最后返回仓库形成回路。sum(x_0j_t) 1从仓库出发sum(x_i0_t) 1返回仓库对于每个中间点流入等于流出。无人机任务约束每架无人机的每次飞行都是一个从卡车发射、服务一个或多个客户、再返回卡车回收的行程。无人机必须在卡车上被发射和回收。定义“同步点”卡车停放点发射点i和回收点j。无人机从i飞到客户c再飞到j其总飞行时间必须小于等于E_max。关键的时间耦合约束卡车到达回收点j的时间a_j必须大于等于无人机完成客户点服务后到达j的时间。同时无人机在i点被发射的时间必须等于卡车在i点完成服务或等待的时间。这个时间耦合是模型的核心可以用大M法线性化处理。例如引入一个二进制变量y_ij表示卡车是否在点i发射无人机并在点j回收然后添加约束a_j b_c d_cj_d - M*(1 - y_ij)其中M是一个足够大的数。容量约束卡车和无人机在任意时刻的负载不能超过其容量。时间窗约束隐式由协同逻辑自然产生。卡车在回收点必须等待无人机抵达才能继续前行或进行下一轮操作。子回路消除约束防止卡车路径中出现不包含仓库的独立回路这是VRP问题的标准约束可用MTZMiller-Tucker-Zemlin约束或流约束实现。注意这是一个高度简化的框架。实际比赛中题目会给出更具体的细节比如无人机是否必须返回原卡车、卡车是否可以同时携带多架无人机、无人机是否可以连续服务多个客户点“多跳”模式等。这些细节会显著增加模型的复杂度和约束数量。模型选择的心得对于这种NP-Hard问题我们通常构建一个混合整数线性规划模型。虽然直接求解大规模算例可能困难但MILP模型的价值在于其表述的清晰性和严谨性。它能作为基准模型验证后续启发式算法的有效性。很多优秀论文都会先给出MILP模型再说明由于其求解困难进而设计启发式算法。3. 算法设计精确解与启发式的权衡艺术面对几十甚至上百个客户点想直接用CPLEX、Gurobi求解上述MILP模型得到最优解在比赛有限的时间内几乎是不可能的。因此算法设计是解题的关键也是拉开论文档次的地方。我们的策略通常是“精确模型指导启发式算法求解”。3.1 两阶段启发式算法一种务实高效的思路这是我比较推荐且经过实践检验的一种框架特别适合初次接触此类问题的队伍。第一阶段客户点聚类与任务分配目标决定哪些客户点由卡车服务哪些由无人机服务。思路无人机擅长服务那些离卡车路径不太远、且包裹重量小的客户。我们可以设计一个“无人机适宜度”评分。方法先忽略无人机用一个快速的启发式算法如节约算法、最近邻法生成一条纯卡车的初始路径。对路径上的每个客户点i计算一个“偏离度”假设卡车路径上i的前后节点是p和s则无人机从p飞到i再飞到s的时间与卡车从p到s的时间之差。差值越小说明让无人机“拐出去”服务i的成本越低。考虑无人机续航E_max。只有当“从p飞i再飞s”的总时间 E_max时点i才有可能被无人机服务。根据偏离度、客户点需求重量需小于无人机载重等因素筛选出候选的无人机服务点集。输出一个初步的“卡车必访点”列表和“无人机候选点”列表。第二阶段协同路径优化目标在确定了大致分工后优化卡车的行驶路径以及无人机的发射/回收计划。思路将问题转化为一个扩展的车辆路径问题。此时卡车路径上的每个节点可能是一个“发射点”或“回收点”这些节点本身也带有时间约束。方法构建搜索空间卡车路径是一个序列。无人机任务可以看作“插入”到这个序列中的子任务。例如卡车路径是0 - A - B - C - 0。一个无人机任务可能是“在A点发射服务客户U在B点回收”。那么新的序列可以看作是0 - A(发射U) - B(回收U) - C - 0其中A和B成了有特殊属性的节点。使用元启发式算法搜索遗传算法将解编码为染色体。一种有效的编码方式是“两段式编码”第一段表示客户点访问顺序混合了卡车直接服务和无人机服务的客户点第二段表示每个点是由卡车服务还是由哪架无人机服务。解码时需要设计一个复杂的解码器能根据编码解析出具体的卡车路径和无人机调度方案并计算时间。模拟退火/禁忌搜索基于当前解一个完整的协同方案定义邻域动作。例如交换交换两个由卡车服务的客户点的顺序。插入将一个无人机服务点改为由卡车服务并插入到卡车路径的某个位置。无人机重分配将一个客户点从一架无人机任务中移除分配给另一架无人机或卡车。发射/回收点调整改变某个无人机任务的发射点或回收点。每次邻域移动后需要快速评估新解的目标值。这里需要编写一个仿真函数输入卡车路径和无人机任务列表模拟整个配送过程计算总时间。这个函数要严格检查时间耦合约束和续航约束。局部搜索加强在元启发式算法中嵌入局部搜索。例如对当前解中的卡车路径部分使用2-opt算子进行局部优化对无人机任务分配尝试贪心调整。3.2 算法实现中的关键技巧与坑点解码器的设计是重中之重尤其是在遗传算法中一个鲁棒、高效、能处理各种约束的解码器决定了算法的成败。解码器一旦有逻辑漏洞整个算法就会跑出不可行解或错误结果。可行性维护在邻域搜索中很多移动会产生不可行解如无人机续航不足。有两种策略一是在移动设计时就尽量避免产生不可行解难度大二是允许产生不可行解但在目标函数中施加一个很大的惩罚项引导搜索回到可行域。后者更常用也更容易实现。目标函数的设计除了总时间可以将卡车的等待时间、无人机的空飞时间作为惩罚项加入目标函数以鼓励更紧密的协同。初始解的生成一个好的初始解能极大加快收敛速度。除了用简单的最近邻法可以尝试先全部用卡车服务再用贪心策略将一些点“剥离”给无人机。踩坑实录在一次模拟中我们忽略了无人机的起降时间和服务时间认为它们可以忽略不计。结果在解规模较大时这些微小时间的累积导致无人机总是在回收点“迟到”整个调度方案崩溃。教训必须将所有的操作时间起飞、降落、装卸货纳入模型和仿真哪怕题目没明确给出也要根据常识进行合理假设并在论文中说明。4. 求解与验证让模型和代码跑起来有了算法设计接下来就是编码实现和结果分析。这部分是论文“实干”精神的体现。4.1 编程语言与工具选择Python无疑是首选。生态丰富NumPy,Pandas处理数据Matplotlib画图PuLP或OR-Tools可以用于构建和求解小规模MILP模型作为基准。元启发式算法自己实现也很灵活。MATLAB优化工具箱强大画图方便适合算法原型快速验证。但对于复杂的逻辑控制和数据结构处理不如Python直观。核心建议用Python。编写一个清晰的仿真器是核心。这个仿真器的输入是“卡车路径序列”和“无人机任务列表”输出是总时间、各主体时间线、以及是否违反约束的标识。4.2 参考代码框架Python示例这里给出一个高度简化的模拟退火算法框架用于说明核心逻辑。import numpy as np import random import math class DroneTruckSimulator: 协同配送仿真器 def __init__(self, customer_locs, truck_speed, drone_speed, drone_range): self.customer_locs customer_locs self.truck_speed truck_speed self.drone_speed drone_speed self.drone_range drone_range def calculate_distance(self, loc1, loc2): 计算两点间欧氏距离 return np.linalg.norm(np.array(loc1) - np.array(loc2)) def simulate(self, solution): 仿真一个解。 solution: 一个字典包含truck_route和drone_missions drone_missions: 列表每个元素为 (launch_node, customer_node, retrieve_node) truck_route solution[truck_route] # e.g., [0, 1, 3, 2, 0] drone_missions solution[drone_missions] # e.g., [(1, 4, 3), (3, 5, 2)] total_time 0 truck_time 0 truck_pos truck_route[0] events [] # 记录所有事件卡车到达某点、无人机发射/回收 # 1. 计算纯卡车行驶时间线先忽略无人机 truck_timeline [0] for i in range(1, len(truck_route)): dist self.calculate_distance(self.customer_locs[truck_route[i-1]], self.customer_locs[truck_route[i]]) travel_time dist / self.truck_speed truck_time travel_time # 假设每个点服务时间为1单位 truck_time 1 truck_timeline.append(truck_time) # 2. 处理无人机任务调整时间线 # 这是一个简化处理实际情况需要迭代调整直到所有时间约束满足 for mission in drone_missions: launch_idx truck_route.index(mission[0]) retrieve_idx truck_route.index(mission[2]) launch_time truck_timeline[launch_idx] retrieve_time truck_timeline[retrieve_idx] # 无人机飞行时间 fly_time (self.calculate_distance(self.customer_locs[mission[0]], self.customer_locs[mission[1]]) self.calculate_distance(self.customer_locs[mission[1]], self.customer_locs[mission[2]])) / self.drone_speed # 检查续航 if fly_time self.drone_range: return float(inf), False # 不可行解返回无穷大代价 # 检查时间耦合无人机到达回收点的时间 卡车到达回收点的时间 drone_arrival_time launch_time fly_time if drone_arrival_time retrieve_time: # 无人机晚了卡车需要等待 wait_time drone_arrival_time - retrieve_time # 调整卡车从回收点开始往后的所有时间点 for j in range(retrieve_idx, len(truck_timeline)): truck_timeline[j] wait_time retrieve_time truck_timeline[retrieve_idx] # 更新回收点时间 total_time truck_timeline[-1] # 卡车返回仓库的时间 return total_time, True def simulated_annealing(initial_solution, simulator, iterations5000, initial_temp100, cooling_rate0.995): 模拟退火算法主框架 current_solution initial_solution current_cost, feasible simulator.simulate(current_solution) if not feasible: current_cost float(inf) best_solution current_solution.copy() best_cost current_cost temp initial_temp for i in range(iterations): # 生成邻域解 (这里需要根据你的解表示设计具体的邻域操作函数) new_solution generate_neighbor(current_solution) new_cost, feasible simulator.simulate(new_solution) if not feasible: new_cost float(inf) # 接受准则 if new_cost current_cost or random.random() math.exp((current_cost - new_cost) / temp): current_solution new_solution current_cost new_cost if current_cost best_cost: best_solution current_solution.copy() best_cost current_cost # 降温 temp * cooling_rate if i % 100 0: print(fIteration {i}, Temp {temp:.2f}, Best Cost {best_cost:.2f}) return best_solution, best_cost # 示例生成初始解和邻域解的函数需要根据你的编码方式具体实现 def generate_neighbor(solution): 示例随机交换卡车路径中的两个节点 new_solution solution.copy() route new_solution[truck_route] if len(route) 3: # 除了仓库头尾 i, j random.sample(range(1, len(route)-1), 2) route[i], route[j] route[j], route[i] # 更复杂的邻域操作还应包括对drone_missions的修改 return new_solution代码使用要点上面的simulate函数是极度简化的真实情况需要更精细的时间推进仿真处理并发、等待等复杂逻辑。generate_neighbor函数是算法的核心之一你需要设计多种有效的邻域操作并在算法中随机选择使用。初始解可以通过一个简单的构造启发式算法生成比如全部点由卡车服务的最近邻路径。4.3 结果分析与可视化跑出结果后不能只扔一个总时间了事。敏感性分析改变关键参数无人机续航、速度、客户点数量观察总时间的变化趋势。这能体现你对模型机理的理解。例如可以绘制“无人机续航 vs 总配送时间”的曲线会发现存在一个临界续航超过后对效能的提升就不明显了。对比实验基准对比与纯卡车配送方案对比量化无人机带来的效率提升百分比。算法对比如果你的算法有多个变体如不同邻域结构对比它们的性能。场景对比如果题目有多个数据集不同规模、分布分析你的算法在不同场景下的表现是否稳定。可视化一图胜千言。甘特图展示卡车和每架无人机的时间线何时何地执行什么任务等待时间一目了然。可以用Matplotlib的broken_barh绘制。路径图在地图上画出卡车的行驶路径实线以及每架无人机的飞行轨迹虚线或不同颜色的线发射点和回收点用特殊标记标出。收敛曲线展示模拟退火或遗传算法在迭代过程中最优解的变化情况体现算法的收敛性。5. 论文撰写与提升从解题到脱颖而出的临门一脚模型建了算法编了结果跑了最后都要落到论文上。数学建模竞赛本质上是一场“基于数学的写作竞赛”。摘要重中之重采用“问题概述-模型-方法-结果-结论”的结构但要用精炼的语言。必须包含针对什么问题建立了什么模型名称设计了什么算法名称得到了什么结果关键数据如效率提升了XX%最后有什么结论或发现。避免空洞的形容词多用数据说话。问题重述与分析不要照抄题目。用自己的话梳理问题的要素、约束、目标并画出逻辑关系图。明确指出问题的难点在于“时间耦合”和“资源约束下的协同”。模型假设合理且必要。例如“假设无人机在任意两客户点间沿直线飞行”、“忽略起飞降落时间”、“客户点需求已知且确定”等。每一条假设都要服务于简化模型且不能影响问题的核心。符号说明表格呈现清晰美观。按模型、决策变量、参数分类。模型建立这是核心章节。先讲整体思路如两阶段框架再分小节详述。公式要编号重要的约束要解释其物理意义。技巧对于复杂的约束如时间耦合可以用“约束5确保了无人机必须在卡车到达回收点之后才能被回收”这样的文字辅助说明。算法设计讲清楚为什么选这个算法针对问题特性算法的流程建议用流程图关键操作如编码、解码、邻域动作的具体设计以及如何保证解的可行性。模型求解与结果分析展示程序运行的环境、参数设置。用表格展示不同数据集或不同参数下的结果。结合图表进行分析解释现象背后的原因。例如“从图3可以看出当客户点分布稀疏时无人机协同的优势更加明显因为无人机可以直线飞行避开卡车绕行的弯路。”模型评价与推广客观评价自己模型的优点如考虑全面、求解高效和缺点如未考虑动态交通、假设较理想。提出可能的改进方向如加入随机需求、考虑多仓库。将模型推广到其他类似场景如消防车与无人机协同救援、巡检车与无人机协同巡检。参考文献规范引用体现你的研究有据可依。附录可以放核心代码的片段不要全部粘贴以及大的结果数据表。个人体会一篇优秀的数模论文读起来应该像一个逻辑严密、层层递进的技术报告。评委往往没有时间细读你的每一行代码但他们通过论文的结构、图表和关键论述就能判断出你们队对问题的理解深度和工作量。因此图表的美观与专业、论述的清晰与自信、对结果背后机理的洞察往往是获得高分的关键。最后保持论文排版整洁、格式规范这是最基本的专业体现。