无人机配送问题研究综述

宋佳怡 毛瑜琳 艾云艳 申佳微 邹晔

摘  要：物流业是支撑国民经济发展的基础性、战略性产业。我国“双碳”目标的提出是物流业实现智能化转型升级、谋求绿色低碳发展的重要契机，而无人机配送则是物流业实现节能减碳的重要途径。无人机配送一直是国内外学者关注的重要课题，文章主要从无人机独立配送和卡车-无人机协同配送两个方面分析无人机在配送领域的研究现状及发展趋势。

关键词：无人机配送；双碳；卡车-无人机协同配送

中图分类号：V279    文献标识码：A  文章编号：2096-4706（2023）08-0146-05

Abstract： The logistics industry is the basic and strategic industry that supports the development of the national economy. The proposal of China's “double carbon” goal is an important opportunity for the logistics industry to realize intelligent transformation and upgrading and seek green and low-carbon development， while UAV distribution is an important way for the logistics industry to achieve energy conservation and carbon reduction. UAV distribution has always been an important topic for scholars at home and abroad. This paper mainly analyzes the research status and development trend of UAV in the field of distribution from two aspects： UAV independent distribution and truck and UAV collaborative distribution.

Keywords： UAV distribution; double carbon; truck and UAV collaborative distribution

0  引  言

2020年9月22日，国家主席习近平在第七十五届联合国大会上郑重宣布，中国将“提高国家自主贡献力度，采取更加有力的政策和措施，力争2030年前二氧化碳排放达到峰值，力求2060年前实现碳中和”。同年12月，习近平主席在气候雄心峰会上宣布“到2030年，中国单位国内生产总值二氧化碳排放将比2005年下降65%以上”。

无人机大多是清洁能源驱动，无须配備驾驶员，速度比卡车快，且不受地面交通的限制，因此，无人机物流正处于快速成长期，具有巨大的商用前景，如亚马逊Prime Air无人机以及DHLParcelcopter无人机[1]，分别如图1、图2所示。摩根士丹利的研究报告显示，到2050年，全球城市空中交通市场价值将达9万亿美元，而空中智慧物流将是最有希望率先实现商业化的细分市场。UPS和DHL等物流巨头已在考虑通过无人机物流提高业务效率，并积极进行无人机物流的研发。中国各大物流、电商、无人机领域企业也在积极布局，正在逐渐步入高速发展阶段。2021年出台的《无人机快递投递服务规范》邮政行业标准是中国首个无人机快递服务行业标准，对于促进无人机物流的发展具有重大意义。

1  无人机独立配送问题研究现状及发展动态

国内外有很多学者研究了无人机独立配送问题，鉴于无人机成本低，不受地面交通的限制，飞行速度快但续航里程短，载重量有限，飞行安全性低等特点研究了多种无人机独立配送问题的变型。

1.1  无人机电量消耗函数研究

为描述无人机在不同环境和飞行模式下的电量需求，Kirschstein[2]提出了无人机电量消耗模型，并用于模拟一个从配送中心为固定客户群提供服务的固定包裹递送系统的电量需求。最后将无人机消耗的电量与同一配送中心服务同一客户群的柴油卡车和电动卡车的能量需求进行对比。Zhang等[3]回顾、分类和评估了几种不同的无人机电量消耗模型，并分析了关键因素与绩效指标之间的关系。

1.2  考虑非线性耗电函数的无人机独立配送问题研究

Cheng等[4]将无人机的电量消耗建模为载重量与行驶距离的非线性函数，研究了多行程无人机路径问题，并在求解过程中通过增加逻辑切割和次梯度切割来处理更为复杂的非线性电量消耗函数，采用两指标公式建模并设计了分支切割算法。数值实验表明，在许多情况下，线性电量消耗模型产生的路径在非线性电量消耗模型下是不可行的，与基于非线性电量消耗的模型相比存在约9%的电量消耗差异。例如，客户1和3的包裹重量分别为3和7，则无人机两条可行飞行路径（a）和（b）如图3所示。图3（a）中，无人机从发射站0出发，经过客户点1、换电站2、客户点3、换电站4、检修站5，最终回到无人机收集站0。图3（b）中，无人机从发射站0出发，经过客户点3、换电站2、客户点1，最终回到无人机收集站0。通过变换客户点的遍历顺序，减少了弧上的无人机载重量、耗电量和行驶距离。

1.3  无人机长距离配送问题研究

为克服无人机续航里程短、安全性低的问题，Shao等[5]提出一种新型包括电池更换站和维护检查点的长距离无人机配送服务系统，以最小化配送路径长度和着陆站点数量为目标构建无人机路径规划模型，并设计了蚁群优化算法与A*算法相结合的启发式算法，以避免蚂蚁的无方向性搜索。

1.4  无人机绿色路径优化问题研究

Chiang等[6]研究无人机对碳排放和成本的影响，提出一种无人机混合整数线性绿色路径的优化模型，设计一种有效求解复杂模型的遗传算法，并进行了大量的实验来验证模型及算法。结果表明，无人机配送能有效节约成本，降低碳排放。

1.5  无人机充电站选址-配送路径优化问题研究

Hong等[7]针对商业无人机配送服务系统，提出无人机充电站选址-路径模型，构建混合整数规划模型并设计启发式算法。

1.6  任务分配与路径联合优化的无人机配送问题研究

郭兴海等[8]针对无人机“最后一公里”配送问题，首先运用基于“区块链”思想的拍卖算法优化无人机编队的任务分配，然后以无人机碰撞、路径长度、雷达威胁、地形为约束构建目标函数模型，最后运用改进的量子粒子群算法对其进行求解。

1.7  无人机配送问题研究

裴颂文等[9]构建了逆向物流路径与正向物流路径相结合的动态路径规划模型，并设计了拓展性K-means++算法与遗传算法相结合的混合启发式算法。数值实验表明，该模型解的成本低于单独的逆向物流配送成本，相较于传统的K-means++算法，所提出算法的运行时间更短。

2  卡车-无人机协同配送问题研究现状及发展动态

国内外诸多学者研究了卡车-无人机协同配送问题，鉴于无人机成本低、不受地面交通的限制、飞行速度快但续航里程短、载重量有限、飞行安全性低，以及卡车续航里程长、载重量大等特点研究了多种卡车-无人机协同配送问题的变型。卡车-无人机协同配送过程如图4所示。一辆卡车携带一架无人机从配送中心0出发，服务客户点1并发射无人机，在等待无人机返回过程中服务客户点3并收集无人机，然后服务客户点4和客户点5并在客户点5发射无人机，在等待无人机返回过程中服务客户点7并收集无人机，最后返回配送中心。

由于卡车受地面交通状况的影响，故未来可在优化卡车-无人机的协同配送路径时将卡车的时变速度考虑在内，文献中较为常见的是将时变行驶速度设置成阶梯函数，如图5所示。

2.1  “单卡车+单无人机”协同配送问题研究

Vásquez等[10]研究了基于无人机的旅行商问题，构建了混合整数规划模型，并根据模型结构将其分解为两个自然决策阶段：

1）决策被卡车服务的客户子集并将客户进行排序。

2）决策无人机的派遣以及收集位置。然后设计一种分解算法进行求解。EsYurek和Ozmutlu[11]研究了一辆在车顶上搭载无人机的送货卡车与一架无人机的协同配送问题，以最小化配送时间为目标，设计一种基于分解方法的迭代算法，第一阶段确定卡车路径以及分配给无人机的客户，第二阶段通过确定第一阶段的路径和分配决策，求解一个混合整数线性规划模型来优化无人机路径。基于无人机的电量约束和载重量约束，郭秀萍和胡运霞[12]针对一辆卡车和一架无人机的协同配送路径规划问题进行了研究，设计了三阶段求解算法。

2.2  “单卡车+多无人机”协同配送问题研究

Poikonen和Golden[13]研究了一辆卡车与多个无人机的协同配送问题，允许无人机一次运送多个包裹服务多个客户，无人机的电量消耗与其载重量息息相关。Murray和Chu[1]分别在配送中心离客户点较远和较近的不同情形下构建了卡车-无人机协同配送的两种混合整数线性规划模型，其中前者假定无人机由卡车进行派送和收集，后者假定无人机由配送中心进行派送和收集，卡车和无人机的配送路径相互独立。Moshref-Javadi等[14]以最小化客户等待时间为目标，构建一辆卡车与多个无人机协同配送路径优化的混合整数线性规划模型，以确定客户集合在卡车和无人机之间的最优分配、卡车的最优路径，以及无人机沿卡车路径的最优发射和收集位置。与传统货车配送系统相比，比较客户等待时间差异。Salama和Srinivas[15]针对多架无人机与一辆卡车协同配送问题，将客户划分为小集群，每个集群确定一个焦点，并让卡车通过所有焦点。基于此构建数学模型，并假设集群焦点可位于某一客户位置或配送区域任意位置。Dell'Amico等[16]以最小化服务所有客户所需的总时间为目标，针对无人机和车辆并行配送问题构建了混合整数线性规划模型，并设计了相应的算法。Murray和Raj[17]针对一辆运输卡车与一组无人机的协同配送问题构建了混合整数线性规划模型，并设计了相应的算法。Mbiadou等[18]以最小化配送完成时间为目标，研究单个车辆与无人机并行配送路径问题，其中车辆执行传统的送货路径，而无人机则执行往返路径。设计了迭代两步启发式算法，主要包括将问题解转换为客户序列的编码步骤，以及将客户序列分解为车辆路径和无人机路径的解码步骤。Ha等[19]研究了一辆车与多个无人机的协同配送路径问题，其目标是最小化总运输成本和车辆等待时间所产生的成本。设计的第一种算法是修改Murray和Chu[1]提出的方法，通过局部搜索将最优TSP解转化为可行解。第二种算法是贪婪随机自适应搜索过程，它基于一个新的分割过程，将任意TSP路径最优地分割为问题解。Agatz等[20]研究了一辆车与多个无人机的协同配送路径问题，构建了整数规划模型并基于局部搜索和动态规划提出几种先路径、后聚类的启发式算法。胡大伟[21]研究了基于TSP的车辆-无人机协同配送路径问题（TSP-D以及基于VRP的车辆-无人机协同配送路径问题（VRP-D），并进行了数值分析。

2.3  “多卡车+多无人机”协同配送问题研究

多卡车-多无人机协同配送过程如图6所示。

Wang和Sheu[22]假设在满足飞行距离约束和装载能力约束的情形下，无人机可与卡车一起飞行，从站点起飞为客戶服务，在服务中心降落，与另一辆卡车一起飞行。基于此运营特点，研究了多卡车-多无人机协同配送路径问题，构建了混合整数规划模型并设计了分支定价算法。Jeong等[23]在研究卡车-无人机协同配送路径问题时考虑了无人机的禁飞区域以及无人机载重量对其电量消耗的影响这两个因素，构建了数学模型并提出了两阶段的构造及搜索启发式算法。Wang等[24]研究了以最小化路径最大持续时间为目标的无人机-卡车协同配送车辆路径问题，装有无人机的卡车车队向客户递送包裹，其中无人机可以从仓库或任何客户地点派出，并由卡车搭载。Euchi和Sadok[25]针对卡车-无人机协同配送路径问题，构建了混合整数线性规划模型，验证了模型的有效性并设计了混合遗传算法。Das等[26]针对带时间窗的卡车-无人机协同配送问题构建了多目标优化模型，该模型包含两个相互冲突的目标，即最小化行驶成本和最大化客户服务水平。提出协同帕累托蚁群优化算法来求解模型，并设计了非支配排序遗传算法对提出的算法进行比较和验证。Gonzalez-R等[27]针对卡车-无人机协同配送路径问题设计一种基于解的破坏和重构迭代过程的迭代贪婪启发式算法，并从文献中选取大量不同规模的实例对该方法进行测试。Kitjacharoenchai等[28]研究了两级的卡车-无人机协同配送路径规划问题，其中从配送中心出发的一级卡车路径服务于指定的客户，从卡车出发的二级无人机路径服务于其他客户集合。以最小化卡车和无人机在完成配送后到达仓库的总时间为目标，构建了混合整数规划模型，并设计了无人机-卡车路径构造算法和大邻域搜索算法。Schermer等[29]延伸了多卡车-多无人机协同配送路径问题，规定无人机不仅可以在顶点发射和回收，还可以在每个弧线上的一些离散点上发射和回收。针对该问题构建了混合整数线性规划模型，引入一些有效的不等式来提高MILP求解器的性能，并设计了变邻域搜索算法与禁忌搜索算法相结合的混合启发式算法。Schermer等[30]研究了多卡车-多无人机协同配送路径规划问题。以最小化配送完成时间为目标构建了混合整数线性规划模型，并引入几组有效不等式，设计一种有效利用问题结构的元启发式算法，并提出了无人机分配和调度问题。Sacramento等[31]针对多卡车-多无人机协同配送问题提出一种自适应大邻域搜索元启发式算法，进行了大量的计算实验，对卡车-无人机协同配送与单独的卡车配送模式进行对比分析。Kitjacharoenchai等[32]研究了卡车-无人机协同配送问题，其中无人机从卡车起飞进行派送，并飞到附近任何可用的卡车上。以最小化卡车和无人机完成配送后到达配送中心的时间为目标构建了混合整数规划模型，设计了新的插入启发式算法。王新等[33]研究了基于多个无人机站点的卡车-无人机协同配送路径问题，构建了相应的数学模型并设计了自适应大规模邻域搜索算法。

2.4  取送货卡车-无人机协同配送问题研究

Karak和Abdelghany[34]以最小化车辆和无人机的路径成本为目标，构建了针对车辆-无人机取送货混合路径问题的混合整数规划模型，设计该模型时考虑了无人机调度和收集过程中车辆-无人机路径的交互作用，以及与电池续航和最大载重量相关的无人机运营约束，设计了基于经典Clarke和Wright算法的新的求解方法，并将其性能与车辆驱动的路径启发式算法、无人机驱动的路径启发式算法进行比较。Ham[35]将Murray和Chu[1]的卡车-无人机并行配送问题扩展至多配送中心、多车辆、多无人机的情形，并假设无人机在投递完一个包裹后，可返回配送中心派送下一个包裹，也可以直接飞往下一个客户点取其他包裹。

3  结  论

未来可围绕非线性电量消耗模式以及时变行驶速度两个领域来丰富现有的研究体系，以期为物流企业的无人机配送路径决策提供参考，提高物流企业的配送效率及利润，进一步加快物流行业节能减碳的进程：

1）大多数学者在研究无人机配送问题时运用线性近似的无人机电量消耗函数，少数学者在研究无人机配送问题时假设无人机电量消耗是其载重量和行驶距离的非线性函数，但尚未将其应用于长距离无人机独立配送。未来可在优化无人机独立配送路径时考虑与载重量和行驶距离非线性相关的电量消耗函数。

2）大多数学者在研究卡车-无人机协同配送问题时未考虑卡车的时变速度，这不符合城市交通日益拥堵的现实。未来可在优化卡车-无人机的协同配送路径时考虑卡车的时变速度。

3）大多数学者在研究无人机配送问题时以最小化配送成本或配送完成时间为目标。未来可在针对无人机独立配送问题以及卡车-无人机协同配送问题进行建模或设计算法时，以最小化碳排放总量为目标，进一步契合当下大力提倡的“雙碳”目标。

参考文献：

[1] MURRAY C C，CHU A G. The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery [J].Transportation Research Part C： Emerging Technologies，2015，54：86-109.

[2] KIRSCHSTEIN T. Comparison of energy demands of drone-based and ground-based parcel delivery services [J/OL].Transportation Research Part D： Transport and Environment，2020，78：[2022-10-10].https：//www.sciencedirect.com/science/article/abs/pii/S1361920919309575.

[3] ZHANG J，CAMPBELL J F，SWEENEY II D C，et al. Energy consumption models for delivery drones： A comparison and assessment [J/OL].Transportation Research Part D： Transport and Environment，2021，90：[2022-10-13].https：//www.sciencedirect.com/science/article/abs/pii/S1361920920308531.

[4] CHENG C，ADULYASAK Y，Rousseau L. Drone routing with energy function： Formulation and exact algorithm [J].Transportation Research Part B： Methodological，2020，139：364-387.

[5] SHAO J，CHENG J，XIA B，et al. A Novel Service System for Long-Distance Drone Delivery Using the “Ant Colony+A*” Algorithm [J].IEEE Systems Journal，2021，15（3）：3348-3359.

[6] CHIANG W，LI Y Y，SHANG J，et al. Impact of drone delivery on sustainability and cost： Realizing the UAV potential through vehicle routing optimization [J].Applied Energy，2019，242：1164-1175.

[7] HONG I，KUBY M，Murray A T. A range-restricted recharging station coverage model for drone delivery service planning [J].Transportation Research Part C： Emerging Technologies，2018，90：198-212.

[8] 郭兴海，计明军，温都苏，等.“最后一公里”配送的分布式多无人机的任务分配和路径规划 [J].系统工程理论与实践，2021，41（4）：946-961.

[9] 裴颂文，沈天马，宁钟，等.ＫＭＧ：考虑逆向物流的无人机路径规划策略研究 [J].系统工程理论与实践，2019，39（12）：3111-3119.

[10] VÁSQUEZ S A，ANGULO G，KLAPP M A. An exact solution method for the TSP with Drone based on decomposition [J/OL].Computers & Operations Research，2021，127：[2022-10-16].https：//www.sciencedirect.com/science/article/abs/pii/S0305054820302446.

[11] YUREK E E，OZMUTLU H C. A decomposition-based iterative optimization algorithm for traveling salesman problem with drone [J].Transportation Research Part C： Emerging Technologies，2018，91：249-262.

[12] 郭秀萍，胡運霞.卡车与无人机联合配送模式下物流调度的优化研究 [J].工业工程与管理，2021，26（1）：1-8.

[13] POIKONEN S，GOLDEN B. Multi-visit drone routing problem [J].Computers & Operations Research，2020（113）：1-10.

[14] MOSHREF M，HEMMATI A，WINKENBACH M. A truck and drones model for last-mile delivery： A mathematical model and heuristic approach [J].Applied Mathematical Modelling，2020（80）：290-318.

[15] SALAMA M，SRINIVAS S. Joint optimization of customer location clustering and drone-based routing for last-mile deliveries [J].Transportation Research Part C： Emerging Technologies，2020，114：620-642.

[16] DELL'AMICO M，MONTEMANNI R，NOVELLANI S. Matheuristic algorithms for the parallel drone scheduling traveling salesman problem [J].Annals of Operations Research，2020，289（2）：211-226.

[17] MURRAY C C，RAJ R. The multiple flying sidekicks traveling salesman problem： Parcel delivery with multiple drones [J].Transportation Research Part C： Emerging Technologies，2020，110：368-398.

[18] MBIADOU S，LAURENT D，DOMINIQUE F，et al. An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem [J].Networks，2018，72（4）：459-474.

[19] HA Q M，DEVILLE Y，PHAM Q D，et al. On the min-cost Traveling Salesman Problem with Drone [J].Transportation Research Part C： Emerging Technologies，2018，86：597-621.

[20] AGATZ N，BOUMAN P，SCHMIDT M. Optimization Approaches for the Traveling Salesman Problem with Drone [J].Transportation science，2018，52（4）：965-981.

[21] 胡大伟，陈海妹，梁一为，等.车辆与无人机混合编队的路径优化问题模型构建 [J].长安大学学报：自然科学版，2021，41（1）：78-89.

[22] WANG Z，SHEU J B. Vehicle routing problem with drones [J].Transportation Research Part B： Methodological，2019，122：350-364.

[23] JEONG H Y，SONG B D，LEE S. Truck-drone hybrid delivery routing： Payload-energy dependency and No-Fly zones [J].International Journal of Production Economics，2019，214：220-233.

[24] WANG X，POIKONEN S，GOLDEN B. The vehicle routing problem with drones： several worst-case results [J].Optimization Letters，2017，11（4）：679-697.

[25] EUCHI J，SADOK A. Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones [J/OL].Physical Communication，2021，44：[2022-10-26].https：//doi.org/10.1016/j.phycom.2020.101236.

[26] DAS D N，SEWANI R，WANG J，et al. Synchronized Truck and Drone Routing in Package Delivery Logistics [J].IEEE Transactions on Intelligent Transportation Systems，2021，22（9）：5772-5782.

[27] GONZALEZ-R P L，CANCA D，ANDRADE-PINEDA J L，et al. Truck-drone team logistics： A heuristic approach to multi-drop route planning [J].Transportation Research Part C： Emerging Technologies，2020，114：657-680.

[28] KITJACHAROENCHAI P，MIN B C，LEE S. Two echelon vehicle routing problem with drones in last mile delivery [EB/OL].[2022-10-25].https：//www.researchgate.net/publication/338212362_Two_echelon_vehicle_routing_problem_with_drones_in_last_mile_delivery.

[29] SCHERMER D，MOEINI M，WENDT O.A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations [J].Computers & Operations Research，2019，109：134-158.

[30] SCHERMER D，MOEINI M，WENDT O. A matheuristic for the vehicle routing problem with drones and its variants [J].Transportation Research Part C： Emerging Technologies，2019，106：166-204.

[31] SACRAMENTO D，PISINGER D，ROPKE S. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones [J].Transportation Research Part C： Emerging Technologies，2019，102：289-315.

[32] KITJACHAROENCHAI P，VENTRESCA M，MOSHREF-JAVADI M，et al. Multiple traveling salesman problem with drones： Mathematical model and heuristic approach [J].Computers & Industrial Engineering，2019，129：14-30.

[33] 王新，王征，徐偉.面向多个无人机站点的车辆与无人机联合配送路径问题研究 [J].运筹与管理，2021，30（5）：31-37.

[34] KARAK A，ABDELGHANY K. The hybrid vehicle-drone routing problem for pick-up and delivery services [J].Transportation Research Part C： Emerging Technologies，2019，102：427-449.

[35] HAM A M. Integrated scheduling of m-truck， m-drone， and m-depot constrained by time-window， drop-pickup， and m-visit using constraint programming [J].Transportation Research Part C： Emerging Technologies，2018，91：1-14.

作者简介：宋佳怡（2000—），女，汉族，内蒙古赤峰人，本科在读，研究方向：工程管理；毛瑜琳（2002—），女，壮族，广西柳州人，本科在读，研究方向：法学；艾云艳（2001—），女，汉族，湖南临武县人，本科在读，研究方向：工程管理；申佳微（2000—），女，汉族，湖南邵东人，本科在读，研究方向：工程管理；通讯作者：邹晔（1991—），女，汉族，湖南益阳人，讲师，博士，研究方向：组合优化问题。