卡车-无人机协同配送建模与优化：从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等求解器）只适用于客户点很少（比如N<20）的情况。对于竞赛规模（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, demand=0): self.id = id # 节点ID，0为配送中心 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, speed=1.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_makespan

4.3 模拟退火主循环框架

import random import copy def simulated_annealing(initial_solution, all_nodes, max_iter=10000): 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_cost

4.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 算法复杂度分析（简要说明）
算例分析与结果：
- 数据：如果题目没给数据，需要自己生成。说明生成规则（如客户点随机分布在某个区域，配送中心在中心等）。可以设计不同规模（N=20，50，100）的算例。
- 对比基准：为了体现你模型算法的优越性，必须设置对比基准。常见的基准有：
  - 纯卡车配送：即不考虑无人机，用经典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, c='black', marker='o', label='Customer', zorder=5) plt.scatter(nodes[0].x, nodes[0].y, c='red', marker='s', s=200, label='Depot', zorder=10) # 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-', linewidth=2, label='Truck 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--', linewidth=1.5, alpha=0.7) # 在客户点上做个标记 plt.scatter(nodes[cust].x, nodes[cust].y, c='blue', edgecolors='blue', s=100, zorder=6) plt.legend() plt.grid(True, linestyle='--', alpha=0.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题的关键在于理解“协同”二字的含义，并把它转化为数学上的“同步约束”。算法上不必追求最新最炫，稳定、健壮、能出结果的算法就是好算法。写作上务必清晰、直观、有逻辑。祝你在比赛中能高效协作，把这一套方法用起来，顺利拿下这道充满挑战的无人机物流配送题。