1. 项目概述当数学建模遇上无人机物流最近几年但凡关注数学建模竞赛的朋友应该都注意到了“无人机物流配送”这个题目的热度。从国赛、美赛到各种地区性赛事它几乎成了出题老师的“心头好”。这不2024年的五一数学建模联赛B题又把“具有无人机的物流配送问题”摆在了我们面前。这题目听起来挺时髦但内核其实非常经典它本质上是一个复杂的、多约束的优化问题核心目标是如何高效、经济、安全地把一堆包裹从仓库送到分散的客户手里而这次你的配送员不只是卡车还有能飞檐走壁的无人机。为什么这个组合如此受青睐因为它精准地踩在了两个时代脉搏上一是电商物流对“最后一公里”极致效率的追求二是无人机技术从概念走向大规模商用的临界点。题目给的场景很具体一个配送中心多辆卡车多架无人机一群地理位置各异的客户每个客户有特定的货物需求和配送时间窗。卡车可以携带无人机和货物行驶在公路网上无人机则从卡车上起飞执行“最后一公里”或“中途接力”的配送然后再返回卡车或直接飞往下一个集结点。你的任务就是为这个混合车队设计一套最优的配送方案包括路径规划、任务分配、起降调度最终使得总成本或总时间最小。这不仅仅是写几行代码跑个算法那么简单。它要求你建立一个能同时刻画车辆路径问题VRP和无人机旅行商问题DTSP的混合模型并处理好两者之间复杂的耦合关系。比如卡车不仅是运输工具还是无人机的移动“航母”和充电站无人机的续航里程、载重限制、起降时间都是硬约束客户的时间窗可能让整个调度计划牵一发而动全身。我参加过也指导过不少这类比赛发现很多队伍一开始就埋头搞算法结果模型建得漏洞百出后面全在打补丁。所以咱们这次得先把思路理清楚把问题拆解明白。2. 核心问题拆解与建模思路面对这么一个综合性的题目直接上手建模很容易迷失。我的习惯是像剥洋葱一样把它一层层拆开看清楚每个核心子问题及其相互关系。2.1 问题本质一个多层耦合的优化问题首先我们要认清这不是一个单纯的路径规划问题而是一个资源受限的多模态协同调度问题。我们可以把它分解为以下几个关键层次客户聚类与区域划分哪些客户适合由卡车直接服务比如订单量大、位置沿主干道哪些客户适合交给无人机比如偏远、分散、道路不便这需要对客户的地理位置、需求量进行初步分析形成初步的任务分区。卡车路径规划VRP with Time Windows这是传统车辆路径问题的升级版。卡车有容量限制客户有服务时间窗要求。卡车的路径不仅服务于自身配送的客户点还必须作为无人机的移动基地在合适的地点我们称为“起降点”或“ rendezvous point”进行无人机的释放与回收。无人机任务分配与路径规划DTSP对于分配给无人机的客户群需要规划每架无人机的飞行路线。这里的关键约束是续航里程和载重。无人机从卡车起飞服务一个或多个客户后必须返回卡车同一点或另一点。这形成了一个个以卡车停靠点为起终点的无人机子旅行商问题。卡车-无人机协同调度这是整个问题的“灵魂”。卡车的行程决定了无人机可用的起降点和时间窗口。无人机的飞行时间又反过来制约了卡车的等待时间。两者必须在时间和空间上紧密同步。例如卡车到达某个起降点释放无人机后是原地等待还是继续前往下一个点再回收无人机这需要精确的时间计算。2.2 建模框架选择数学规划 vs. 启发式算法明确了子问题接下来就是选择建模和求解的工具。主流思路有两类精确算法数学规划例如建立混合整数线性规划MILP模型。你可以用0-1变量x_{ij}^k表示卡车k是否从i点行驶到j点用另一个0-1变量y_{ij}^d表示无人机d是否从i点飞往j点然后加上流量平衡、容量、时间窗等约束最后最小化总成本距离或时间。优点是严谨能在理论上求得最优解。缺点是对于本题这种规模客户点可能上百模型会极其庞大变量和约束数量爆炸即使用CPLEX、Gurobi等商业求解器也可能在比赛时间内无法得到可行解。启发式与元启发式算法这是数学建模竞赛中更实际、更主流的选择。我们并不追求绝对的最优解而是在可接受的时间内找到一个高质量的“满意解”。常用框架包括两阶段法第一阶段先用聚类算法如K-means 基于距离和需求将客户初步划分为“卡车服务簇”和“无人机服务簇”。第二阶段对卡车簇用改进的遗传算法GA或模拟退火SA求解带时间窗的VRP对每个无人机簇用贪心算法或蚁群算法ACO规划飞行路线最后用一个协调算法来微调卡车和无人机的汇合时间。协同进化算法设计两个种群一个代表卡车路径的编码一个代表无人机任务的编码。两个种群独立进化但通过一个共同的评估函数总成本进行交互和选择。这能更好地探索卡车与无人机协同的解空间。基于仿真的优化先设计一套调度规则例如卡车优先服务大客户无人机见缝插针服务周边小客户然后通过离散事件仿真来评估方案性能再用优化算法调整规则参数。我的经验之谈对于限时竞赛我强烈推荐**“聚类改进遗传算法”的两阶段启发式框架**。它结构清晰模块化好易于实现和调试。不要把问题想得太复杂先做出一个能跑通的、逻辑正确的方案比追求一个高大上但调不通的模型要重要得多。先把“树干”搭起来再去优化“枝叶”。3. 模型构建的关键细节与实操要点有了框架我们来填充血肉。这部分是决定你论文能否脱颖而出的关键很多细节处理不好模型就会变得脆弱或不切实际。3.1 如何科学地定义“起降点”题目通常不会明确规定卡车在哪里释放无人机。这是一个需要你定义的决策变量。常见做法有客户点即起降点最简单的方式。卡车到达某个客户点在服务该客户的同时释放无人机去服务附近其他客户。优点是模型简单无需引入新节点。缺点是限制了灵活性无人机只能从有公路通达的客户点起飞。道路网络节点将道路交叉口或特定坐标设为候选起降点。这增加了搜索空间但更贴合实际卡车可以在路边安全区域停靠。你需要将这些点纳入整体网络中进行路径规划。虚拟起降点在客户点周围一定半径如无人机单程最大航程的一半内动态生成虚拟点。这种方法灵活性最高但建模和求解也最复杂。实操建议对于初次接触的队伍采用**“客户点即起降点”** 策略最为稳妥。在模型假设中明确说明这一点并论证其合理性例如城市配送中客户地址通常有可供临时停车的场地。这能大大简化你的模型复杂度。3.2 时间窗与同步约束的处理时间窗是让问题从“难”变成“非常难”的关键。卡车和无人机都有自己的时间线必须让它们在汇合点“碰上面”。卡车时间线你需要为每个节点配送中心、客户点、起降点计算卡车的到达时间AT_i、服务开始时间ST_i和离开时间DT_i。公式大致是AT_j DT_i travel_time(i, j)ST_j max(AT_j, time_window_start_j)DT_j ST_j service_time_j。无人机时间线对于从卡车在点i释放服务客户集C{c1, c2, ...}然后返回点j的无人机你需要计算其总飞行时间flight_time(i, C, j)。这个时间必须小于等于无人机的续航时间。同步约束这是最烧脑的部分。如果无人机从点i释放在点j回收那么卡车的离开点i的时间DT_i必须晚于无人机的释放准备完成时间。卡车到达点j的时间AT_j必须早于无人机返回点j的时间并且卡车需要在点j等待一段时间等待时间wait_time_j drone_return_time_j - AT_j。或者你可以约束AT_j约等于drone_return_time_j允许一个很小的时间容差epsilon。一个实用的简化技巧在算法设计中可以先忽略严格的时间窗只优化路径距离得到一个初始路径。然后再引入一个时间推进算法沿着这条路径模拟运行插入等待时间以满足时间窗和同步要求并计算实际的总时间成本。如果某些点无法满足比如无人机飞不回来则给这个解一个很大的惩罚值引导优化算法淘汰它。这种方法将复杂的时空耦合约束转化为了目标函数中的惩罚项更易于启发式算法处理。3.3 目标函数的设定目标函数是指挥棒。常见选项有最小化总行驶距离最直观但可能忽略了时间成本。最小化总完成时间Makespan即最后一辆车/无人机返回配送中心的时间。这更强调整体效率。最小化总成本可以定义为a * 总距离 b * 总时间 c * 使用的车辆数其中a, b, c是权重系数。这最全面但也需要你合理设定权重。我的选择在竞赛中我通常选择最小化总完成时间作为首要目标。因为它直接对应“配送效率”意义明确且计算方便就是模拟结束时的时间戳。可以在论文中讨论如果考虑成本可以对方案进行简单的折算分析。4. 算法实现与核心代码逻辑这里我以最经典的“两阶段法聚类 改进遗传算法”为例给出一个可操作的实现蓝图。我们使用Python语言借助scikit-learn、numpy和deap(一个进化算法框架) 或自己编写遗传算法核心。4.1 第一阶段数据预处理与客户聚类假设我们有客户数据customers包含ID、坐标(x,y)、需求量demand、时间窗[e, l]、服务时间service_time。import numpy as np from sklearn.cluster import KMeans def preprocess_and_cluster(customers, truck_capacity, drone_capacity, drone_range): 预处理数据并进行初步聚类。 返回卡车客户列表和无人机客户列表。 coords np.array([[c.x, c.y] for c in customers]) demands np.array([c.demand for c in customers]) # 规则1需求量超过无人机载重的直接分配给卡车 truck_candidate_indices [i for i, d in enumerate(demands) if d drone_capacity] drone_candidate_indices [i for i, d in enumerate(demands) if d drone_capacity] drone_coords coords[drone_candidate_indices] # 规则2对剩余客户根据距离配送中心的远近和密集程度用K-means聚类 # 这里简单起见以距离配送中心超过一定阈值为准分配给无人机 depot np.array([0, 0]) # 假设配送中心在(0,0) distances_to_depot np.linalg.norm(drone_coords - depot, axis1) remote_threshold drone_range * 0.4 # 经验参数距离超过无人机航程40%的考虑用无人机 final_truck_indices list(truck_candidate_indices) final_drone_indices [] for idx, (cust_idx, dist) in enumerate(zip(drone_candidate_indices, distances_to_depot)): if dist remote_threshold: final_drone_indices.append(cust_idx) else: # 还可以加入其他规则比如客户点是否易于停车等 final_truck_indices.append(cust_idx) truck_customers [customers[i] for i in final_truck_indices] drone_customers [customers[i] for i in final_drone_indices] return truck_customers, drone_customers4.2 第二阶段卡车路径规划改进遗传算法我们为卡车客户规划路径。染色体编码采用最常用的顺序编码例如[0, 3, 1, 4, 2, 0]表示从配送中心(0)出发依次访问客户3,1,4,2再返回中心。import random from deap import base, creator, tools, algorithms # 定义问题和个体 creator.create(FitnessMin, base.Fitness, weights(-1.0,)) # 最小化目标 creator.create(Individual, list, fitnesscreator.FitnessMin) def eval_truck_vrp(individual, truck_customers, truck_capacity, distance_matrix): 评估函数计算一条卡车路径的总距离并检查容量约束返回惩罚值。 total_distance 0 current_load 0 penalty 0 # 从配送中心(索引0)开始 from_node 0 for gene in individual: to_node gene total_distance distance_matrix[from_node][to_node] current_load truck_customers[to_node-1].demand # 假设个体编码中0代表配送中心客户索引从1开始 if current_load truck_capacity: penalty 10000 # 容量约束违反施加巨大惩罚 from_node to_node # 返回配送中心 total_distance distance_matrix[from_node][0] return (total_distance penalty,) def cx_partially_matched(ind1, ind2): 部分匹配交叉PMX用于顺序编码。 size min(len(ind1), len(ind2)) p1, p2 [0]*size, [0]*size for i in range(size): p1[ind1[i]] i p2[ind2[i]] i cxpoint1 random.randint(0, size-1) cxpoint2 random.randint(0, size-1) if cxpoint1 cxpoint2: cxpoint1, cxpoint2 cxpoint2, cxpoint1 for i in range(cxpoint1, cxpoint2): temp1 ind1[i] temp2 ind2[i] ind1[i], ind1[p1[temp2]] temp2, temp1 ind2[i], ind2[p2[temp1]] temp1, temp2 p1[temp1], p1[temp2] p1[temp2], p1[temp1] p2[temp1], p2[temp2] p2[temp2], p2[temp1] return ind1, ind2 def mut_reverse_sequence(individual): 逆转变异随机选择一段序列并反转。 start, stop sorted(random.sample(range(len(individual)), 2)) individual[start:stop] reversed(individual[start:stop]) return individual, # 主算法流程 def solve_truck_vrp(truck_customers, distance_matrix, truck_capacity, pop_size300, gen_num500): toolbox base.Toolbox() # 注册属性、个体、种群 n_customers len(truck_customers) toolbox.register(indices, random.sample, range(1, n_customers1), n_customers) # 客户编号从1开始 toolbox.register(individual, tools.initIterate, creator.Individual, toolbox.indices) toolbox.register(population, tools.initRepeat, list, toolbox.individual) toolbox.register(evaluate, eval_truck_vrp, truck_customerstruck_customers, truck_capacitytruck_capacity, distance_matrixdistance_matrix) toolbox.register(mate, cx_partially_matched) toolbox.register(mutate, mut_reverse_sequence, indpb0.05) toolbox.register(select, tools.selTournament, tournsize3) pop toolbox.population(npop_size) hof tools.HallOfFame(1) stats tools.Statistics(lambda ind: ind.fitness.values) stats.register(avg, np.mean) stats.register(min, np.min) # 运行算法 algorithms.eaSimple(pop, toolbox, cxpb0.7, mutpb0.2, ngengen_num, statsstats, halloffamehof, verboseTrue) best_individual hof[0] best_fitness best_individual.fitness.values[0] return best_individual, best_fitness4.3 无人机任务分配与路径规划对于分配给无人机的客户我们需要将它们分组并分配给不同的无人机行程。这里采用一种贪心算法def assign_drone_trips(drone_customers, depot, drone_capacity, drone_range, distance_func): 贪心算法分配无人机行程。 返回一个列表每个元素是一个无人机行程客户ID列表。 trips [] unserved drone_customers.copy() while unserved: trip [] current_load 0 # 假设无人机从卡车当前停靠点current_point起飞这里简化起点设为depot current_point depot remaining_range drone_range while unserved and remaining_range 0: # 寻找在剩余航程内距离当前点最近且满足载重的客户 feasible_customers [c for c in unserved if distance_func(current_point, c.location) distance_func(c.location, depot) remaining_range and current_load c.demand drone_capacity] if not feasible_customers: break # 选择最近的一个 next_customer min(feasible_customers, keylambda c: distance_func(current_point, c.location)) trip.append(next_customer.id) dist_to_customer distance_func(current_point, next_customer.location) # 假设服务客户后立即飞回仓库计算剩余航程最保守估计 # 更精确的估计需要考虑服务完所有客户后一起飞回 remaining_range - dist_to_customer current_load next_customer.demand current_point next_customer.location unserved.remove(next_customer) if trip: trips.append(trip) else: # 如果连一个客户都无法服务说明问题参数可能有问题 print(Warning: A customer cannot be served by drone under current constraints.) break return trips4.4 协同调度与时间推进模拟这是将卡车路径和无人机行程“缝合”起来的关键一步。我们需要沿着卡车的最优路径决定在哪些点释放和回收无人机并计算最终时间。def simulate_schedule(truck_route, truck_speed, drone_trips, drone_speed, customers_dict, depot): 时间推进模拟。 truck_route: 卡车路径节点ID列表首尾是配送中心。 drone_trips: 无人机行程列表每个行程已知其服务的客户ID。 返回总完成时间和详细时间线。 time 0 current_pos depot truck_timeline [] drone_assignments {} # 记录每个无人机行程从哪个卡车点释放在哪个点回收 # 简化策略按顺序将无人机行程分配给卡车路径上合适的客户点 # 更复杂的策略需要优化分配 trip_index 0 for i, node_id in enumerate(truck_route): if node_id 0: # 配送中心 arrive_time time service_time 0 # 在中心装卸货时间 depart_time arrive_time service_time truck_timeline.append((node_id, arrive_time, depart_time)) time depart_time continue customer customers_dict[node_id] # 卡车行驶到该点 travel_distance distance(current_pos, customer.location) travel_time travel_distance / truck_speed arrive_time time travel_time # 检查时间窗 start_service_time max(arrive_time, customer.time_window[0]) wait_time start_service_time - arrive_time # 服务时间包括可能的无人机操作 service_time customer.service_time # 尝试在此点分配无人机行程 if trip_index len(drone_trips): # 简单分配把这个行程分配给当前卡车点 drone_assignments[trip_index] {launch_node: node_id, recover_node: node_id} # 假设同点回收 # 无人机飞行时间计算需要根据行程具体计算 drone_trip drone_trips[trip_index] drone_flight_time calculate_drone_flight_time(drone_trip, customer.location, drone_speed, customers_dict) # 无人机飞行时间可能比卡车服务时间长卡车需要等待 service_time max(service_time, drone_flight_time) trip_index 1 depart_time start_service_time service_time truck_timeline.append((node_id, arrive_time, start_service_time, depart_time)) time depart_time current_pos customer.location # 总完成时间就是卡车返回中心的时间 # 最后一段回程 travel_distance distance(current_pos, depot) travel_time travel_distance / truck_speed total_makespan time travel_time return total_makespan, truck_timeline, drone_assignments5. 模型检验、优化与论文写作要点模型跑通了结果出来了但工作只完成了一半。如何检验你的模型如何优化它如何在论文中清晰地呈现这才是拿高分的关键。5.1 模型检验与敏感性分析有效性检验极端情况测试设置无人机航程为0你的模型应退化为经典的带时间窗车辆路径问题VRPTW。设置卡车成本极高模型应倾向于全部使用无人机在航程允许内。通过这些测试可以验证模型逻辑的基本正确性。小规模精确解对比生成一个只有5-10个客户的小规模算例尝试用枚举法或整数规划求精确解对比你的启发式算法结果计算误差百分比。敏感性分析这是论文的亮点。分析关键参数变化对结果的影响。无人机航程绘制总成本/完成时间随无人机航程变化的曲线。你会发现存在一个“临界航程”超过它后收益递减。无人机 vs. 卡车速度比分析无人机速度提升对整体效率的改善程度。客户分布对比客户集中分布和分散分布对方案的影响。通常客户越分散无人机的优势越明显。时间窗宽度分析时间窗变严格宽度变小对方案可行性和成本的影响。5.2 算法优化进阶思路如果你的基础模型跑得不错可以尝试以下优化让方案更上一层楼变邻域搜索VNS在遗传算法得到的解基础上使用VNS进行局部精细搜索。设计多种邻域结构如交换两个客户、反转一段路径、将一段路径移到另一个位置等能有效跳出局部最优。动态起降点选择不要固定起降点。在算法中将起降点选择也作为决策变量。可以在卡车路径附近动态生成候选点评估每个点释放/回收无人机的效果。考虑多无人机协同一辆卡车同时携带多架无人机。模型需要处理多架无人机从同一点起飞、可能在不同点回收的复杂调度目标是最大化并行度。这可以通过在编码中为每个卡车点关联一个无人机任务列表来实现。5.3 论文写作核心要点与避坑指南数学建模论文形式与内容同等重要。摘要这是评委第一眼看到的内容决定了他是否有兴趣继续读。要用精炼的语言概括问题、你的方法、模型、算法、主要结果和结论。避免细节突出亮点。例如“本文针对卡车-无人机协同配送问题构建了一个以最小化总完成时间为目标的混合整数规划模型。鉴于问题NP-Hard特性设计了一种结合K-means聚类与改进遗传算法的两阶段启发式算法。通过仿真对比验证了模型有效性并分析了无人机航程、客户分布等关键参数的影响。结果表明在客户分散度较高的场景下引入无人机可降低约22%的完成时间。”模型假设清晰合理。例如“假设无人机与卡车在客户点进行起降交接假设无人机续航里程为固定值且充电/换电池时间已计入服务时间假设道路网络为完全图两点间距离为欧氏距离。” 合理的假设能简化问题但要在优缺点分析中讨论其局限性。模型建立符号说明要清晰、完整。公式推导要严谨有逻辑连贯性。不要堆砌公式每个公式都要有文字解释其物理意义。算法设计用流程图文字说明。解释清楚编码方式、交叉变异操作、评估函数设计特别是约束如何处理成惩罚项。给出伪代码或关键代码片段。结果分析多用图表说话。提供清晰的路径规划图用Python的matplotlib或networkx绘制、收敛曲线图、敏感性分析图。表格对比不同参数下的结果。分析时要言之有物例如“如图5所示当无人机航程小于15km时总成本下降明显超过20km后成本下降趋于平缓说明在该场景下配备航程20km左右的无人机性价比最高。”模型评价与推广客观评价自己模型的优点如求解效率高、方案合理和缺点如未考虑交通拥堵、天气影响。提出几个可行的改进方向体现你的思考深度。最大的坑忽视可视化。一张清晰美观的路径规划图比十页文字描述都管用。务必花时间做好结果可视化。使用不同颜色和线型区分卡车路径和无人机飞行路线在图例中标注清楚。6. 常见问题排查与实战技巧结合我带队的经验队伍在实现过程中最容易卡在以下几个地方算法陷入局部最优收敛早检查评估函数中的惩罚项是否设置得过大过大的惩罚会淹没目标函数本身的信息导致算法早期就收敛到一些“可行但很差”的解。解决尝试动态惩罚系数初期设置小一些让算法充分探索后期逐渐增大。或者采用可行性规则Feasibility Rules优先保留可行解在可行解之间比较目标函数值。调整算法参数增大种群规模如从100调到300、提高变异概率如从0.01调到0.05、采用更复杂的交叉算子如顺序交叉OX。无人机行程规划不合理总是超航程检查你的贪心算法或路径规划是否只考虑了“最近邻”而忽略了返航计算剩余航程时必须用当前点到客户距离 客户到汇合点距离 剩余航程来判断。解决在规划无人机单次行程时采用插入法。从一个种子客户开始尝试将其他客户插入到行程的各个位置计算插入后总飞行距离的增加量选择增加量最小且满足约束的位置插入。时间同步无法满足模拟时出现“卡车等不到无人机”或“无人机等不到卡车”检查你的时间推进模拟逻辑是否有漏洞特别是当卡车在某个点释放无人机后是立即离开还是等待如果无人机在另一个点回收卡车到达该点的时间是否早于无人机解决在算法中引入时间缓冲和重调度机制。在评估一个解时如果发现某个汇合点时间冲突不是直接丢弃而是尝试微调卡车在该点前后的等待时间或者轻微调整路径上节点的访问顺序看能否消除冲突。可以将“时间冲突总量”作为一个额外的优化目标多目标优化或惩罚项。代码运行速度太慢无法在合理时间内求解优化距离计算预先计算好所有点对之间的欧氏距离存储为矩阵避免在循环中重复计算sqrt((x1-x2)^2 (y1-y2)^2)。向量化操作在评估种群适应度时尽量使用NumPy的向量化运算避免低效的Python循环。设定迭代停止条件不要盲目跑500代。可以监控最优解连续多少代没有改进如50代一旦满足就提前终止。最后记住数学建模竞赛的核心是用数学工具解决一个实际问题并清晰地将你的思考过程和解决方案传达给评委。从看到“具有无人机的物流配送问题”这个标题开始你的思考就应该是结构化的理解问题、分解问题、建立模型、设计算法、验证分析、总结展望。把每个环节做扎实你的论文就不会差。这个题目包罗万象足够你从多个角度展现能力无论是模型的严谨性、算法的创新性还是分析的深度。祝你在比赛中能搭建出自己满意的“空地一体化”配送网络。