基于无人机的高层住宅最后“一百米”配送优化

蒋丽，杨露，梁昌勇，董骏峰

（合肥工业大学，管理学院，合肥 230009）

0 引言

随着新冠疫情常态化，“无接触式”上门配送服务常态化提上日程，以无人机、无人机车为代表的配送工具出现在大众视野。无人机凭借低空飞行、高灵活性等优势获得广泛关注，亚马逊、UPS、京东等国内外电商、物流公司纷纷开展无人机在末端配送方面的研究，为无人机上门配送服务提供技术支持。

国内外学者也开始研究无人机末端配送模式，主要集中在无人机“最后一公里”配送的路径优化问题，可以分为两类。一类是单独使用无人机配送，例如在“最后一公里”场景下，郭兴海等[1]建立了配送过程中无人机任务重新分配、路径重新规划的目标函数模型。张洪海等[2]使用栅格法对无人机飞行环境进行建模，建立城市区域多约束物流无人机路径规划模型。郭兴海等[1]、张洪海等[2]都未考虑无人机载重量对无人机飞行能力的影响。Dorling等[3]证明无人机有效载重量与能源消耗之间的线性关系，提出MTVRP（Multi- trip Vehicle Routing Problem）思 想 下 的 DDPs（Drone Delivery Problems）。Cheng 等[4]在Dorling 等[3]的基础上，进一步考虑无人机有效载重量与能源消耗的关系，提出多行程无人机路径问题MTDRP。Dorling 等[3]、Cheng 等[4]都以无人机的车辆数作为目标函数，本文以高层住宅垂直平面为配送区域，以单台无人机的重复利用完成所有配送任务。任新惠等[5]为了使无人机的路径规划更贴合实际情况，提出考虑能耗分段的无人机调度模型，却仅以飞行距离最小化为目标函数。

另一类是无人机与卡车联合配送，Murray 等[6]针对无人机载重量小、飞行时间短等劣势提出无人机与卡车联合配送模式，率先建立了卡车和无人机联合配送的FSTSP （Flying Sidekick Traveling Salesman Problem）模型。Ha 等[7]在FSTSP 基础上提出TSP-D （Traveling Salesman Problem with Drone）的MILP 模型，Tu 等[8]将TSP-D 扩展为TSPmD，即货车搭载多台无人机的情形。Wang 等[9]进一步提出城市物流中的VRP-D。TSP-D、TSP-mD、VRP-D 等都是无人机联合卡车参与“最后一公里”配送的典型变体，但未考虑顾客对上门配送服务的需求。Poikonen 等[10]认为无人机在满足能耗约束的情况下一次飞行可以服务多个顾客，并考虑无人机有效载重量与能源消耗的关系。本文想法与Poikonen等[10]有许多相似之处，都是假定无人机一次飞行可服务多个顾客，将无人机有效载重量与能源消耗关系引入到模型中，不同之处在于，Poikonen 等[10]考虑了无人机在“最后一公里”与卡车的联合配送，而本文聚焦于高层住宅顾客上门配送这一场景，考虑无人机在“垂直位置最后一百米”的配送。

综上，现有研究聚焦于如何使无人机更好的在“最后一公里”配送中发挥作用，并未考虑城市中包裹送货上门的“最后一百米”。为此，本文提出高层住宅无人机上门配送问题（High-rise Residential Drone Door-to-door Distribution Problem，HRRDDTDP），针对城市高层住宅顾客对上门配送服务的需求，结合张坤等[11]设计的高层住宅无人机智能快递接收平台，建立以无人机容量、电池组容量等为约束的MILP 模型，由无人机完成“垂直位置”顾客的上门配送服务。基于HRR-DDTDP模型特点，引入4个局部搜索算子，设计带VND的混合蚁群算法（Hybrid Ant Colony Optimization with Variable Neighborhood Descent,HACO-VND）求解该模型，并通过实验证实HACO-VDN算法的有效性和可行性。

1 高层住宅无人机上门配送

1.1 问题描述

针对城市高层住宅顾客上门配送需求，在每户安装无人机停放平台[11]的条件下，用一台无人机完成一栋高层住宅所有上门配送任务，无人机可重复利用，图1 为由9 个顾客点组成的HRR-DDTDP 最优路线示例图。无人机具体配送过程如图2所示，无人机携带不同重量的包裹从高层住宅楼的单元门（简称“始发点”，如图1中始发点位置）出发，当无人机到达顾客所在住宅楼层的具体“垂直”位置时，发送信号到该顾客的无人机停放平台，无人机停放平台滑出，无人机包裹投放完毕后发送信号到停放平台使其收回室内，无人机进行下一个包裹的配送或回到始发点，若有未配送的包裹，回到始发点的无人机则更换电池开始新一轮的配送，直到所有顾客的包裹送达。

图1 HRR-DDTDP示例图Fig.1 Example diagram of HRR-DDTDP

图2 高层住宅无人机上门配送过程Fig.2 Door to door distribution process of drone in high-rise residence

无人机每次飞行必须满足最大载重量以及最大能耗约束，即无人机容量、电池组容量约束。根据Dorling等[3]的研究，无人机在悬停、水平飞行、改变飞行高度时的做功大致相等，同时证明多旋翼无人机能源消耗与载重量之间的线性关系为

式中：m为无人机负载重量；mbattery为电池重量之和；α为无人机每千克载重量的功率消耗；βframe为无人机保持机身在空中飞行时的功率消耗，其中，battery、frame分别代表电池、无人机机身。

本文不考虑电池能源消耗对电池重量的微弱影响，将无人机电池重量看做机身重量，式（1）变为

令β=αmbattery+βbattery，得到

此外，由于无人机在不同路段的包裹总重量不同，故不同路段的能源消耗量是不同的[5]。

基于上述问题，本文假设如下：

（1）对于目标函数，只考虑与无人机相关的成本，如单次飞行成本、能源消耗成本，不考虑人工及其他成本；

（2）只考虑无人机的载重量、能耗限制，不考虑包裹体积，并忽略天气对无人机电池续航能力的影响（风、温度等）；

（3）无人机采用换电池的方式，不考虑在始发点换电池、装载包裹的时间；

（4）始发点无人机电池数量储备充足，无人机每次离开始发点时的电池满电，累计能源消耗为0；

（5）顾客点位置与需求已知，顾客点需求不大于无人机的最大载重，不考虑顾客点时间窗，每个顾客点必须且仅被无人机服务一次；

（6）无人机在每位顾客点的服务时间相同，无人机在服务时间内的能耗计算与飞行时能耗计算相同；

（7）无人机配送时飞行速度恒定不变，采用曼哈顿距离，每次飞行可以服务多个顾客。

1.2 符号表示

根据问题描述，模型符号定义及解释如表1所示。

表1 模型符号定义及解释Table 1 Definition and interpretation of model symbols

1.3 模型

根据问题描述，建立高层住宅无人机上门配送问题的MILP模型为

目标函数式（4）为最小化无人机飞行成本和能源消耗成本。式（5）～式（9）对配送路径进行约束：式（5）和式（6）确保每个顾客点都能得到无人机服务且只能被无人机服务一次；式（7）确保到达顾客点j的无人机一定飞出；式（8）确保无人机从始发点飞出的次数与回到始发点的次数相同；式（9）表示无人机不在同一顾客点打转。式（10）～式（12）对载重量进行约束：式（10）确保无人机离开某一顾客点时携带的包裹总重量小于到达该顾客点时的载重量，且差值为该顾客点的包裹重量；式（11）表示无人机的载重量不能超过无人机的最大载重量；式（12）表示无人机完成一次飞行后飞回始发点时的载重量，即包裹重量为0。式（13）～式（17）对能耗进行约束（能耗与载重量的关系、能耗分段等）：式（13）表示无人机在路径（i,j）上的功率与无人机在该路径上的载重量成正线性关系；式（14）表示从始发点出发直接服务某顾客点的无人机在离开该顾客点时的累计能耗等于无人机离开始发点的累计能耗和功率与时间乘积之和；同理，式（15）和式（16）分别表示从顾客点出发直接服务其他顾客点、从顾客点直接飞回始发点的无人机能耗约束；式（17）确保无人机的每次飞行都不超出无人机的最大能耗。式（18）～式（20）说明变量的类型和允许范围。

2 算法设计

当无人机的容量和电池组容量无限制时，HRR-DDTDP 就转化为旅行商（TSP）问题，众所周知TSP 问题为NP 难问题，所以本文提出的HRRDDTDP也为NP难问题。

蚁群算法对于求解TSP这类NP难问题具有较好的效果，但蚁群算法收敛速度慢，易陷入局部最优等缺点使得其在求解大规模问题时的求解效果差。为此，本文根据HRR-DDTDP模型解的特点引入4个局部搜索算子，并依据顾客数量选择不同的局部搜索算子组合，进一步提高算法求解性能，设计出带VND的混合蚁群算法（HACO-VND）。

2.1 局部搜索算子组合策略

基于无人机每次飞行服务顾客数少的这一特点，设计4个局部搜索算子，弥补蚁群算法（ACO）收敛速度慢且易陷入局部最优的不足。在蚁群算法中增加VND能够克服ACO的缺点，但也会导致算法求解时间随顾客点数量呈指数倍增加，为兼顾算法的有效性、求解时间，本文在局部搜索阶段设计了两种不同的算子组合：combination2、combination3，其中combination2包含Q3、Q4算子，combination3包含Q1、Q2、Q3算子。根据顾客数量选择不同的算子组合，并将顾客数量判断条件放在算法进入循环之前，以缩短求解时间。

（1）不同无人机路径之间顾客点的插入——Q1

基本原理：从任意两条无人机路径中的一者中随即选择一点即顾客点，将其依次放入另一条无人机路径中的任意位置，若得到的新解优于原先解，则替换原先解；否则，原先解保持不变。

该算子有两种情况：（a）两条无人机路径都有两个及以上顾客点，如图3（a）所示；（b）待移除顾客点的无人机路径只有一个顾客点，待插入顾客点的无人机路径有一个及以上顾客点，如图3（b）所示。

图3 Q1 算子Fig.3 Q1 operator

（2）不同无人机路径之间顾客点的交换——Q2

基本原理：选择两条无人机路径，分别从无人机路径中选择一点即顾客点，放入到对方原来所在路径的位置中，若得到的新解优于原先解则替换原先的解，否则原先解保持不变，如图4 所示。在此算子中，所有无人机路径的组合都尝试一遍。

图4 Q2、Q3 算子Fig.4 Q2,Q3 operator

（3）不同无人机路径之间顾客点的交换——Q3

基本原理与Q2算子相同，如图4所示。不同的是，Q3算子中该操作重复Nvnum（无人机飞行次数）次。

（4）某一无人机路径顾客点的重新插入——Q4

基本原理：将无人机路径中的某一点重新放入路径中，路径中的每一个顾客点在每一个位置都尝试一次，观察所得到的新解是否优于原先的解，若是则替换，否则保持不变，如图5所示。

图5 Q4 算子Fig.5 Q4 operator

2.2 HACO-VND算法步骤

Step 1 初始化蚂蚁种群及参数，如蚂蚁数量m、路径表、信息素表等，初始信息素为到达点的包裹重量，到始发点的信息素值定义为足够小的正数。

Step 2 判断顾客数量Nnumcom，若Nnumcom＜40，则进行步骤Step 3、Step 4、Step 6；否则进行步骤Step 3、Step 5、Step 6。

Step 3 为每只蚂蚁随机选择初始位置，并选择下一个位置，当所有蚂蚁位置选择完毕时，将所有蚂蚁按照成本值升序排列，只对成本值小的前m2 只蚂蚁进行局部搜索。

Step 4 前m2 只蚂蚁依次经过combination3中的Q1、Q2、Q4算子，即前一个算子优化后的解是后一个算子的初始解。结束局部搜索操作并更新信息素，转到Step 6。

Step 5 前m2 只蚂蚁依次经过combination2中的Q3、Q4算子。结束局部搜索操作并更新信息素，转到Step 6。

Step 6 在所有m只蚂蚁中找出此次迭代的最优解以及最优配送方案，并与上一代进行对比，得到目前为止各代的最优解及最优配送方案；初始化蚂蚁种群及参数，迭代次数加一，若迭代次数Niter＞100，则输出目前的最优解及最优配送方案，否则转到Step 3。

3 算例分析

本文实验是在Intel（R）Core（TM）i5-9400 CPU@2.90 GHz的CPU，内存8.00 GB的个人电脑上进行。算法采用MATLAB2016a编写并运行，取运行10 次的平均结果；CPLEX 12.6.3 求解MILP 模型，取运行时间不超过3600 s的结果。

3.1 数据获取

本文提出的高层住宅上门配送问题没有标准的实例集，需自行生成数据。数据生成过程如下。

（1）顾客点需求量——包裹重量（kg）

假设无人机上门配送的包裹物品仅限于服装，整栋高层住宅住户的包裹重量服从正态分布，即N（0.5,0.2）。

（2）顾客点“垂直”坐标

假设高层住宅楼每层4户居民，每层楼高3 m，每户户型为10 m×10 m，高层住宅楼层数Nnumfloor有10，20，30，40，50 层等，分别用A、B、C、D、E 表示，从每栋高层住宅中随机选取顾客点，图6是规格为A（10 层）的高层住宅示例图。由于同一栋楼所有居户在同一天都有包裹需要配送的概率非常小，所以设每栋高层住宅楼一天内需要配送的顾客数量Nnumcom不超过整栋居民楼住户的75%，即

图6 10层高层住宅示例图Fig.6 Example drawing of 10 storeys high-rise residence

（3）无人机参数取值

假设一架无人机3000元，可飞行6000次；无人机电池组600元，电池的循环次数为300次；一度电费大约1 元；其他相关参数参考Dorling 等[3]。无人机参数取值如表2所示。

表2 无人机参数取值Table 2 Drone parameter value

3.2 对比分析

通过大量的前期工作以及尝试，首先确定了两种算法：含有Q3、Q4两个算子的HACO-2VND 算法；含有Q1、Q2、Q4这3 个算子的HACO-3VND算法。

两种算法在不同算例下的求解结果如表3 所示。（1）HACO-3VND 求解结果优秀，求解时间却成倍增加；（2）HACO-2VND 的解虽然不如HACO-3VND的解好，但相差不大，而且求解时间短很多，当顾客点数为40 时，其求解时间就仅为HACO-3VND 求解时间的1/2。最后，综合HACO-3VND和HACO-2VND 的表现，本文提出HACO-VND 算法，将两种算法相互补充。

表3 HACO-2VND、HACO-3VND、HACO-VND求解结果Table 3 Solution results of HACO-2VND,ACO-3VND and HACO-VND

为验证HACO-VND算法的有效性，以CPLEX结果为对比，得到不同算例下的GAP 值，如表4 所示。对不同的Nnumcom进行3 次顾客点位置获取，取3 次算例平均结果，以降低选点随机性造成的结果不真实性。

求解结果方面：表4 矩形框所在算例C30的GAP 值为负，但HACO-VND 的TF 远远优于CPLEX的TF；其他算例GAP值皆为非负数。表明HACO-VND 在求解结果上可以达到甚至优于CPLEX的解。

表4 CPLEX、HACO-VND求解结果Table 4 Solution results of CPLEX and HACO-VND

求解时间方面：对于Nnumcom＜10 的小算例，CPLEX求解时间小于HACO-VND；对于Nnumcom＞10的算例，HACO-VND的求解时间更优。

从求解结果和求解时间上都可以得出HACOVND算法的有效性，并且优于CPLEX。

3.3 灵敏度分析

为验证不同住宅楼规模，即不同楼层数的住宅楼对配送方案的影响，对来自A、B、C、D、E 这5 种不同规模住宅楼的算例进行实验，通过无人机能耗利用率DECU 分析不同规模住宅楼对配送结果的影响。实验结果如表5 所示，整理后得到图7（a）和图7（c）。

表5 不同规模住宅楼算例结果Table 5 Calculation results of residential buildings of different sizes

图7（a）中可以得出：Nnumcom不变时，随楼层数增加，DECU整体上呈上升趋势；住宅楼规模不变时，DECU 虽有波动但整体上保持平稳。这说明在住宅楼规模不变时，Nnumcom增加使无人机单次飞行时的能源得到充分利用，所以不需要替换为性能更优的其他型号无人机。

除了住宅楼规模，无人机最大能耗E、无人机最大载重量Q、无人机单次飞行成本与单位能耗成本F1∶F2之比等都可能对结果产生影响。各参数在不同取值下的配送结果如表6所示，整理得到图7（b）和图7（d），分析结果如下。

表6 不同单位成本比值、最大载重量、最大能耗下的算例结果Table 6 Calculation results under different unit cost ratio,maximum load capacity and maximum energy consumption

图7 住宅楼规模、F1∶F2、Q、E 对DECU或FN的影响Fig.7 Impact of residential building scale,F1∶F2 , Q, E on DECU or FN

（1）F1∶F2

从图7（b）中发现，随着F1∶F2变大，TEC成本在TF中占比增大。当F1∶F2≥1 时，DECU保持不变，这说明TN 仍然是配送方案的决定性因素；当F1∶F2＜1 时，决定性因素变成了TEC，此时会尽量减少无人机能耗，通过增加TN 减少TEC，导致DECU 下降，FN 减少。无论F1∶F2如何变化，降低无人机飞行成本和TEC 成本依旧是减少配送成本的最快途径。

（2）Q、E

一方面，从图7（c）中发现，E不变时，DECU 与住宅楼的规格无关，但对于同一规格住宅楼，DECU 随着E的增加而降低；从表5 中可以看出，TF 几乎没有变化，说明单方面提高E不会改善配送结果或提高DECU，由此猜测Q限制了配送结果的优化。

另一方面，对图7（d）进行分析。首先，随着Q的增加，TF逐渐减少；当Q=1.5 kg 时，E的增加对TF 无影响；当Q＞1.5 kg 时，E的增加使TF 短暂下降。其次，对于Q，当无人机E＞138 kJ 时，DECU随着Q的增加而上升，说明此时的Q是限制性因素；E=95 kJ 时，TF 和DECU 基本保持不变，说明此时的E是限制性因素。最后，对于E，Q≤2.0 kg时，DECU 随着E的增加而下降，这是因为此时Q为限制性因素，E的增加未能改变配送方案；Q=2.5 kg 时，DECU 随着E的增加有短暂的上升，这是因为E=95 kJ 时，限制了FN，而随着E的上升，Q又成了限制性因素。

综上表明，单方面提高E或Q并不能提高DECU，两者是相互牵制的，所以未来配送无人机的改进应同时提高这两个性能。此外，改善无人机的E、Q能够优化配送方案，减少物流公司上门配送成本，使高层住宅无人机上门配送模式得到普及，反向推动物流公司加大对无人机性能的研究。

4 结论

本文提出一种新场景下的无人机末端配送模式，解决城市高层住宅顾客上门配送需求，完成“最后一公里”配送中的“最后一百米”配送。综合考虑无人机最大载重量、最大能耗以及不同配送阶段的实际能耗，使HRR-DDTDP 模型更具有实际意义。带VND的混合蚁群算法根据顾客数量使用不同局部搜索算子组合，在求解大中型规模算例时具有较优的性能。实验结果表明：配送区域范围的扩大可以提高无人机能耗利用率，使用一台无人机为整栋高层住宅服务是可取的；无人机的最大载重量、最大能耗互为限制，共同影响配送方案，物流公司在研发无人机时应将两者结合起来考虑。

疫情的常态化将推动无人机在上门配送中的应用，除却包裹重量，还有其他因素会对无人机的能耗产生影响，今后研究将考虑飞行高度、风速、温度等对无人机配送能力的影响。