时空运动耦合的地空协同智能配送规划方法

doi:10.11918/202508061

时空运动耦合的地空协同智能配送规划方法

doi: 10.11918/202508061

付金宇^1,2,3 ，朱红⁴ ，杨子澳^1,2 ，宋罘林^1,2 ，汪义睿^1,2 ，曹建^1,2

1. 智能海洋航行器技术全国重点实验室（哈尔滨工程大学），哈尔滨 150001

2. 哈尔滨工程大学船舶工程学院，哈尔滨 150001

3. 哈尔滨工程大学南海研究院，海南三亚 572024

4. 哈尔滨工业大学仪器科学与工程学院，哈尔滨 150001

基金项目: 国家自然科学基金(52401367) ；海南省自然基金(525QN380) ；国家资助博士后研究人员计划项目（GZB20240946）；黑龙江省博士后面上项目(LBH-Z24011) ；智能海洋航行器技术全国重点实验室稳定支持项目（2024-HYHXO-WDZC01）

详细信息

作者简介

付金宇(1994—)，男，副研究员

通讯作者

付金宇，fujinyu@hrbeu.edu.cn

中图分类号: TP242.6

文献标识码: A

文章编号: 0367-6234(2026)01-0056-09

Trajectory planning method of heterogeneous multi-robot cooperative intelligent transportation under spatiotemporal and motion constraints

FU Jinyu^1,2,3 ， ZHU Hong⁴ ， YANG Ziao^1,2 ， SONG Fulin^1,2 ， WANG Yirui^1,2 ， CAO Jian^1,2

1. National Key Laboratory of Autonomous Marine Vehicle Technology (Harbin Engineering University), Harbin 150001 , China

2. College of Shipbuilding Engineering, Harbin Engineering University, Harbin 150001 , China

3. Nanhai Institute of Harbin Engineering University, Sanya 572024 , China

4. School of Instrumentation Science and Engineering, Harbin Institute of Technology, Harbin 150001 , China

摘要

为提升时空运动耦合约束的物流配送效率和灵活性，通过结合无人机高机动和无人车强运载能力，构建了异构空地协同智能物资配送系统。设计了一种多层级多尺度的多机物资配送轨迹规划方法(multi-layer multi-scale multi-robot transportation trajectory planning,M³TTP)，基于改进蚁群算法与概率路线图算法相结合，以优化多目标障碍约束下的旅行商问题轨迹求解结果，实现多尺度的分层任务分配决策规划。实验结果表明，考虑实际环境中空间障碍物和动态时序约束条件，通过改进的末端启发式算法构建邻接矩阵，可以实现小尺度的已知路网信息下求解最优配送路径。提出的异构协同任务作业时间同步机制，以Dubins算法将规划的轨迹均匀离散，提高了地空配送任务中多机协同效率。设计的M³TTP方法可以增强系统在时空运动耦合约束下的适应性和配送效率。

关键词

地空异构协同 / 智能运输配送 / 轨迹规划 / 多层级最优 / 时空运动耦合约束

Abstract

To enhance the efficiency and flexibility of logistics distribution under spatiotemporal motion coupling constraints, a heterogeneous aerial-ground collaborative intelligent transportation system is developed, which integrates the high mobility of unmanned aerial vehicles with the strong carrying capacity of unmanned ground vehicles. A multi-layer multi-scale multi-robot transportation trajectory planning (M³TTP) method is designed, which combines an improved ant colony optimization (ACO) algorithm with the probabilistic roadmap (PRM) algorithm. This method optimizes the trajectory solution for the traveling salesman problem (TSP) under multi-objective obstacle constraints, to achieve multi-scale hierarchical task allocation and decision planning.The simulation results demonstrate that, considering the real-world spatial obstacle and dynamic time sequence constraints, an adjacency matrix is constructed using an improved terminal heuristic algorithm. This enables the planning of an optimal transportation path based on detailed information from a small-scale and well-known road network.A time synchronization mechanism is proposed to address the challenges of heterogeneous collaborative path planning. The discrete Dubins path planning algorithm is presented to improve the efficiency of collaborative tasks. The proposed M³TTP method enhances both the adaptability and delivery efficiency of the system under spatiotemporal motion coupling constraints.

Keywords

ground-air heterogeneity coordination / intelligent transportation distribution / trajectory planning / optimal multi-layer / spatiotemporal motion coupling constraint

1 地空协同智能配送规划模型构建 1.1 异构多机器人配送任务最优分配 1.2 地空协同运动学约束 2 M³TTP轨迹规划算法框架 2.1 多层级聚类区域划分算法 2.1.1 多层级聚类区域划分算法 2.1.2 空间障碍约束下任务聚类重分配算法 2.2 复杂障碍环境多目标多机协同任务规划 2.2.1 无道路信息的改进蚁群全局避障规划算法 2.2.2 基于道路信息的宏微多尺度轨迹规划算法 3 仿真实验及分析 3.1 无道路信息的物资配送轨迹避障及求解收敛 3.2 基于道路信息的多无人机配送任务最优分配 4 结语

近年来，国家政策持续加码对低空经济产业支持，为该领域的发展注入了新的动力。物流配送的“最后一公里”是物流链条中的关键环节。针对智能化配送，结合多无人机与无人车构建异构地空协同无人配送系统，以应对不同客户需求的包裹配送问题。无人机和无人车凭借其高灵活性、低成本和可靠性，逐渐成为最后一公里配送的首选方案^[1-2]。

针对不同需求的包裹类型和配送环境，如何有效利用无人机进行高效配送，成为实现这一配送模式的关键^[3]。任新惠等^[4]将无人机与无人车空地异构配送问题分解为组合运行模式，综合考虑了无人系统续航、配送包裹数量等多目标约束，并转化为求解任务分配^[5]、旅行商（traveling salesman problem，TSP）^[6]，以及路径规划等问题^[7-9]。

地空协同多无人系统任务分配的目标是使无人车和无人机进行协同任务，确保无人车及多架无人机能够在最短时间内完成任务并到达任务目标点^[10-12]。Li等^[13]提出了一种基于博弈论的启发式编队方法，用于提升多无人机在离散资源约束下的任务分配效率。宋薇等^[14]提出了结合蚁群算法（ant colony optimization，ACO）和目标优化函数的多无人系统任务分配算法，可以有效提升医疗物资配送的效率。Fu等^[15]提出了一种复杂环境下的无人机任务分配方法，通过立体化分层聚类结合分层概率路线图方法（probabilistic roadmap，PRM）对任务区域进行有效分配，提升集群协同作业效率。在异构多无人系统协同配送中，物流路径优化问题通常可以抽象为TSP问题求解^[16]。然而，现有方法尽管能够在一定程度上实现多任务与多平台间的合理分配，但对于无人机与无人车本身的运动学与动力学约束考虑不足，进而可能导致任务分配与路径规划的整体效率下降。

在TSP映射方法下，高效求解是确保无人机能够准确完成物资投送的关键环节。蚁群算法作为经典的群体智能优化方法，求解多目标点最优覆盖的TSP问题具有良好效果^[17]。然而，在多目标、多无人系统协同任务的复杂场景下，问题可进一步分解为任务分配与覆盖路径的联合优化。针对传统蚁群算法收敛速度慢、易陷入局部最优的不足，有研究者提出基于跳点搜索的改进蚁群算法，以确保全局路径长度最优且提升了求解速度^[18]。但在立体化城市楼宇环境中，二维问题扩展至三维会使规划求解难度呈指数级增长，现有方法在大规模目标下的TSP序列求解仍存在协同效率低等问题，且考虑无人系统运动约束后，更增大了可行路径求解难度。因此研究更高效、更具适应性的地空协同规划方法是提高配送效率的必要途径。现有的协同规划方法，因启发式算法引入了轨迹求解的概率不确定性，对于具有任务时间最优、空间障碍约束及其自身的运动约束的多目标异构协同规划任务的稳定性无法保证。

鉴于此，根据无人机与无人车的特性，本文提出了异构多无人系统地空协同智能物资配送系统，构建多层级、多尺度的多机物资配送轨迹规划方法（multi-layer multi-scale multi-robot transportation trajectory planning，M³TTP），通过对区域的多层级划分，有效降低任务区域内的任务点数量，减小任务规模。考虑任务时间、空间障碍及无人系统运动约束，提高地空跨域无人物资配送的效率和环境适应性。该方法结合改进蚁群算法与PRM算法实现多尺度的分层任务分配决策，可优化障碍约束下大尺度多目标在TSP轨迹求解结果；结合末端启发式算法，实现路网信息已知的小尺度精确物资配送轨迹规划。在异构协同作业时间同步机制下，以Dubins算法将规划的轨迹均匀离散，提高地空配送任务协同时间率和配送效率。

1 地空协同智能配送规划模型构建

地空协同智能配送系统在每个特定区域内，采用一辆无人车搭载 N 架四旋翼无人机，结合无人车的大载量、长续航与无人机的高机动、立体化配送优势，实现空地协同立体化自主物资配送。考虑时空运动耦合约束，合理选定多层级区域划分，进而降低系统对单个机器人的性能要求，增强地空协同多机器人系统的空间运动能力和作业效率^[19-20]。本文构建了一种地空协同智能物资配送系统，如图 1 所示，其中 l_s 为无人机起飞的判定距离。

图1异构多无人系统地空协同智能物资配送

Fig.1Heterogeneous multi-unmanned vehicle ground-air cooperative intelligent material delivery

将地图分类为无道路信息的生活小区以及有道路信息的城市区域，在已知拓扑地图和先验栅格地图场景下，无人车根据区域层级划分到特定区域，完成整片区域对无人车的任务分配。该系统对空地协同配送问题的解决方案表示为

S^{*} = m i n (S_{1} + \sum_{m = 1}^{M} S_{2}^{k} (m))

(1)

式中：S₁为无人车路径规划的目标函数，

S_{2}^{k}

为无人机路径规划的目标函数，

S_{2}^{k}

（m）表示无人机在第k个无人车目标点附近的第m个配送点的目标函数，M为配送点附近的用户数量。

1.1 异构多机器人配送任务最优分配

为求解异构多机器人空地协同智能物资配送规划轨迹，通过将栅格地图或拓扑地图、多目标坐标信息、初始分类中心3个信息作为输入，进行复杂障碍环境下的多目标任务分配^[21-23]。针对多机器人的轨迹，最优任务分配的目标函数表述为：

\{\begin{matrix} S_{1} = \sum_{k = 1}^{K - 1} m i n ϖ (Z (k), Z (k + 1)) \\ S_{2}^{k} (m) = \sum_{j = 1}^{N_{t}} m i n ϖ (C_{k} (j), Z (k)) \end{matrix}

(2)

式中：K为无人车目标点数量；Z为所有聚类中心的坐标列表，Z（k）为Z中第k个点的坐标；为起点到终点求解避障距离的函数；N_t为当前无人机对应的目标任务点个数，j=1，2，3，···，N_t；C_k为第k个区域内的所有目标的坐标列表，C_k（j）为第j个点的坐标。

根据实际需求进行多次任务再分配迭代循环。当S₁与

S_{2}^{k}

收敛至一定范围，即多次实验结果相近，可认为获得了在给定约束与算法参数设置下的经验最优解。

1.2 地空协同运动学约束

由于道路和障碍物约束，异构多机器人不能简单地视为粒子模型。该系统的非线性动力学模型可以表示为：

[\begin{matrix} {\dot{x}}_{a} \\ {\dot{y}}_{a} \\ {\dot{z}}_{a} \\ {\dot{θ}}_{a} \\ {\dot{x}}_{v} \\ {\dot{y}}_{v} \\ {\dot{θ}}_{v} \end{matrix}] = [\begin{matrix} v_{a} \cdot c o s θ_{a} \\ v_{a} \cdot s i n θ_{a} \\ v_{z} \\ u_{1} v_{a} / r_{a} \\ v_{v} \cdot c o s θ_{v} \\ v_{v} \cdot s i n θ_{v} \\ u_{2} v_{v} / r_{v} \end{matrix}]

(3)

式中：

[x_{\sim} ， y_{\sim} ， z_{\sim} ， θ_{\sim}]

表示无人机与无人车的位置和航迹方位角，其中角标a和v分别表示关于无人机和无人车的变量；u₁和u₂是输入变量，-1≤u₁≤1，-1≤u₂≤1；v_a和v_v分别为无人机与无人车的水平速度，v_z为无人机垂直速度；r_a和r_v分别为无人机和无人车转弯半径。

多无人机配送任务分配的两个关键问题：立体化多点任务分配和多目标障碍环境下任务分配。要解决这两个问题，首先需要进行多机任务分配，获得地图及目标信息和建模，然后进行多目标任务分配，针对多目标障碍环境下的任务分配，设置避障路程新指标，对复杂任务进行分割，设计任务分配指标反馈。

2 M³TTP轨迹规划算法框架

为了提高异构多机器人空地协同智能物资配送的作业效率与准确性，构建了多层级多尺度的多机器人轨迹规划算法框架。该物资分配策略整体包含4个层级，第一层级为不同的市区，第二层级为在划分的市区中设置数目、位置均合理的物流集散点，第三层级为与各物流集散点联系的物流配送点，上述层级的划分可对无人车完成任务分配，第四层级为物流配送点向小区完成配送任务。若仅考虑欧氏距离情况下的物资发放，在各区选择一个地点作为物流集散点（二级）视为物流上游，分拣中心通过欧式距离直接以各配送点（三级）位置进行相连，视为物流中游。各个接收物资的小区为下游。然后通过蚁群算法求解以中游点为起点，到达下游并回到配送点的闭环序列。经过多层级划分，有效降低了每个任务区域内的任务规模，有效解决局部最优问题，通过TSP求解，得到最优序列。

2.1 多层级聚类区域划分算法

根据感知层建图方式得到目标区域地图，转化为栅格地图，根据需求得到多目标坐标信息，之后需要获得初始聚类中心，分层聚类求解表示为：

[C_{i}, C_{t}] = κ * (C_{o}, K_{i}, I)

(4)

式中：κ^*为以k-means聚类方法为初值的聚类函数，C_o为待聚类目标坐标，C_i为多目标任务分类序号，C_t为初始聚类中心，K_i为聚类个数，I为聚类迭代次数，所述聚类个数即为无人机的个数，即是最终任务分区的个数。

2.1.1 多层级聚类区域划分算法

聚类算法是一种常见的数据挖掘手段，其本质是将一组数据按照给定的标准划分成若干个簇，其中标准的设定取决于聚类的目的以及数据的类型。本文对集散中心以及配送点辐射区域划分进行研究。假设有一个样本集为

\{X^{(1)}, X^{(2)}, X^{(3)}, \dots, X^{(m)}\}

(5)

式中：

X^{（ i ）} \in R^{N} ， i = 1，2 ， \dots ， M_{\circ}

其中，核函数 Φ 从核函数映射关系 R ^N→R ^F 可得:

Φ (X^{(i)}, X^{(i)}) = {‖N (X^{(i)})‖}^{2} = N {(X^{(i)})}^{T} N (X^{(i)})

(6)

N（X^（ⁱ^））是Φ（X^（ⁱ^））的映射，任何一个点N（X^（ⁱ^））到类均值

m_{k}^{a}

距离为

\begin{matrix} d_{H} = ‖N (x) - m_{k}^{a}‖ = \\ \sqrt{{(N (x) - m_{k}^{a})}^{T} (N (x) - m_{k}^{a})} = \\ \sqrt{Φ (x, x) - \frac{2}{N_{k}} \sum_{j = 1}^{N_{k}} Φ (x_{j}, x_{j}) + \frac{1}{N_{k}^{2}} \sum_{j, p = 1}^{N_{k}} Φ (x_{j}, x_{p})} \end{matrix}

式中：

m_{k}^{a} = \frac{1}{N_{k}} \sum_{j = 1}^{N_{k}} N (x_{j}) ， k = 1，2 ， \dots ， K; K

为聚类数目; N_k为第K类聚类的样本数目；x_j和x_p则为第k类C_k的第j和p个样本。根据

m_{k}^{a}

可以求出K-means聚类算法目标函数V在三维空间的表达方程式为

V = \sum_{K = 1}^{k} \sum_{i = 1}^{N_{k}} {‖N (x) - m_{k}^{a}‖}^{2}

(7)

在原始三维空间中，样本点x_i与x_j之间的欧式距离可表示为

d (x_{i,}, x_{j}) = \sqrt{{(x_{i 1} - x_{j 1})}^{2} + {(x_{i 2} - x_{j 2})}^{2} + {(x_{i 3} - x_{j 3})}^{2}}

本文将三维空间中的样本压缩到二维平面，能够极大程度地降低样本处理的复杂程度，提高信息处理效率。考虑复杂障碍环境约束，构建集群任务分配的目标函数。通过对目标函数的最小值求解，实现最优任务重新分配。

2.1.2 空间障碍约束下任务聚类重分配算法

如图2所示，由于聚类中心实际会存在位于障碍或其障碍膨胀区域的场景，该情况会导致集群点到中心的避障路径无法求解。因此，寻找每个集群中目标任务点与分类中心欧式距离最近的点作为聚类重规划的备用中心点。如图2中绿色实线所示，如果分类中心出现在障碍物位置，则采用备用中心作为替代，若未出现在障碍物位置则继续使用该分类中心，再次执行聚类流程，进行任务再分配，如此循环完成任务最优分配。

图2任务分类效果图

Fig.2Task classification renderings

每获得一次备用中心点后，进行一次当前目标任务点的重新分配，并计算一次对应每台无人机的目标任务点与相应的备用中心点的避障距离总和，经迭代后，获得目标任务点针对无人机的最优任务分配。同时，将每类的各目标点到相应的中心的避障距离总和作为新的分类指标，从而获得复杂障碍环境下的任务分配新指标。

配送点数量的设置还与附近小区人口分布具有相关性，在配送点所供给的城区范围中去除居住规模极大的小区（小区人口数m＞配送点供给阈值T，已被单独分配n个配送点），对剩余小区进行聚类划分，获取最优配送点地理位置。根据配送策略，某SC_i供给范围内 j个小区的总人口

\sum_{j \in S C_{i}} m_{j}

所设配送点数目K_i应为：

K_{i} = \sum_{j \in S C_{i}} m_{j} / T

(8)

2.2 复杂障碍环境多目标多机协同任务规划

任务分配完成后，系统将会进行最优路径规划，准备开始配送。复杂障碍环境多目标多机协同任务规划的关键问题可拆分为多机协同任务规划及覆盖任务的最优求解。PRM算法具有障碍环境下避障路径寻优特性，而蚁群算法则可以在多目标TSP最优序列求解，通过将PRM和蚁群算法相结合，可以使算法在障碍环境下求解出最优避障轨迹。通过求解的TSP序列能够得到最优的投放点序列，每次提取两个相邻的序列点，完成单次配送，由于障碍物的阻碍，采用PRM算法进行两点之间的路径规划。通过提出的PRM-ACO算法求解出多机多目标覆盖轨迹。

2.2.1 无道路信息的改进蚁群全局避障规划算法

针对无道路信息的生活小区，根据获得的卫星地图能够获得可通行区域及用户位置信息。该环境下无人车的行进路线是不规则的。全局规划首先利用全局代价地图为无人车搜索一条无碰撞最短路径，并将其传递给局部轨迹规划模块。无人车通过蚁群算法求解小区内的最优配送序列，在该序列的基础上融合PRM算法实现二维轨迹避障与底层控制算法。

异构多机器人协同配送需要根据配送点位置进行路径规划，无人车对于配送点序列求解问题可以归结为求解TSP序列的问题。蚁群算法转移概率

P_{i j}^{k}

（t）可以表示为：

P_{i j}^{k} = \{\begin{array}{l} \frac{{[τ_{i j} (t)]}^{α} {[η_{i j} (t)]}^{β}}{\sum_{s \in J_{k} (i)} {[τ_{i j} (t)]}^{α} {[η_{i j} (t)]}^{β}}, j \in J_{k} (i) \\ 0, 其他 \end{array}

(9)

式中：τ_ij（t）为信息素浓度；α和β为调节因子，用于调节τ_ij（t）和η_ij之间的作用程度；j∈J_k（i）表示蚂蚁k下一步能够到达且没有选择过的节点集合，通过这种存储可以保证所有解的逻辑可行；η_ij通常取节点i到节点j之间距离的倒数，即η_ij=1/d_ij。物资配送中信息素更新规则如下：

τ_{i j} (t) = (1 - ρ) τ_{i j} + \sum_{k = 1}^{m} Δ τ_{i j}^{k}

(10)

Δ τ_{i j} = \sum_{k = 1}^{m} Δ τ_{i j}^{k}

(11)

式中:ρ（0＜ρ＜1）为路径上信息素的挥发系数；1-ρ为信息素的持久性系数；Δτ_ij（t）为本次迭代中节点i到节点j之间路径上信息素的增量；Δ

τ_{i j}^{k}

为第k只蚂蚁在本次迭代中留在节点i到节点j之间路径上的信息素量。若蚂蚁k未经过该段路径，则Δ

τ_{i j}^{k}

的值为零。Δ

τ_{i j}^{k}

表示为：

Δ τ_{i j} = \{\begin{matrix} \frac{Q}{L_{k}}, k \in i j \\ 0, 其 他 \end{matrix}

(12)

式中：Q为信息素强度常数，L_k为第k只蚂蚁本次迭代构建路径的总长度。根据蚁群算法得到的配送序列，提取出相邻两点，由于两点间存在楼宇等障碍物，对每次提取的配送点组进行避障路径规划。本文的避障方法均采用图搜索方法G=（V，E）。随机概率路线图（PRM）算法是一种经典的基于采样的路径规划方法。在全局大尺度的栅格地图场景下，避障过程中选用PRM算法。随机路标生成过程是通过将连续空间离散化，随机采样生成采样点，并剔除位于障碍物上的点，得到无碰撞点。以每个无碰撞点为中心，在一定半径范围内搜索其邻域点，并通过连线形成路径图网络。利用图搜索算法在构建的图中生成一条可行路径。最终根据TSP序列对多组PRM路径进行融合，进而获得全局避障路线。执行步骤如算法1所示。

需特别指出的是，本文所采用的M³TTP 框架下的改进ACO算法属于近似求解范畴，其理论上并不能对任意实例严格保证全局最优解。本文提出的 M³TTP 框架中，多层级聚类将全局任务空间划分为若干子区域，显著降低了单个子问题的规模，从而提高了ACO在每个子区域内的收敛速度与解的一致性。

M³TTP 框架下的改进蚁群算法：若设I为迭代次数，m为蚂蚁数，n为单次求解的目标点数，I与m为设定的常数，则其主循环的时间复杂度可近似表示为O（n²）；PRM路径规划：设采样点数为s，连边数量约为E，s为设定的常数，则构图与图搜索的复杂度约为O（E）。

2.2.2 基于道路信息的宏微多尺度轨迹规划算法

针对能够获得城市道路信息的区域，配送系统需根据道路信息进行路径规划。将不同道路相交的节点设置为参考点，此时对于输入的拓扑地图，构建不同区域内结合道路信息的节点距离邻接矩阵：

D = {[\begin{matrix} d_{11} & \dots & d_{N_{k}} \\ ⋮ & ⋱ & ⋮ \\ d_{N_{k} 1} & \dots & d_{N_{k} N_{k}} \end{matrix}]}_{N_{k} \times N_{k}}

(13)

约束于

d_{j i} = d_{i j} = Λ (c_{i} ， c_{j}) = \{\begin{matrix} {‖c_{i} - c_{j}‖}_{2} ， s_{o} = 1 \\ 0 ， s_{o} = 0 ， \\ \emptyset ， 其 他 \end{matrix}

式中：d_ji为道路节点i与j之间的距离，c_i为节点i的坐标信息；s_o=1表示i≠j且节点i与j存在直接相连道路；s_o=0表示i=j；N_k为该区域内的节点数量

通过结合无人机的高灵活性与无人车的大载重与长续航能力，实现了物流配送的高效性与智能化。提出的多层级聚类任务分配算法和结合蚁群算法与概率路图算法的轨迹规划方法，通过复杂环境中的路径优化实验得到验证。

3 仿真实验及分析

为实现地空协同智能物资配送，本文设计并实现了M³TTP算法。以长春市为例，基于对物流集散中心以及配送点辐射区域划分进行研究，提出配送方案。如图3所示，首先将长春市九个行政区划分作为整个城市物资配送的第一级划分标准，利用行政单位的管辖优势加快物流流通速度与投放效率。通过将分配策略分解为4个层级，第一层级为9个不同的市区，第二层级为在9区中设置数目、位置均合理的物流集散点，第三层级为与各物流集散点联系的物流配送点，第四层级为物流配送点向小区配送。

图3长春市的小区地理位置分布及拓扑地图可视化

Fig.3Geographical distribution and topological map visualization of residential areas in Changchun City

配送问题可按照所设计的分配策略，分城区进行规划，也即第二、三级划分均在各城区内部进行。无人车在到达配送点过程中，若与用户的距离达到l_s=25 m以内，无人机根据PRM算法驶向用户位置完成配送，再返回至无人车。

3.1 无道路信息的物资配送轨迹避障及求解收敛

依据长春市某区域的遥感影像，小区内有12个配送点坐标以及起点和终点两点坐标。采用蚁群算法在二维栅格地图环境下求解多目标TSP（旅行商问题）轨迹，并结合得到的配送序列与PRM（概率路标图）算法生成无人车在小区内的配送路径，如图4所示。每个配送点附近会存在1~3个用户等待配送，无人车在到达配送点后无人机起飞执行配送任务，于此同时无人车驶向下一个配送点。无人机完成一次配送任务后返回至无人车上方完成停靠，等待下一次配送。设定无人车最小转弯半径为1 m，无人机最小转弯半径为0.5 m。

图4中求解TSP得到的最优路径距离为1 216.79 m，图4（d）中，蓝色虚线代表TSP配送序列，红色实线为基于PRM算法求解的无人车实际配送路径，绿色实线则对应无人机的配送路径。作为经典的采样型路径规划方法，快速随机搜索树（rapidly-exploring random tree，RRT）能够作为对比基准算法。实验中橘黄色虚线为采用RRT^[24]算法得出的无人车配送路径。红色圆为无人车配送点，玫红色圆为用户位置，图4（e）和（f）分别展示了算法在地图边缘狭窄区域及宽阔区域的配送效果。通过与RRT算法对比，采用本文提出的M³TTP算法最终求解出无人车的路径长度为1 374.7 m，比RRT算法下的路径长度1 671.0 m减少了21.6%。

如图5所示，通过配送点[217.98，54.12] m附近的无人机配送情况，呈现了无人机与无人车配送过程中的三维空间关系；实时监测无人机与无人车之间的距离，以及配送过程中的协同率。仿真实验结果显示，在多数情况下，一台无人机即可完成配送任务，而在需要多台无人机协同完成任务场景下，本文提出的协同配送方法可以较好地提高协同率。

图4长春市某地配送效果及对比实验

Fig.4Delivery performance and comparative experiments in a specific area of Changchun City

图5无人机与无人车实时位置与距离

Fig.5Real-time location and distance between UAVs and unmanned vehicles

3.2 基于道路信息的多无人机配送任务最优分配

综合考虑物资供给效率与供给能力等实际情况，通过聚类分析后，第二级划分所获取各城区的集散点最优个数为6~9个，设定半径为SC_i=10 km，每个集散点附近的用户数量存在一个阈值，当半径SC_i≤10 km，且用户数量超出阈值时，会减小该二级划分区域的半径，直至用户数量小于阈值。图6（a）展示了第二级划分结果，最终集散点为6个。聚类后可获得集散点的最优位置及该集散点供给的最优小区范围。根据公式（8），图6（a）中‘★’为算法获取的最优集散点位置，红圈即为各集散点的最优管辖范围，红圈中散布的同色且同形状坐标点代表该集散点供给的小区分布，个别散落在红圈外，成为“飞地”，但它们仍接受集散点的物资供给。

如图6（b）所示，通过第三级划分获取各城区的物流配送点，供给城区中的各居民区，其划分对象为第二级划分得到的集散点所辐射的城区范围。

图6区3分拣中心集散点及配送点地理分布图

Fig.6Zone3 sorting center distribution point and delivery point geographical distribution map

配送点可以为其周围的多个小区同时提供物资供给任务，然而常规的聚类算法仅依据空间上的便利性（距离越近越优）划分聚类中心。这是由于在发放任务中仅考虑距离因素会造成某个配送点的供给任务超负荷（需要同时服务周围多个临近小区，服务总人数超载）。因此为每个小区设定一个配送阈值，当该小区的配送任务大于该阈值时，该小区会设置多个配送点。如图7所示，最后一层级为物资配送点向小区供给物资，以人力最优为指标，实现欧式距离最短，求解包括上游物资向中游物资流通的路径，以及中游物资向下游物资流通的路径。如图7所示，设定每块区域半径为3 km，其中绿色虚线为上游到下游的欧式直线距离。蓝圈所在范围为中游的覆盖区域，在该区域内的小区，需要进行最优覆盖，做到全面配送物资。

图7区8及区9上、中、下游物资配送有向图

Fig.7Zone8 and zone9 upper, middle and lower reaches of material distribution digraph

由于实际道路的限制，需考虑道路信息对物资配送的影响，通过上述的蚁群算法求解序列后，车辆从一个小区到另一个小区的过程中需要根据路网信息，以距离作为优化指标，求解规划信息。如图8所示，基于路网信息构建邻接矩阵，基于改进末端启发式算法求解出带有道路信息的路径，从而保证道路资源计算的更准确，实现资源的最大化调配。

图8改进末端启发式算法求解出带有路网信息的路径

Fig.8Path with road network information obtained by improved terminal heuristic algorithm

4 结语

为有效实现地空协同立体化大范围物资配送需求，本文提出了M³TTP方法，通过多层级聚类算法将配送区域进行层级划分，能够显著提升配送效率。根据地图信息类型，实现有路网信息的地图与无道路信息地图场景下协同规划。针对无道路信息地图，将改进ACO与PRM算法相结合，实现栅格地图环境下的配送TSP求解和避障轨迹规划；针对存在路网信息的区域，计算道路节点的邻接矩阵，结合末端启发式算法，实现小尺度场景下拓扑地图下的轨迹规划。在动态约束与复杂障碍环境下规划出安全高效的配送轨迹，实现了时空运动混合约束下的地空协同高效物资配送，提高了系统的效率和适应性。

图1异构多无人系统地空协同智能物资配送

Fig.1Heterogeneous multi-unmanned vehicle ground-air cooperative intelligent material delivery

下载: 全尺寸图片

图2任务分类效果图

Fig.2Task classification renderings

下载: 全尺寸图片

图3长春市的小区地理位置分布及拓扑地图可视化

Fig.3Geographical distribution and topological map visualization of residential areas in Changchun City

下载: 全尺寸图片

图4长春市某地配送效果及对比实验

Fig.4Delivery performance and comparative experiments in a specific area of Changchun City

下载: 全尺寸图片

图5无人机与无人车实时位置与距离

Fig.5Real-time location and distance between UAVs and unmanned vehicles

下载: 全尺寸图片

图6区3分拣中心集散点及配送点地理分布图

Fig.6Zone3 sorting center distribution point and delivery point geographical distribution map

下载: 全尺寸图片

图7区8及区9上、中、下游物资配送有向图

Fig.7Zone8 and zone9 upper, middle and lower reaches of material distribution digraph

下载: 全尺寸图片

图8改进末端启发式算法求解出带有路网信息的路径

Fig.8Path with road network information obtained by improved terminal heuristic algorithm

下载: 全尺寸图片

图1异构多无人系统地空协同智能物资配送

Fig.1Heterogeneous multi-unmanned vehicle ground-air cooperative intelligent material delivery

图2任务分类效果图

Fig.2Task classification renderings

图3长春市的小区地理位置分布及拓扑地图可视化

Fig.3Geographical distribution and topological map visualization of residential areas in Changchun City

图4长春市某地配送效果及对比实验

Fig.4Delivery performance and comparative experiments in a specific area of Changchun City

图5无人机与无人车实时位置与距离

Fig.5Real-time location and distance between UAVs and unmanned vehicles

图6区3分拣中心集散点及配送点地理分布图

Fig.6Zone3 sorting center distribution point and delivery point geographical distribution map

图7区8及区9上、中、下游物资配送有向图

Fig.7Zone8 and zone9 upper, middle and lower reaches of material distribution digraph

图8改进末端启发式算法求解出带有路网信息的路径

Fig.8Path with road network information obtained by improved terminal heuristic algorithm

图1异构多无人系统地空协同智能物资配送

Fig.1Heterogeneous multi-unmanned vehicle ground-air cooperative intelligent material delivery

图2任务分类效果图

Fig.2Task classification renderings

图3长春市的小区地理位置分布及拓扑地图可视化

Fig.3Geographical distribution and topological map visualization of residential areas in Changchun City

图4长春市某地配送效果及对比实验

Fig.4Delivery performance and comparative experiments in a specific area of Changchun City

图5无人机与无人车实时位置与距离

Fig.5Real-time location and distance between UAVs and unmanned vehicles

图6区3分拣中心集散点及配送点地理分布图

Fig.6Zone3 sorting center distribution point and delivery point geographical distribution map

图7区8及区9上、中、下游物资配送有向图

Fig.7Zone8 and zone9 upper, middle and lower reaches of material distribution digraph

图8改进末端启发式算法求解出带有路网信息的路径

Fig.8Path with road network information obtained by improved terminal heuristic algorithm

MENG Zhiyi, ZHOU Yuting, LI E Y,et al. Environmental and economic impacts of drone-assisted truck delivery under the carbon market price[J]. Journal of Cleaner Production,2023,401:136758. DOI:10.1016/j.jclepro.2023.136758

任璇, 黄辉, 于少伟, 等. 车辆与无人机组合配送研究综述[J]. 控制与决策,2021,36(10):2313. REN Xuan, HUANG Hui, YU Saowei,et al. Review on vehicle-UAV combined delivery problem[J]. Control and Decision,2021,36(10):2313. DOI:10.13195/j.kzyjc.2020.1315

WANG Xudong, LIU Zeyu, LI Xueping. Optimal delivery route planning for a fleet of heterogeneous drones: A rescheduling-based genetic algorithm approach[J]. Computers & Industrial Engineering,2023,179:109179. DOI:10.1016/j.cie.2023.109179

任新惠, 岳一笛, 尹晓丽, 等. 无人机车辆组合物流配送路径规划探讨[J]. 飞行力学,2020,38(2):88. REN Xinhui, YUE Yidi, YI Xiali,et al. Theoretical discussion on the logistics route planning problem of UAV and vehicle combination[J]. Flight Dynamics,2020,38(2):88. DOI:10.13645/j.cnki.f.d.20191115.003

GUO Bin, LIU Yan, WANG Leye,et al. Task allocation in spatial crowdsourcing: Current state and future directions[J]. IEEE Internet of Things Journal,2018,5(3):1749. DOI:10.1109/JIOT.2018.2815982

FU Jinyu, YAO Weiran, SUN Guanghui,et al. Multirobot cooperative path optimization approach for multiobjective coverage in a congestion risk environment[J]. IEEE Transactions on Systems, Man,and Cybernetics: Systems,2024,54(3):1816. DOI:10.1109/TSMC.2023.3329970

罗欣, 丁晓军. 地面移动作业机器人运动规划与控制研究综述[J]. 哈尔滨工业大学学报,2021,53(1):1.LUO Xin, DING Xiaojun. Research and prospective on motion planning and control of ground mobile manipulators[J]. Journal of Harbin Institute of Technology,2021,53(1):1. DOI:10.11918/201910067

FU Jinyu, YAO Weiran, SUN Guanghui,et al. Full coverage path planning recombination framework for unmanned vehicles with multi-objective constraints[J]. IEEE Transactions on Industrial Electronics,2024,71(8):9276. DOI:10.1109/TIE.2023.3319732

GUO Hongzhi, WANG Yutao, LIU Jiajia,et al. Multi-UAV cooperative task offloading and resource allocation in 5G advanced and beyond[J]. IEEE Transactions on Wireless Communications,2024,23(1):34. DOI:10.1109/TWC.2023.3277801

宗群, 王丹丹, 邵士凯, 等. 多无人机协同编队飞行控制研究现状及发展[J]. 哈尔滨工业大学学报,2017,49(3):1. ZONG Qun, WANG Dandan, SHAO Shikai,et al. Research status and development of multi UAV coordinated formation flight control[J]. Journal of Harbin Institute of Technology,2017,49(3):1. DOI:10.11918/j.issn.0367-6234.2017.03.001

WU Jiehong, ZHANG Jingchuan, SUN Ya′nan,et al. Multi-UAV collaborative dynamic task allocation method based on ISOM and attention mechanism[J]. IEEE Transactions on Vehicular Technology,2024,73(5):62255. DOI:10.1109/TVT.2023.3341878

FAIGL J, VÁNA P, DECKEROVÁJ. Fast heuristics for the 3-D multi-goal path planning based on the generalized traveling salesman problem with neighborhoods[J]. IEEE Robotics and Automation Letters,2019,4(3):2439. DOI:10.1109/LRA.2019.2900507

LI Yibing, ZHANG Zitang, HE Zongyu,et al. A Heuristic task allocation method based on overlapping coalition formation game for heterogeneous UAVs[J]. IEEE Internet of Things Journal,2024,11(17):28945. DOI:10.1109/JIOT.2024.3406336

宋薇, 高原, 沈林勇, 等. 一种基于近场子集划分的多机器人任务分配算法[J]. 机器人,2021,43(5):629. SONG Wei, GAO Yuan, SHEN Linyong,et al. A multi-robot task allocation algorithm based on near-field subset partition[J]. Robot,2021,43(5):629. DOI:10.13973/j.cnki.robot.200337

FU Jinyu, SUN Guanghui, LIU Jianxing,et al. On hierarchical multi-UAV dubins traveling salesman problem paths in a complex obstacle environment[J]. IEEE Transactions on Cybernetics,2024,54(1):123. DOI:10.1109/TCYB.2023.3265926

HU Linqiang, LEI Wanjun, Zhao Jiaqi,et al. Optimal weighting factor design of finite control set model predictive control based on multiobjective ant colony optimization[J]. IEEE Transactions on Industrial Electronics,2024,71(7):6918. DOI:10.1109/TIE.2023.3301534

WANG Xinyu, CHOI T M, LIU Haikuo,et al. Novel ant colony optimization methods for simplifying solution construction in vehicle routing problems[J]. IEEE Transactions on Intelligent Transportation Systems,2016,17(11):3132. DOI:10.1109/TITS.2016.2542264

马小陆, 梅宏. 基于JPS策略的ACS移动机器人全局路径规划[J]. 机器人,2020,42(4):494. MA Xiaolu, MEI Hong. The global path planning of ant colony system mobile robot based on jump point search strategy[J]. Robot,2020,42(4):494. DOI:10.13973/j.cnki.robot.190463

FU Jinyu, LI Ye, LIAO Yulei,et al. Mission-driven trajectory homotopy to explore dynamic coverage of USV-UAV system[J]. IEEE Transactions on Systems, Man,and Cybernetics: Systems,2025,55(12）:8877. DOI:10.1109/TSMC.2025.3613395

YANG Ziao, FU Jinyu, SUN Yushan,et al. A pseudo-trajectory homotopy method for UMVs information collection iot system with underwater communication constraint[J]. IEEE Internet of Things Journal,2025,12(20):43255. DOI:10.1109/JIOT.2025.3596338

WANG Shengli, LIU Youjiang, QIU Yongtao,et al. An efficient distributed task allocation method for maximizing task allocations of multirobot systems[J]. IEEE Transactions on Automation Science and Engineering,2024,21(3):3588. DOI:10.1109/TASE.2023.3281577

CHEN Yang, DING Yuemin, HU Zhenzhong,et al. Geometrized task scheduling and adaptive resource allocation for large-scale edge computing in smart cities[J]. IEEE Internet of Things Journal,2025,12(10):14398. DOI:10.1109/JIOT.2024.3525020

KANG Woosuk, JEONG Eunjin, SHIM Sungjin,et al. Optimization of task allocation for resource-constrained swarm robots[J]. IEEE Transactions on Automation Science and Engineering,2025,22:3068. DOI:10.1109/TASE.2024.3389013

UWACU D, YAMMANURU A, NALLAMOTU K,et al. HAS-RRT: RRT-based motion planning using topological guidance[J]. IEEE Robotics and Automation Letters,2025,10(6):6223. DOI:10.1109/LRA.2025.3560878

出版声明

期刊订阅

1 地空协同智能配送规划模型构建

2 M³TTP轨迹规划算法框架

3 仿真实验及分析

4 结语

出版声明

期刊订阅

1 地空协同智能配送规划模型构建

2 M3TTP轨迹规划算法框架

3 仿真实验及分析

4 结语

2 M³TTP轨迹规划算法框架