导  语

新冠肺炎疫情当前，为做到快速响应，服务于当前和后续疫情的科学有效防控，《中国公路学报》拟组织出版“重大突发公共卫生事件下交通运输应急管理专刊”。本文为专刊已录用论文。

彭勇，工学博士，重庆交通大学教授，重庆市运筹学会理事，西部交通与经济社会发展研究中心研究员，中国公路学会及重庆市道路运输协会会员，长期从事交通运输规划与管理、物流系统优化等方面的研究。主持主研省部级及以上项目10项，公开发表SCI/EI收录论文20余篇，出版教材1部，在建《运输组织学》线上精品课程。

0 引言

在新型冠状病毒肺炎（COVID-19）疫情蔓延开来的背景下，为了控制疫情发展，多地采取一经发现确诊病例，就对该区域进行隔离封闭的措施。该措施在减少人与人接触的同时，也阻断了车辆的正常行驶。城市配送面临非正常的新环境，只有改变传统物流配送方式才能让长时间处于封闭隔离区域的客户得到服务。

近年来，以无人机和无人车为主的配送新模式进入人们的视野。与无人车相比，无人机在配送过程中对道路条件无要求，技术应用较为成熟，已开始商用实践。顺丰早在2012年就开始研究无人机配送，并获得了数百余项专利。2016年6月京东物流实验室也开始无人机测试，作为京东智慧物流全国运营调度中心，也是京东全国无人机运营调度中心的宿迁，在2017年“618”期间，实现了无人机常态化运营，并对宿迁周边部分村庄实现用无人机配送快递。国内物流“三巨头”京东、顺丰、阿里巴巴正与来自世界各地的公司竞相开发兼具性能、续航能力和可靠性的无人机，以便大规模配送商品，解决快递公司面临的成本高昂的“最后一公里”难题。

无人机配送已在企业开始实践，但国内关于无人机配送系统优化相关学术研究较少，国外近几年有学者在该方面展开研究。如Dorling等^[1] 考虑无人机的飞行距离和载重的关系并建立模型，研究发现能量消耗和送货时间不能同时达到最优，因此需要在这两者之间做出平衡，选择在实际场景下的合适的方案。Song等^[2] 融合无人机物流系统飞行时间有限、货物对性能影响大等特点，提出基于混合整数线性规划的无人机运输路径模型，设计启发式算法解算路径。Boualem等^[3] 考虑了无人机在人道救援物流的应用，提出在载荷和能耗约束下无人机运输物品总成本最小的优化模型。

无人机的使用有望在“最后一公里”货物配送中改变物流行业的格局。然而无人机在商业领域广泛应用之前，仍然存在监管问题和技术的障碍。2018年3月21日中国民航局发布《民用无人驾驶航空器经营性飞行活动管理办法（暂行）》，填补了无人驾驶航空器从事经营性飞行活动的法律空缺，但是却不适用于无人机载客类和载货类的经营性活动。京东等国内巨头的无人机配送实践仍然停留在划定区域的实验示范阶段。同时，无人机的配送过程还与自身技术有着紧密的联系。在配送过程中无人机依靠的是GPS，在GPS没有校正的情况下，无人机的精度大约为10米^[4] 。无人机在城市中进行配送，很可能会与GPS失去联系。Park和Kim^[5]研究发现，即使有精确的定位信息，（半）自主无人机也需要拥有障碍物探测和规避的能力。

2014年，Wohlsen^[6]提出了无人机与卡车协同送货的想法，在该问题中无人机和卡车可以同时独立送货，但无人机送货服务完成后需要返回卡车上。Agatz等^[7] 将该路径规划问题称为无人机旅行商问题，并将该问题构建成混合整数规划模型，并提出了一种基于局部搜索和动态规划的两阶段启发式算法用以解决该问题。Murray和Chu^[8]针对无人机与卡车协同送货提出了FSTSP和PDSTSP两种模型，假设一辆卡车和一架无人机，共同为客户服务，以最小化服务时间为目标。Yurek和Ozmutlu^[9]提出了求解FSTSP的两阶段迭代算法。

本文综合考虑由新冠疫情等事件导致部分客户点卡车无法实现配送的情况、无人机最大飞行时间受无人机载重影响以及无人机在某一客户点多次完成起降的情景，研究车辆搭载无人机对某区域内多个客户送货时，如何分配客户以及规划车辆和无人机路径，使总服务时间最短的问题。本问题的解决方案既能满足在发生新型冠状病毒肺炎等重大突发公共卫生事件时的人群隔离要求，减少人与人之间接触，又能增加传统卡车配送货物的灵活性，提高总体的配送效率。

1 问题描述

配送中心安排一架有效载重约为10kg的小型无人机与一辆卡车协同，对某区域内不同疫情状况以及不同需求的多个客户进行日常生活需求送货。考虑突发事件下，配送最重要的是时间因素，因此，优化目标定为寻找卡车和无人机服务客户的最小服务时间。每个客户必须由司机操作的卡车或搭载的无人机提供一次服务。由于某些客户的需求可能无法由无人机完成（例如，超过无人机有效载荷能力的包裹、包裹需要本人签收或者无人机无法安全降落的客户位置），因此这样的客户必须仅由卡车提供服务（Truck-only Customer，TC）。而由于新型冠状病毒肺炎的蔓延，有些小区或者区域由于确诊病例施行了交通管制、道路封闭，这样的客户点使得卡车无法直接服务，而只能由无人机进行配送（UAV-only Customer，UC）。

与此同时，还有一些客户点（Flexible Customer，FC），卡车与无人机配送不受限制。

在疫情背景下，考虑对客户与客户之间接触的可控性，设定无人机一次飞行服务只服务一个客户点。

卡车和无人机同时移动，但不独立。卡车和无人机的运动必须同步，以允许无人机在其允许的飞行时间内在离散位置返回卡车。无人机在配送过程中，卡车可以在起飞地点等待无人机返回，也可以在某一点回收并再次发射无人机。图1给出了一个有无人机协助的卡车配送方案。

图1. “卡车-无人机”协同配送路径示意图

以开始提供配送服务到完成配送服务所花费总时间最小为目标建立数学模型。为了保证卡车在某节点的出发时刻不早于到达该节点完成服务及可能的无人机发射回收操作后的时刻，给出如下约束：

为了确保卡车到达某个节点完成服务后的时刻不晚于无人机达到该节点的时刻，给出如下约束：

为了确保卡车在某个节点的出发时刻不早于无人机回到该节点完成回收后的时刻，即无人机需要回到该节点回收后卡车才能够出发，给出如下约束：

为了确保无人机在某个节点的出发时刻不早于卡车到达该节点完成服务后的时刻，即无人机必须等卡车到达该节点完成服务后才能够起飞服务其他节点，给出如下约束：

为了保证无人机在服务客户时，不会出现从卡车上再派出无人机这种不可能情况，给出如下约束：

并通过以下两个约束保证无人机服务满足飞行时间限制：

2 邻域搜索算法设计

为了解决“卡车-无人机”协同配送路径规划问题，本文提出一种结合简单启发式算法的混合邻域搜索算法（算法流程如下图2所示）。在形成初始路径的情况下，采用无人机起飞端邻域搜索（USS）、无人机降落端邻域搜索（UES）、FC取出操作（FCTO）、FC放回操作（FCPI）及跳出局部搜索空间的暴力交叉操作（WOPT）等五种不同的邻域操作，对路径进行优化。

图2. 邻域搜索算法流程

2.1 不同配送方案设计

在实际生活中，存在因为客户处在比较偏远的地方，同时周围只有一个可以让无人机起飞和降落的客户点，那么配送该客户显然需要让卡车在服务的客户点等待无人机完成配送任务并回收后才继续下一个点的配送服务；或者由于起飞降落耗时不多而可以在同一点完成无人机的降落与执行下一任务的起飞操作。在疫情发生交通管控情况下，道路资源更是允许采取这样的配送策略。但对于城市环境，也存在卡车无法长时间停车和阻塞交通，必须尽快前往下一个服务目的地，不能在起飞地点等待无人机返回，只能在随后的一个客户地点等待这一情况，这可以认为是本问题的特例。在下文会同时对两种方案进行分析。为便于区分，我们将无人机必须在不同节点起飞降落，即卡车在同一个节点不能同时完成无人机的起飞以及无人机的回收的情况称为方案a；无人机可以在同一个节点完成起飞和降落，即卡车可以在同一个节点完成无人机的起飞和无人机的回收的情况称为方案b。两种配送方案如图3和图4所示。

图3. 方案a配送示意图

图4. 方案b配送示意图

2.2 不同优化操作设计

（1）无人机起飞降落领域搜索

USS是指在无人机路径中随机选取一条无人机子路径，针对无人机起飞节点，从卡车路径中前一次无人机完成服务降落点到该次无人机任务降落点之间客户点中随机选择一客户点作为新的该次无人机任务起飞点进行领域搜索（搜索示意如图5和图6）。UES与USS类似，不再累述。

图5. 方案a无人机起飞节点搜索示意图

图6. 方案b无人机起飞节点搜索示意图

（2）灵活客户点取出、放入卡车路径操作

针对卡车路径，分为FCTO和FCPI。对于FCTO，首先随机选取卡车路径中无人机处于未工作状态的路段，从该路段中随机选择满足条件的灵活点作为无人机服务的节点；然后针对该灵活点，方案b在排除该灵活点的该路段中选择距离其最近客户点的作为无人机的起飞降落节点，方案a要求选择满足要求的两个不同节点分别作为起降点，如图7和图8所示。对于FCPI，随机选取一条为FC服务无人机子路径，从无人机起飞节点到降落节点的节点区间，将无人机服务节点放回到区间内距离无人机服务节点最近的节点之后，形成新的卡车路径和无人机路径。

图7. 方案a取出操作示意图

图8. 方案b取出操作示意图

（3）暴力交叉操作

本文采用随机选取卡车路径上两点进行交叉（WOPT），扩大搜索空间，避免以上邻域搜索陷入局部最优解。当粗暴交叉卡车路径上的客户点时，可能会出现无人机路径不可行情况，这时调整无人机起飞降落点，将出现的不可行解变为可行解，保证在扩大搜索空间的同时能够避免不可行解，提高算法搜索效率。

3 实验分析

采用Solomon标准实例数据集R101数据，生成25个客户点的小规模案例和100个客户点的大规模案例。

本文采用了三种不同的生成初始路径的TSP方法，分别为随机生成法（R）、模拟退火法（SA）以及迭代最近法（ICP）。表1是在小规模案例下，三种不同生成路径方法得到的卡车行驶距离表。从表中可以看出，R 法生成初始卡车路径所花费的时间最短，但是得到的卡车初始路径行驶的距离最长，且与另两种方法的结果相差巨大。ICP法平均运行时间较小的同时，平均路径行驶距离也最短。

表1不同TSP方法生成卡车初始路径对比（25个客户点）

采取不同卡车初始路径生成方法，算法30次寻优结果如图9和图10所示。

图9. 小案例规模不同TSP方法计算结果对比

图10. 大案例规模不同TSP方法计算结果对比

可以看出，无论是小规模案例还是大规模案例，由ICP得到的初始卡车路径，采取相同的领域搜索，得到的解质量较好，说明产生较好的初始卡车路径有利于搜索发现更好的方案。同时还可以看出，经过ICP法得到的最优解显得更加的集中，从侧面反映出ICP法与邻域搜索算法相结合求解效果较好。对比方案a与方案b，不难发现，方案a的解集为方案b解集的子集，理论上，方案b的最优解不劣于方案a，但这也意味着方案b需要在更大的搜索空间去搜索最优解。因此，在相同的迭代次数与搜索策略下，方案b不一定能找到比方案a更好的解，上图验证了这一点。

在不同邻域搜索模块组合下，算法运行30次，得到结果如图11所示。

图11. 不同算法模块组合平均最优值对比

可以看出，同样采用R方法生成初始卡车路径，SF获取的优化结果明显劣于其他组合策略，说明想要只通过SF得到一个好的目标函数值，则需要更好的初始解作为支撑。这也从另一个角度反映出FCTO与FCPI模块对寻找最优解的影响最大。同时可以看出增加了FCPI之后，目标函数的最优值在相同条件下都得到了减少，反映出FCPI对于整个目标函数的优化具有积极的影响。USS和UES两个模块对比，在寻优结果上，USS模块优于UES模块。

4 案例分析

以重庆市南岸区为例，可以通过疫情地图得到发生新型冠状病毒肺炎病例的地点，这些地点施行了道路交通管制，只能通过无人机配送货物。TC、UC与FC位置分布如图12所示。通过百度地图道路网络得到各点之间的车行距离，各点之间无人机飞行距离取两点之间的直线距离。车辆在一般城市道路行驶速度为40km/h，在内环快速行驶速度为80 km/h。无人机空载行驶速度为30km/h。设置不同的客户点需求以及服务时长，无人机飞行速度载重影响因子为2km/(h•kg)，最大飞行时间为30min，发射无人机所需时间为2min，回收无人机所需时间为2min。通过本文所给算法可得到图12所示配送方案，服务耗时3.51h。

图12. 实际案例配送方案

研究还发现，选择飞行速度受货物装载量影响小、续航能力更强的无人机进行配送，可以相应减少物流配送所花费的时间。但这会增加无人机成本，在无人机应用其他场景应注意这一点。

5 结语

本文研究了在发生新型冠状病毒肺炎疫情等重大突发公共卫生事件下的城市物流配送问题。

结合道路条件、无人机飞行时间限制等约束，考虑无人机载重对飞行速度的影响，构建了卡车-无人机协同配送的路径优化模型。为了解决本文所提出的问题，采用了结合简单启发式算法的混合邻域搜索算法，使用经典的Solomn数据集形成两个不同规模的案例进行了数值实验，验证了该算法具有较高的可行性和实用价值。最后，给出了利用所设计算法解决实际问题的一个案例。

在疫情背景下，无人机协同卡车进行配送相较与传统卡车配送具有独特的优势，无人机能够实现“无接触”配送，但是在城市配送中，高楼等外部因素会影响无人机的安全性。

未来可具体研究不同无人机型号产生的成本，结合无人车的协助配送，研究适应不同情境状况下的新型物流配送方式。同时可针对邻域搜索算法不同的算子设计进行更深层次更丰富的分析，尝试设计更多不同的邻域搜索算子来提高解的质量。

参考文献

[1]  Dorling K, Heinrichs J, Messier G G, et al. Vehicle routing problems for dronedelivery [J]. IEEETransactions on Systems, Man, and Cybernetics: Systems, 2016, 47(1): 70-85.[2]  Song B D, Park K, Kim J. Persistent UAV delivery logistics: MILP formulation and efficientheuristic[J]. Computers & Industrial Engineering, 2018, 120:418-428.[3]  Rabta B, Wankmüller C, Reiner G. A drone fleet model forlast-mile distribution in disaster relief operations[J]. InternationalJournal of Disaster Risk Reduction, 2018,28: 107-112.[4]  ArnoldL L, Zandbergen P A. Positional accuracy of the wide area augmentation system inconsumer-grade GPS units[J]. Computers & Geosciences, 2011, 37(7):883-892.[5]  Park J, Kim Y. 3Dshape mapping of obstacle using stereo vision sensor on quadrotorUAV[C]// AIAA Guidance, Navigation, and Control Conference. 2014: 0975.[6]  Wohlsen M. The nextbig thing you missed: Amazon’s deliverydrones could work—they just need trucks[J]. Wired: Business,Jun, 2014, 10.[7]  Agatz N, Bouman P, Schmidt M. Optimization approaches for the traveling salesmanproblem withdrone[J]. Transportation Science, 2018, 52(4):965-981.[8]  Murray C C, Chu A G.The flying sidekick traveling salesman problem: Optimization ofdrone-assisted parcel delivery[J]. Transportation Research Part C: Emerging Technologies,2015, 54: 86-109.[9]  YurekE E, Ozmutlu HC. A decomposition-based iterative optimization algorithm fortraveling salesman problem with drone[J]. Transportation Research Part C:Emerging Technologies, 2018, 91: 249-262.

备注

（1）本文投稿日期为2020年2月29日，3月20日修回，现已正式录用。

（2）本文正式论文的全文3月23日已在中国知网进行网络首发：彭勇,黎元钧.考虑疫情影响的“卡车-无人机”协同配送路径优化[J/OL].中国公路学报:1-18[2020-03-23].http://kns.cnki.net/kcms/detail/61.1313.U.20200323.1002.002.html.

（3）本文为《中国公路学报》“重大突发公共卫生事件下交通运输应急管理”专刊论文，该专刊其他文章全文将于近日陆续在中国知网以网络首发形式刊出，印刷版后续结集出版。