物流无人机城市低空轴辐式网络构建方法研究

曲欣宇 叶博嘉 程予 雷昌定

摘要：无人机在城市物流配送方面具有极大应用潜力，然而城市低空空域运行场景中的潜在不确定因素较多，亟待通过科学方法构建安全有序的物流无人机配送网络。从物流无人机运输经济性和运行安全性角度出发，结合物流无人机性能特征，在原有地面物流配送网点的基础上，构建多层级轴辐式网络的整数规划模型，提出了带距离限制的PAM（partitioning around medoids，围绕中心点划分）聚类与整数规划相结合的网络构建方法；从配送时效性、网络安全性和网络结构特征三方面选取评价指标，用于对比构建物流无人机运输网络与原地面运输网络；以南京市江宁区为例构建物流无人机配送网络，验证该网络构建方法的可行性。实验结果表明，该方法构建的无人机配送网络在兼顾运输成本与运输安全性的同时，还具有较好的配送时效性。

关键词：无人机；城市低空空域管理；物流配送；轴辐式运输网络；PAM聚类

中图分类号：U8   文献标志码：A   文章编号：1002-4026（2023）06-0086-10

The method to construct an urban logistics unmanned aerial vehicles

low-altitude hub-and-spoke network

QU Xinyu， YE Bojia*， CHENG Yu， LEI Changding

（College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，China）

Abstract∶Unmanned aerial vehicles （UAVs） have considerable application potential in urban logistics delivery. However， there are many uncertainties in urban low-altitude airspace operation scenarios. Therefore， it is essential to build a safe and orderly logistics UAV delivery network using scientific methods. From the perspectives of delivery economy， operational safety， and features of logistics UAVs， an integer programming model of multilevel hub-and-spoke network was constructed based on the original ground logistics delivery network. A network construction method was proposed， which combines partitioning around medoids（PAM） clustering with distance restrictions and integer programming. Three evaluation indicators were selected， i.e.， delivery timeliness， network security， and network structure characteristics， to compare the constructed logistics UAV delivery network with the original ground delivery network. A logistics UAV delivery network was constructed in Jiangning District of Nanjing city to verify the feasibility of the proposed network construction method. The experimental results show that the UAV delivery network constructed using this method has good delivery timeliness while taking delivery costs and safety into account.

Key words∶unmanned aerial vehicle; low altitude airspace anagement; logistics and distribution; hub-and-spoke network; partitioning around medoids clustering

隨着快递业务的迅猛发展，人们对快递配送速度提出了更高的要求。无人机快递配送不仅具有时效性强、成本低、可达性强的优点，还可有效减少快递配送过程中人与包裹的接触。美国亚马逊、德国敦豪、顺丰速运、京东等众多国内外企业均在进行物流无人机的研发和试运行。此外，美国联邦航空局、欧洲单一天空研究计划等已开展无人机城市交通项目研究［1］，中国民用航空局也先后发布文件针对城市物流无人机制定技术规范与航线标准，推动我国城市物流无人机宏观政策走向成熟。城市低空空域成为无人机应用的重要场景，无人机的安全高效运行受到各界广泛关注。

为保障城市低空空域内无人机有序运行，各国学者对物流无人机航路网络划设展开研究。Venkatesh等［2］在需求和旅行时间限制下，分别对有容量和无容量限制的情况采用混合整数规划方法进行机场选址；钱欣悦等［3］从配送效率出发，以最小化物流配送成本和最大化客户时间满意度为目标，建立物流无人机起降点选址分配模型；任新惠等［4］以步行距离最短为目标函数，以无人机机场的覆盖半径为约束构建基础线性规划模型；Chauhan等［5］考虑初始电池可用性和电池消耗的不确定性提出整数线性规划公式，并使用鲁棒优化最大化覆盖率；Feng等［6］从建设成本和运营成本的角度出发，考虑性能限制、空域限制和容量限制，建立了城市环境下物流无人机机场的选址模型；Li等［7］结合城市低空环境特点和物流无人机的操作局限性，提出了一种基于改进元胞自动机算法和最优生成树的航路网络规划方法；张洪海等［8］以总经济成本最小和客户满意度最高为目标，以禁飞区、无人机性能、容需匹配等为约束构建整数规划选址模型。目前这些研究多侧重于无人机起降点的选址布局，大部分选址问题研究中考虑的常规因素有物流无人机的运输需求、配送时间、配送距离、运输成本等，少部分研究将无人机覆盖半径、禁飞区考虑在内。但研究通常忽视航路网络的安全性，仅有少数学者在无人机路径规划时考虑了无人机与地面人员碰撞的风险［9-11］。此外，在物流无人机运输研究中缺少对配送节点等级划分和运输网络结构的研究。

本研究聚焦城市低空空域末端运输，在地面快递网点的基础上构建无人机快递运输网络。依据网点等级划分将网络构建问题分解为底层网点聚类和构建上层严格轴辐式网络模型；最后，以南京江宁某快递公司网点为例构建无人机快递运输网络，对比分析网络评价指标。研究为未来城市低空物流无人机配送网络的构建提供方法参考，推动城市物流无人机未来商用化的发展。

1 问题分析

目前无人机快递配送主要应用在区域枢纽机场到二、三线城市机场间的支线运输和二、三线城市机场到顾客的末端运输，物流企业可通过配置无人机起降平台、快递接驳柜等基础设施改造原地面快递网点。城市低空空域内建筑物、电磁信号等的干扰均会对物流无人机的运行带来阻碍，物流无人机的投入使用必将增加城市低空运行的复杂度。为保障未来城市低空空域内物流无人机的安全运行，避免物流无人机无序运行导致低空空域环境复杂、危害居民生命财产安全，需对物流无人机配送网络进行合理有序的规划。

1.1 网络结构选取

传统地面快递网络依靠一定的网络结构完成运输活动，网络中通常划分快递节点等级，包裹经各级节点层层分拣运输最终送达目的地。民航运输网络与地面运输网络常见的结构有全连通网络、轴辐式网络［12］。其中，全连通网络将网络中每两点都相连接，该网络中快递运输不存在中转，运输效率高但稳定性差，适用于货运量大且运输网点少的情况。物流无人机运输量达不到全联通网络的规模经济需求，因此全联通网络结构并不适合无人机运输时使用。而在轴辐式网络中，快件至少经一次中转到达目的地，其按非枢纽点间能否直接连接可进一步分类为严格和非严格轴辐式网络。严格轴辐式网络在快递运输中应用广泛，与现有快递运输模式适应、便于追踪快递信息。为适应具有分拣、转运等不同功能网点的运输，本文选择构建多层级严格轴辐式物流无人机运输网络。

多层级严格轴辐式网络中至少包含3类网络节点，如运作部、集配站、营业点。各层级网点与从上一级筛选出的枢纽点构成严格轴辐式网络，而筛选出的枢纽点又可进一步构建出更高一级的轴辐式网络，最终得到由多层级严格轴辐式航线网络组成的城市物流无人机网络，如图1所示。

1.2 无人机运行安全因素

研究主要从城市低空空域使用、无人机城市运行风险和物流无人机性能三方面考虑城市低空物流无人机的运行安全。

低空空域指真高1 000 m（含）以下区域，根据2022年中国民用航空局发布的《城市场景轻小型无人驾驶航空器物流航线划设规范》［13］，物流无人机航线应在高于高度零位面以上40 m并低于高度基准面以上120 m的空域范围内划设，航线高度可根据航空器性能和地形变化，物流无人机应在专为无人机划设的隔离空域内运行。虽然目前尚未有明确的物流无人机隔离空域划设规定，但为避免影响民航运输的运行安全，民航局规定无人机城市运行需在机场、临时起降点围界以及周边2 000 m外。因此，城市物流无人机网络构建时需首先确保在规定高度层内且不飞经城市中机场禁飞区和限高区。

城市运行风险方面，无人机运行风险可大致分为空中飞行碰撞与地面碰撞，由于城市物流无人机需在隔离空域运行，本研究忽略无人机在空中与民航飞行器的空中碰撞风险。中国民航局发布的《无人驾驶航空器飞行管理暂行条例》［14］综合考慮了无人机地面碰撞时可能引发的地面次生伤害、地面人员安全、地面设施安全以及可能引发碰撞的电磁环境等安全问题，规定了轻小型无人机在飞经卫星地面站、危险品存储区、活动现场等各类城市区域时应保持的飞行间隔。为综合考虑地面碰撞的所有可能风险，本文划设六类城市物流无人机运行风险区域。由于最小飞行距离与风险值为正相关关系，可体现无人机在飞经各类区域可能产生风险的程度，将轻小型无人机与不同风险区应保持的最小飞行距离作为该类区域的风险值，详细内容见表1。

在物流无人机性能方面，市面上现有的物流无人机实际运行时其飞行距离、载重、飞行转弯角等方面均有上限。因此，在构建网络时通常需考虑最大飞行距离、最大载重、最大转弯角等限制，超出限制外的飞行行为将影响无人机运行安全。本研究将无人机最大飞行距离、最大载荷重量作为网络构建的主要约束条件，而路径规划并非本文研究内容，因此对无人机最大转弯角等涉及路径规划的性能约束做简化处理。

2 网络构建方法

2.1 建立整数规划模型

以总配送成本和途径区域风险值最低为目标函数构建严格轴辐式网络模型，通过求解该模型可从上级网点中选出枢纽点以及各网点与上级枢纽点间的分配方式，自下而上在各层级网点构建轴辐式网络，最终得到由多层级严格轴辐式航线网络组成的城市物流无人机网络。

2.1.1 假设与符号说明

模型中符号的含义及其单位见表2。本文假设说明如下：

（1）枢纽点容量总能满足需求点需求；

（2）由枢纽点出发的无人机每次运输多个包裹，每次包裹总重量达到无人机最大载荷；

（3）不考虑无人机载重对运输能耗的影响；

（4）无人机运行中对航线高度上的建筑物等障碍物自主避障，绕飞程度以绕飞系数体现。

2.1.2 模型构建

min C=∑nk=1∑mi=1fαDidkiakixkibmax+∑mi=1Dih+pc，（1）

min E=∑oj=1∑nk=1∑mi=1rjekijakixki，（2）

s.t. ∑nk=1αkixki=1，（3）

∑nk=1yk=p，（4）

xki≤yk，（5）

akidkixki≤lmax，（6）

其中，公式（1）（2）为目标函数，即总配送成本最小和途径区域风险值最低，配送成本包含货物运输能源成本、运营成本和枢纽点建设成本，其中，运营成本包括在枢纽和需求点以及运输途中的管理费用。为减少无人机在城市空域运行的风险，无人机航线应尽量少地途径党政机关、电力设施、建筑物、公路等区域，即无人机应选择风险值较低的航线。公式（3）确保每个节点都与枢纽点相连接。公式（4）限制枢纽点数量。公式（5）保证与各节点相连接的为被选中的枢纽点。公式（6）保证无人机实际飞行距离在最大飞行距离内。

选择理想点法求解该多目标规划模型。分别以式（1）和式（2）为目标求解两个单目标模型，分别得到目标函数值C*、E*。再以式（7）为目标，将多目标规划转化为单目标规划，求得距离两理想点最近的解。

min F=（C*－CC*）2+（E*－EE*）2。（7）

2.2 底层网点聚类

在运输网络中各层级备选网点的数量逐级递增，底层网点多且分布范围广，不宜将所有底层网点纳入同一严格轴辐式网络。考虑到无人机最大飞行距离限制，采用基于距离划分的PAM（partitioning around medoids，围绕中心点划分）聚类算法，并将最大飞行距离作为约束加入，将底层网点分为多个簇。带距离约束的PAM算法克服了k均值聚类算法（k-means）的缺陷，通过计算每簇中除聚类中心外的各点到其他所有点的距离的最小值修正聚类中心，同时还能够筛除无人机最大飞行范围外的样本点，从样本点中选取聚类中心。带距离约束的PAM聚类算法步骤如下：

步驟1 从n个样本点中随机选取k个初始聚类中心；

步骤2 计算剩余点到聚类中心的距离，将样本点归入无人机最大飞行距离内且距离最近的聚类中心，若存在样本点的无人机最大飞行距离内无初始聚类中心，则重复步骤1至每个非聚类中心的样本点均与最大飞行距离内的聚类中心相匹配；

步骤3 计算所有样本点与其聚类中心点的距离值，距离值累加得到损失值c0；

步骤4 选择一个非中心样本点替换聚类中心，重新计算损失值，若新的损失值小于c0，则将c0更新为新损失值，并将该非中心样本点作为新的聚类中心；

步骤5 检验新聚类结果各簇中样本点至聚类中心的距离，若存在簇内距离超过无人机最大飞行距离的样本点，则抛弃该聚类结果；

步骤6 重复步骤4、步骤5，直至聚类中心不再改变。

除了确定聚类中心的位置外，还需要确定聚类中心的数量，文中聚类簇数将通过轮廓系数确定。需要注意的是，将样本点分为较少的簇时，由于在PAM聚类算法中加入了距离约束，聚类结果可能因距离约束被否定，在遍历不同的聚类簇数时可能会出现部分簇数情况的缺失。此外，为确保生成的各簇内样本点间能够构建严格轴辐式网络，还需排除聚类结果中单个样本点成为一簇的情况。因此，聚类簇数的选择将在排除以上两种情况后，选取具有轮廓系数最大值的簇数作为最终的聚类簇数。

3 算例分析

3.1 现状分析

在南京江宁区内以快递网点类型较全面且数量较多的快递公司为例，共搜索到快递中转场、集散中心、集配站和营业点4类共55处网点。假定原有地面配送网络中各网点均由距离最近的上一级网点配送，以直线连接的方式表示该快递目前各级网点的分布情况，如图2所示。

经观察分析，该快递现有地面快递配送网络存在超过物流无人机最大飞行距离的路径。从大疆GEO（geospatial environment online，地理空间环境）系统中获取南京禄口国际机场禁飞区与限高区，部分网点处在南京禄口机场禁飞区和限高区内。因此，不能直接以现有地面配送网络作为无人机配送网络，需要筛选网点并构建适合物流无人机运行的快递配送网络。

3.2 参数设置

拟使用市面上主流物流企业研发的物流无人机Ark方舟进行集配站到营业点枢纽的中短距离运输，该机型最大载荷重量为12 kg，最大航程为20 km；营业点枢纽到营业点的短距离运输由H4四旋翼无人机负责，该飞行器最大载荷重量为10 kg，最大航程为15 km。假设各营业点每日无人机快递运输需求为20 kg，其他参数假设见表3。

3.3 网络构建

去除无人机禁飞区和限高区内的网点，在剩余43处营业点、4处集配站和1处集散中心的基础上构建江宁区物流无人机运输网络。PAM聚类算法对43处营业点进行聚类，以H4四旋翼无人机最大航程15 km为距离约束。对营业点层级网点聚类，遍历不同簇数量并计算轮廓系数，得到的轮廓系数折线图如图3（a）所示。当簇数量超过7时，出现单个网点为一簇的情况，此时该簇无法构成轴辐式网络，因此不考虑簇数量超过7的聚类情况。而在此之前的轮廓系数随簇数量的增加而变大，选取最大轮廓系数所对应的簇数，将营业点聚为7类，聚类结果如图3（b）所示。

将各聚类中心作为枢纽点，分别构建如图4（a）所示的7个单枢纽严格轴辐式网络。按照表1中的分类标准统计江宁区的各类风险区域，无人机最大航程lmax=20 km带入式（6），求解前文建立的多目标规划模型。从集配站级网点中选择东善桥集配站和淳化集配站作为7个营业点聚类中心的枢纽点；进一步以中科路集散中心为两集配站的枢纽点，构建如图4（b）所示的由三级严格轴辐式网络组成的江宁区城市物流无人机配送网络。

3.4 无人机配送网络评价指标

3.4.1 指标选取

参考快递运输网络和航线网络评价指标并考虑无人机运行安全性，分别从配送时效性、网络安全性、网络结构特征等3方面对物流无人机快递配送网络进行评价。

（1）配送时效性

平均路径长度是网络中所有节点间最短路径的平均值，用于衡量网络的传输性能和效率，计算公式：

d=∑i≠j∈Vdij/nn－1，（8）

式中，n为网络中节点数量，dij为网络中任意两节点间距离。

（2）网络安全性

网络安全性由网络中各条航线风险值的平均值的倒数表示（为方便在雷达图中比较，将倒数乘以100以扩大数量级），计算公式：

θ=1（E/u）×100，（9）

式中，u为网络中边的数量。

（3）网络结构特征

节点的中心度指标包含点度中心度、接近中心度与中介中心度，分别反映节点i在整体网络中的核心程度、与其他节点间的紧密程度以及衔接程度，数学表达式分别为式（10）～（12）。其中，ui为与节点i相连的边的数量，dij为i、j两点间最短路径长度，gjk为网络中两点间最短路径总数，gjk（i）为经过节点i的最短路径，均可由Dijkstra算法计算得出。

网络整体结构则选取平均点度中心性CRD、平均接近中心性CRP、平均中介中心性CRB与点度中心势CD、接近中心势CP、中介中心势评价CB，数学表达式分别为式（13）～（18）［16］。其中，CDmax、CPmax、CBmax为网络中相应类别的最大中心度值。

CD（i）=ui/（n－1），（10）

CP（i）=（n－1）/∑jdij，（11）

CB（i）=∑j≠k≠igjk（i）/gjk2（n－1）（n－2），（12）

CRD=∑iCD（i）/n，（13）

CRP=∑iCP（i）/n，（14）

CRB=∑iCB（i）/n，（15）

CD=∑i（CDmax－CD（i））/n－2，（16）

CP=∑i（CPmax－CP（i））/n－1，（17）

CB=2n－3∑i（CBmax－CB（i））n－2n－1。（18）

3.4.2 评价分析

将去除了禁飞区内网点的江宁区某快递公司原地面配送网络网点及运输模式称为原配送网络，实验中构建的无人机配送网络为新建配送网络，均以无人机作为运输工具进行配送，两网络中各项指标计算结果见表3，并结合图5中各指标雷达图进行对比分析。

对比新建配送网络与原配送网络，新建配送网络在运输时效性与运输安全性方面均呈现更优表现，尤其在安全性方面得到显著提高。网络结构方面，新建配送网络平均点度中心性与平均接近中心性均高于原配送网络，即网络中各节点的连接更紧密，节点之间能更加快速地到达，相应的网络运输效率更高；多层级的严格轴辐式网络结构使得新建配送网络具有较高的平均中介中心性，网络中各节点在其他点之间调节能力和控制能力较强；此外，新建配送网络的点度中心势与中介中心势较低，表明相比于原配送网络，新建配送网络中各点的中心度分布较均衡，且节点对枢纽依赖性较低，网络鲁棒性较好。

4 结语

為适应现有物流运输模式、保障城市低空空域无人机安全有序运行，选择多层级的严格轴辐式网络结构，采用带距离约束的PAM聚类和以运输成本与运输风险为目标的整数规划模型，对地面快递网点进行枢纽点的选址和轴辐式网络的构建。以南京市江宁区某快递公司为例构建无人机快递运输网络，对比分析网络评价指标，发现所构建的无人机运输网络在兼顾运行成本与运行安全性的同时，相比于原配送网络在网络配送时效性方面也得到了提高。

研究中有以下几个方面可在未来进行深入研究：第一，由于研究中仅考虑了无人机最大运输距离、最大载荷等性能约束，所构建的物流无人机轴辐式网络仅为二维运输网络，在后续研究中可考虑无人机飞行高度等约束，构建由飞行路径所组成的三维城市物流无人机运输网络；第二，在构建的网络中以直线作为航线表示网点间分配关系，并未对障碍物避障、转弯角等做详细规划，可在选址问题后衔接路径规划，进一步研究城市物流无人机的选址、路径优化问题。

参考文献：

［1］姚虹翔， 叶博嘉， 程予. 低空无人机空中交通管理研究［J］. 科技创新与应用， 2021， 11（25）： 183-187.

［2］VENKATESH N， PAYAN A， JUSTIN C Y， et al. Optimal siting of sub-urban air mobility （sUAM） ground architectures using network flow formulation［C］//American Institute of Aeronautics and Astronautic，Aviation 2020 Forum. Reston， USA： AIAA. 2020： 2921.DOI： 10.2514/6.2020-2921.

［3］钱欣悦， 张洪海， 张芳， 等. 末端配送物流无人机起降点选址分配问题研究［J］. 武汉理工大学学报（交通科学与工程版）， 2021， 45（4）： 682-687. DOI： 10.3963/j.issn.2095-3844.2021.04.013.

［4］任新惠， 王柳. 即时配送下无人机全自动机场分区选址模型［J］. 计算机工程与应用， 2021， 57（10）： 266-272. DOI： 10.3778/j.issn.1002-8331.2003-0433.

［5］CHAUHAN DARSHAN R， AVINASHU， MIGUELF， et al. Robust maximum coverage facility location problem with drones considering uncertainties in battery availability and consumption［J］. Transportation Research Record， 2021， 2675（2）： 25-39.

［6］FENG D K， ZHANG HH， LIU H， et al. Research on location of logistics UAV airport in urban environment［C］// 6th International Conference on Information Science， Computer Technology and Transportation. Xishuangbanna， China： VDE， 2022： 1-5.

［7］LI S， ZHANG HH， LI Z L， et al. An air route network planning model of logistics UAV terminal distribution in urban low altitude airspace［J］. Sustainability， 2021， 13（23）： 13079. DOI： 10.3390/su132313079.

［8］張洪海， 冯棣坤， 张晓玮， 等. 城市物流无人机起降点布局规划研究［J］. 交通运输系统工程与信息， 2022， 22（3）： 207-214. DOI： 10.16097/j.cnki.1009-6744.2022.03.023.

［9］ZHANG X J， LIU Y， ZHANG Y， et al. Safety assessment and risk estimation for unmanned aerial vehicles operating in national airspace system［J］. Journal of Advanced Transportation， 2018， 2018（Pt.6）：4731585. DOI： 10.1155/2018/4731585.

［10］胡莘婷， 戴福青. 基于城区行人安全的无人机运行风险评估［J］. 中国安全科学学报， 2020， 30（8）： 137-142. DOI： 10.16265/j.cnki.issn1003-3033.2020.08.020.

［11］钟罡， 励瑾， 张晓玮， 等. 物流无人机对地风险评估方法研究［J］. 交通运输系统工程与信息，2022，22（4）： 246-254. DOI：10.16097/j.cnki.1009-6744.2022.04.028.

［12］李鹏飞， 彪蔚然. 快递网络结构研究进展［J］. 西安邮电大学学报， 2020， 25（1）： 34-41. DOI： 10.13682/j.issn.2095-6533.2020.01.004.

［13］中国民用航空局空管行业管理办公室.城市场景轻小型无人驾驶航空器物流航线划设规范： MH/T 4054-2022［S］.北京： 中国民航出版社， 2022.

［14］中国民用航空局. 无人驾驶航空器飞行管理暂行条例［EB/OL］.［2023-01-17］.https：//www.gov.cn/zhengce/content/202306/content_6888799.htm.

［15］中通研究院. “末端+支线”无人机运营场景成本分析［EB/OL］.［2023-01-16］.http：//hkjjyjzx.zua.edu.cn/info/1066/1264.htm.

［16］陈欣， 李心茹， 盛寅. 基于复杂网络的长三角航线网络结构特征分析［J］. 交通信息与安全， 2020， 38（4）： 139-146. DOI： 10.3963/j.jssn.1674-4861.2020.04.017.