无人机和车辆协同配送映射模式综述与展望

刘正元, 王清华

(陆军勤务学院军事物流系, 重庆 401331)

无人机在农业、监测等民用领域已广泛运用,而如今无人机在配送领域的研究也逐渐成熟。2013年,亚马逊首次宣布实施无人机配送项目,并宣布于2017年正式进入实际应用阶段。2014年,谷歌实施代号为“Wing”的无人机配送项目,实现了配送无人机直达目的地并自动完成卸货的功能。德国DHL(Dalsey, Hillblom, Lynn)于2013年12月在公司总部完成了无人机投递的室外测试。2014年9月,第2代无人机获得德国联邦运输部和航空管理局许可,飞越北海提取药品,于2016年3月完成第3代无人机试飞[1]。谷歌、亚马逊和DHL等都已经将无人机运用到配送领域,其开发的大多数无人机以每小时48～64 km的速度飞行,飞行距离为16～48 km,有效载荷一般为5 kg左右[2]。由于无人机在大多数场景中可采取直线飞行,相比于车辆配送有配送距离短、飞行速度快等优势,然而无人机又有着有效载荷低、续航能力差的特点,单独使用无人机只适用于小批量多批次的配送。

2014年,Wohlsen[3]首次提出无人机与运输车协同配送的想法,其构思的未来物流配送是无人机与运输车可同时进行独立送货,无人机在完成配送任务后需返回运输车。在此基础上,无人机和车辆协同配送的研究近年来开始兴起,部分企业也对此进行了尝试,如轻浮自主无人驾驶飞机交付、多米诺无人驾驶飞机交付和HorseFly无人驾驶飞机交付,其中无人驾驶飞机从交付车辆发射,在一个位置进行包裹交付,而车辆同时进行另一次交付[4]。

任新惠等[5]对现有无人机和车辆组合配送的相关文献进行综述,总结出无人机和车辆协同配送的4种模式:车辆协助无人机配送模式,无人机协助车辆配送模式,无人机与车辆独立配送模式,无人机和车辆同步配送模式。虽然任新惠总结出了无人机和车辆组合物流配送的方式,但在实际场景中往往可能存在多种模式,而不是运用单一模式。本文将从车辆和无人机映射关系的角度入手,分析无人机和车辆协同配送的映射模式,讨论相关变体、参数和约束条件,总结目标及相关算法,最后对未来研究方向提出展望。

本文第1节在单车单机映射模式(traveling salesman problem with drone，TSP-D)中主要总结了无人机和车辆协同配送的4种模式，包括无人机和车辆同步配送模式(flying sidekick traveling salesman problem, FSTSP)、无人机和车辆并行配送模式(parallel drone scheduling traveling salesman problem, PDSTSP)、车辆保障无人机配送模式(vehicle guarantee drone traveling salesman problem, VGDTSP)和无人机保障车辆配送模式(drone guarantee vehicle traveling salesman problem, DGVTSP)。第2节主要总结了单车多机映射模式(traveling salesman problem with multiple drones，TSP-mD)和多车多机映射模式(multiple traveling salesman problem with drones，MTSPD)的相关文献。第3节从3个方面总结讨论了3种映射模式:首先,讨论了3种映射模式下变体的相同处和不同处;其次,总结了目前无人机和车辆协同配送映射模式中研究的目标和算法,进而讨论了无人机和车辆协同配送映射模式所涉及的相关参数;最后,讨论了无人机和车辆协同配送映射模式面对实际问题所涉及的约束条件。第4节在对无人机和车辆协同配送映射模式的未来展望中考虑了实际性能分析和异构无人机优化。

对TSP-D的分析可基于任新惠提出的无人机和车辆组合配送模式。

1.1 FSTSP

2015年,Murray和Chu[6]引入了一种新型的旅行商问题,称为FSTSP,提出了在车辆顶部安装一架无人机的想法,该无人机可以在车辆进行一项交付任务的同时进行另一项交付任务。一旦无人机完成交付,就需要在当前交付位置或沿其路线返回车辆,到下一个交付位置。由于问题复杂,FSTSP只考虑一辆车辆和一架无人机的情形,如图1所示。

图1 FSTSP拓扑图Fig.1 FSTSP topology

Agatz等[7]提出的无人机旅行推销员问题是独立于FSTSP提出的,但仍然共享大多数常见的假设。在这个问题上,FSTSP的一个关键区别是无人机可以在车辆发射的相同位置被找回,并且无人机的操作受到飞行距离而不是时间的限制,然后采用局部搜索与动态规划相结合的算法求解模型。

Bouman等[8]基于贝尔曼-霍尔德-卡普(Bellman-Held-Karp)动态规划算法介绍了一种求解FSTSP的三步精确式方法,并将该方法的最后一步推广到A*算法。此外,文献[8]尝试将这种精确式算法应用于限制车辆在与无人机分离时可能访问的位置数量的问题,这个限制缩短了计算时间,但代价是可能从解空间中移除最优解。Ha等[9]提出了两种启发式方法——贪婪随机自适应搜索问题(greedy random adaptive search problem, GRASP)和旅行商问题-局部搜索(traveling salesman problem-local search, TSP-LS)，用于启发式求解FSTSP。GRASP元启发式算法首先使用3种不同的启发式算法对车辆旅行推销员问题生成旅行,然后使用分割算法将一些客户从车辆旅行中移除,并将其分配给无人机。TSP-LS启发式算法改编自Murray和Chu提出的启发式算法,但在算法的每次迭代过程中,在无人机和车辆路线之间重新定位客户所节省的成本计算方面存在差异。在拥有100个客户的问题实例上的实验结果表明,GRASP启发式算法在求解质量上优于TSP-LS启发式算法,尽管其需要更多的计算时间。Es和Ozmutlu[10]开发了一种基于两阶段分解的算法来求解FSTSP。在第一阶段,使用贪婪启发式方法将客户分配到车辆和无人机上。在第二阶段,求解一个数学规划模型,得到无人机的行程,使无人机在交会点的等待时间最少。Pedro等[11]对FSTSP模型进行了扩展,允许无人机在与车辆的两次连续会合之间每次访问几个客户。除了多点假设,其模型的其他特点是没有为车辆和无人机预先建立路线,并且将每个位置视为其潜在同步点,然后通过模拟退火算法的全局优化方案,求解了大规模的场景。

综上所述,在FSTSP模式中,车辆一般配送至离供应点较近的需求点,而无人机辅助车辆进行末端配送,以有效节省总的配送时间和成本。然而,由于无人机在配送过程中依赖于车辆,所以需要考虑无人机和车辆在何处对接,因此对协同性的要求很高,这可以参考传统的拖挂运输问题(truck and trailer routing problem, TTRP)。目前,针对FSTSP模式的研究还停留在基础阶段,较少考虑无人机和车辆对接时存在的实际问题,并且在其问题求解算法中通常基于动态规划的思想分阶段求解无人机和车辆的任务目标,未来需要耦合无人机和车辆的协同任务目标。

1.2 PDSTSP

2015年,Murray和Chu[6]除了提出FSTSP,在文献中还提出PDSTSP,即车辆和无人机从仓库出发独立进行交付,如图2所示。

图2 PDSTSP拓扑图Fig.2 PDSTSP topology

无人机和车辆数量的不同不会对PDSTSP的模式运用带来任何变化,所以本节不只基于TSP-D进行文献回顾,还回顾了单车多机、多车多机模式的文献。Ham[12]对PDSTSP问题进行了拓展,其中无人机可以实施连续多阶段的取件和配送任务,解决了多车多机保障多需求点的配送任务分配。Kim和Moon[13]扩展PDSTSP并构建了单无人机站台的旅行商问题(traveling salesman problem with a drone station, TSP-DS)的混合整数线性规划(mixed integer linear programming, MILP)模型,考虑了一辆车和多架无人机,以允许无人机独立于车辆,从仓库以及从预先指定的无人机站进行调度,最后发现TSP-DS比PDSTSP更为高效。Chauhan等[14]针对PDSTSP问题的特点,构建了以配送无人机最大航程为直径、以最大范围覆盖用户为目标的仓库选址模型,并以三阶段贪婪算法求解。

由此看出,PDSTSP问题可以分解为两个经典的运筹学问题: TSP和并行机调度问题(parallel machine scheduling problem, PMS)。PDSTSP模式只需要基于上述两个问题考虑如何合理分配客户以实现完工时间最小化,求解难度较小,但其重点是如何判断先进行TSP问题求解或是先进行PMS问题求解,这将会极大影响PSDTSP问题的求解质量。

1.3 VGDTSP

Mathew等[15]在研究多种运输工具配送问题(heterogeneous delivery problem, HDP)时，首次提出车辆只负责装载配送无人机与需求物资,对所有需求点的配送都由无人机完成,但其在模型约束中事先设定了无人机配送的任务点,因此该问题是传统的旅行商问题。

Savuran和Karakaya[16]提出了VGDTSP,其目标是通过找到车辆停靠点来发射一架无人机,从而在为所有客户提供服务的同时,最大限度地缩减无人机的行驶距离。这个问题可称为“仓库机动性问题”,因为车辆是无人机的移动仓库。文献[16]开发了一种遗传算法,用一辆车辆和一架无人机来解决一些问题实例,并用最近邻和爬山算法来评估和比较所获得的结果。Othma等[17]基于VGDTSP证明了单车辆和单无人机的多式联运是NP(non-deterministic polynomial)-hard问题,并提出了求解该问题的近似算法。

Luo等[18]在TSP-D的模型构建中,允许无人机单次发射实施多个客户的配送,并考虑了无人机与车辆同时在时间和空间上的协同约束。该问题被公式化为一个MILP模型,描述了一个两级位置路由问题。为了解决这个问题,开发了两种启发式方法,首先构建一个车辆旅行,然后将其分成几个子旅行,将每个子旅行分配给一个无人机。Carlsson和Song[19]考虑将一辆货车携带一架无人机,拓展提出无人机配送的始发点与回收点可在车辆路线上的任一位置,通过连续逼近法找到车辆保障无人机的最佳路线。文献[19]的一个关键发现是无人机与车辆协同使用的潜在收益(提高效率)与无人机和车辆之间的相对速度的平方根相关。

本文将上述这种无人机和车辆组合配送的方式称为VGDTSP,如图3所示。这种模式属于给定车辆路线的无人机调度问题(drone scheduling problem for given truck route,DSP)的拓展,并且包括DSP。这一模式适用于车辆无法直达客户地点的城市场景,也适合客户点分散、单位面积物流需求量小、道路条件较差的农村地区配送。

图3 VGDTSP拓扑图Fig.3 VGDTSP topology

1.4 DGVTSP

DGVTSP是指车辆执行配送任务,由无人机作为辅助为车辆补货,这种配送模式主要适用于车辆的途中补货。Dayarian等[20]关注的是无人机补给的同一天交付问题,其中由车辆监督交付订单,无人机的作用是向车辆提供补给,最后提出了一种启发式方法来解决该问题。但为了简化研究模型,考虑了仅有一个配送中心、一辆货车和一架无人机的情况。McCunney和Cauwenberghe[21]假设无人机为车辆提供包裹补给,以实现当天交付服务:无人驾驶飞机将包裹运送到一组预先指定的转运点,每辆车辆从专用转运点提取包裹,为客户所在地的特定区域提供配送服务,根据订单到达间隔时间、转运点数量、车辆数量和无人机数量的不同数值进行综合分析。

由于无人机配送刚刚兴起,相应的配套政策还不够健全,短期内可能无法实现大规模无人机配送。加之受无人机载重能力弱的限制,DGVTSP的运用场景受限,所以相关研究很少,后文不予以讨论。

TSP-mD和MTSPD这两类研究内容和问题基本一致,所以归为一节进行综述。但这两种映射模式与TSP-D有很大区别:这两种映射模式能实施多种无人机和车辆组合模式。由于MTSPD是TSP-mD的更NP-hard问题,目前大部分文献已开始研究基于FSTSP的MTSPD,而基于VGDTSP的研究仍主要停留于研究TSP-mD。

2.1 基于单一模式

2.1.1 基于FSTSP的MTSPD

Campbell等[22]对MTSPD问题提出了连续近似(continuous approximation,CA)模型,以获得每条路线上车辆和无人机的最佳交付数量、每辆车辆上无人机的最佳数量以及车辆-无人机混合交付问题中的总运营成本。Wang等[23]通过研究发现无人驾驶飞机可以从仓库或任何客户位置的车辆上发射,也可以由不同客户位置的车辆取回(或在仓库结束其旅程),并建立了MTSPD模型。文献[22]对使用无人机可以节省的时间提出了几个上限,上限是通过研究最优解的结构获得的,取决于无人机与车辆的相对速度以及每辆车辆的无人机数量。Poikonen等[24]对Wang等的工作进行了改进,提出了从任意位置发射和回收无人机的可能性(同车辆),而不是仅限于客户位置。Daknama和Kraus[25]提出了无人机车辆路径问题,该问题具有Wang等无人机路径问题的大部分特征,不同的是文献[25]允许无人机由不同的车辆发射和回收。Wang和She[26]基于无人机可由不同的车辆发射和回收,通过一个分支定价(branch and price, B&P)算法求解了MTSPD。在该算法的定界子问题中,设计了一个特殊的网络来区分不同类型的路径和节点,并通过剪枝和扩展策略提出了一种改进的脉冲算法。

Sacramento等[27]进一步扩展了FSTSP模型,考虑了车辆的容量限制,并提出了一种自适应大邻域搜索元启发式算法来解决MTSPD。Daniel等[28]基于MILP,同时考虑了无人机可循环操作和不可循环操作,即车辆既可以在无人机发射点等待无人机返回,也可以执行配送任务,在下一需求点与无人机汇合;其次,文献[28]还对无人机参数进行了灵敏度分析,如有限时间、有限距离等情况;最后,提出混合无人机编队下无人机存在速度和耐久性的不同。Euchi和Sadok[29]也研究了MTSPD问题,但假设每辆车只携带一架无人机,设计了一种混合遗传-扫描算法进行求解,即采用扫描算法作为局部搜索的遗传算法,并在构造初始解时采用了最近邻算法和改进的节约算法。Felix和Udo[30]提出一个分支切割(branch and cut, B&C)算法进行求解,并使用有效的不等式来加强线性松弛和加速求解过程,最后说明MTSPD不仅可以提高交付速度,还可以减少车队规模,而不会减缓交付过程,并增加车辆司机的工作量。

MTSPD模式是将FSTSP中TSP-D扩展的一种模式,协同性从二维升至高维,建模复杂难度急剧上升,求解更加困难,所以在绝大部分MTSPD问题研究中,设置了较多的假设条件,并且忽略了很多现实因素而简化模型。当不仅仅能实现只基于FSTSP的MTSPD,而是实现基于多种组合模式的MTSPD时,才能真正将MTSPD运用于真实的配送场景中。

2.1.2 基于VGDTSP的TSP-mD

Ferrandez等[31]研究了车辆和无人机协同交付系统中的时间效率和能量效率,考虑由一辆货车保障多架无人机完成交付作业,通过融合K均值聚类和遗传算法,解决了联合配送时无人机发射位置的确定以及单车携带无人机数量的优化问题。文献[31]做了一些实验来研究各种相对速度的影响,结果表明无人机的速度应该至少是车辆速度的2倍,以显著减少路线时间。Boysen等[32]基于VGDTSP研究了由沿着给定车辆路线运行的车辆发射无人机的调度问题。根据车辆上无人机的数量和无人机的操作策略,导出了6个基本问题版本,并显示了其计算复杂性。Chang和Lee[33]展示了一辆车辆作为无人机的移动仓库,以获得车辆和无人机返回仓库的最短时间。其开发了一个三阶段算法来解决多达100个客户的几个问题实例。该算法首先使用K均值聚类对客户进行分组,然后通过在第二步中求解一个旅行商问题来确定车辆路线,最后通过寻找移动集群中心的移位权值和非线性规划,以增加所获得的集群覆盖的总面积。Aline和khaled[34]基于VGSTSP模式提出单车多机模式,无人机每次执行交付任务能配送一个或多个客户,并且在每个位置都能发射和回收多个无人机。最后设计了改进节约里程算法,对比求解得到:当使用的无人机在其飞行范围和承载能力方面平衡时,网络运行成本显示为最小。一般以客户密度高为特点的服务区,需要承载能力大的无人机;客户稀少的服务区,更适合使用航程较长的无人机。

目前,TSP-mD模式仍停留在基于VGDTSP模式的研究,相比于MTSPD而言复杂度较低,假设条件较少,研究范围较广。虽然当将VGDTSP模式拓展到MTSPD时,复杂度也急剧增大,但复杂度仍远比不上基于FSTSP的MTSPD,这是因为基于VGDTSP的MTSPD不需要考虑车辆之间的任务分配,而只需要考虑无人机与车辆之间的映射关系,比如无人机不一定返回原先出发的车辆,而是根据最优原则返回至任一车辆。

2.2 基于多种组合模式

Patchara等[35]总结了MTSPD的4种运行模式:① 无人机从车辆出发执行配送和交付任务,在任务完成后返回同一车辆,如图4所示;② 无人机从车辆出发执行配送和交付任务,在任务完成后返回不同车辆,如图5所示;③ 无人机从仓库出发执行配送和交付任务,在任务完成后返回车辆,如图6所示;④ 无人机从仓库出发执行配送和交付任务,在任务完成后直接返回仓库,如图7所示。

图4 无人机返回同一车辆的MTSPD运行模式Fig.4 MTSPD operating mode of drones returning to the same vehicles

图5 无人机返回不同车辆的MTSPD运行模式Fig.5 MTSPD operating mode of drones returning to the different vehicles

图6 无人机由仓库出发返回车辆的MTSPD运行模式Fig.6 MTSPD operating mode of drones from warehouse to the vehicles

图7 无人机由仓库出发返回仓库的MTSPD运行模式Fig.7 MTSPD operating mode of drones from warehouse to warehouse

由图4～图7,可以看出前3种模式都属于FSTSP模式,最后一种模式则属于PDSTSP模式。联合此4种运行模式思想,发现运用PDSTSP和FSTSP组合模式,比单一使用FSTSP能减少配送时间。文献[35]在求解中开发了一种新的启发式算法,称为自适应插入启发式算法(adaptive insertion heuristics, ADI)，来解决MTSPD。启发式方法由两个阶段组成:构建多旅行商解决方案和对初始多旅行商解决方案应用移除和插入操作符来构建MTSPD解决方案。在ADI中涉及3种多旅行商启发式算法:遗传算法、组合K均值/最近邻法和随机聚类/旅行法。在Dukkanci等[36]研究的无人机和车辆协同配送中,建立了PDSTSP和VGDTSP组合模式,但其已确定了车辆的路线,如图8所示。

图8 VGDTSP和PDSTSP的组合模式Fig.8 Combination mode of VGDTSP and PDSTSP

目前,对基于多种组合模式的研究较少,但研究的拓展空间很大。虽然目前相关文献只涉及了PDSTSP和VGDTSP的组合模式,但未来还可以探讨FSTSP和PDSTSP组合模式、FSTSP和VGDTSP组合模式、VGDTSP和无人机和车辆协同配送模式(vehicle routing problem with drone, VRPD)的组合模式等。在未来，要想运用好多种组合模式,需要从顶层设计入手,建立起多种组合模式的模型,并设计出可行的算法。

前两节将大部分关于无人机和车辆协同配送的相关文献进行了综述,有些文献将无人机和车辆协同配送的模式命名为VRPD,但无特殊情况时,VRPD模式可以转化为MTSPD模式。本节将基于TSP-D的前两者(即FSTSP和PDSTSP)的TSP-D、TSP-mD和MTSPD的文献回顾,进行综合性分析和论述,并对未来无人机和车辆协同配送的研究方向提出展望。

3.1 3种映射模式下的变体讨论

3.1.1 3种映射模式下变体的相同处

由于3种映射模式只是改变了无人机和车辆的数量,所以实质上MTSPD是基于TSP-mD的更复杂问题,而TSP-mD是基于TSP-D的更复杂问题。3种映射模式下的相同处即为TSP-D下的问题,本节将基于TSP-D分析FSTSP、PDSTSP和VGDTSP下的异同。大部分文献将无人机与车辆协同配送分为串联式服务和并联式服务,将串联式服务定义为无人机安装在车辆上并一起使用,如FSTSP;将并联式服务定义为无人机和车辆互不干扰,如PDSTSP[37]。本文提出一种新的串并联服务定义:在VGDTSP中,所有需求点都是由无人机进行交付,所以可称为串联服务;PDSTSP和FSTSP中部分需求点由无人机交付,部分需求点由车辆交付,所以可称为并联服务。分析FSTSP的相关文献,其变体有如下4种形式:① 无人机能否从仓库起飞或返回;② 无人机是否执行可循环操作(车辆在原地等待无人机),此时包括3种情况:只能执行可循环操作、不能执行可循环操作、可能执行可循环操作;③ 无人机在执行一次配送任务时能否前往多个需求点;④ 无人机能否从车辆路径的任一位置起飞或返回,不能的情况为无人机只能从需求点起飞和返回。

在VGDTSP中,由于车辆专门保障无人机,不存在上述变体形式中的②和④,即在VGDTSP中无人机可能执行可循环操作,并且能从车辆路径的任一位置起飞和返回。同时，对于变体形式中的①,在VGDTSP中无论无人机能否从仓库起飞或返回,对实验结果都不会造成影响,因为无人机从车辆路径中最靠近仓库的位置发射,等同于从仓库发射,所以变体形式①在VGDTSP中也可以不讨论。在PDSTSP中,无人机本来就是从仓库起飞执行独立交付任务,所以不存在变体形式①、②和④。由于在PDSTSP中,无人机每次执行配送任务的起始点都是仓库,所以对于变体形式③,往往是根据无人机的续航能力进行判断,不需要提前假设。

3.1.2 3种映射模式下变体的不同处

3种映射模式下,只有基于FSTSP,才存在不同变体,TSP-mD中的FSTSP变体除了包含TSP-D中的4种变体形式,还包含任何位置能否发射和回收多架无人机;MTSPD下的FSTSP变体除了包含TSP-D中的5种变体形式,还包含无人机能否返回不同车辆,如图5所示。

除了上述不同,TSP-mD和MTSPD与TSP-D最大的区别在于:TSP-mD和MTSPD能同时使用多种组合配送模式。由于VGDTSP和FSTSP之间存在一定的矛盾性(车辆是否需要交付到客户),所以两者不能组合使用。因此，在TSP-mD和MTSPD之间的多种组合模式往往是PDSTSP和FSTSP(见图7)、PDSTSP和VGDTSP(见图8)的两种组合模式。虽然VGDTSP和FSTSP不能联合使用,但将VGDTSP的思想运用到FSTSP中,就变成了FSTSP中的一个变体形式:无人机能从车辆路线上的任一位置起飞和返回。

3.2 目标和算法总结

3.2.1 目标总结

无论是3种基础配送模式还是3种映射模式,其目标函数主要研究3方面内容,但在不同映射模式的变体中存在差异,具体分析如下。

(1) 最小总配送时间，即最小-和时间[38],由所有配送时间和等待时间相加得到:

(1)

此目标可分为两类:一是无人机最小-和时间只考虑无人机的最小总配送时间,一般适用于VGDTSP中,这是因为在VGDTSP中车辆不进行交付任务,此时可以将式(1)中的第3项删除;二是无人机和车辆最小-和时间,不仅要考虑无人机,还需要考虑车辆的最小总配送时间,一般适用于FSTSP和PDSTSP中。将式(1)扩展到TSP-mD中时,最小总配送时间变为

(2)

式中:K为无人机集合;xijk为决策变量,xijk=1代表有无人机k从i点到j点的路径。

将式(1)扩展到MTSPD中时,最小总配送时间变为

(3)

式中:W为车辆集合;yijw为决策变量,yijw=1代表有车辆w从i点到j点的路径。

(2) 最小完成配送时间，即最小-最大时间[38],此目标也可分为两类:当无人机被允许从需求点返回仓库时,此时最小完成配送时间取车辆和无人机到达仓库时间的最大值,即

(4)

当无人机不被允许从需求点返回仓库时,此时最小完成配送时间为车辆到达仓库的时间,即

(5)

(3) 最小配送成本根据对成本包含的内容不同而不同。配送成本通常指车辆和无人机在配送过程中基于行驶距离而产生的油耗和电力成本[39-41]。然而,成本的适当建模通常是困难的,因为成本取决于许多影响变量,并且可能出现非线性成本趋势,例如燃料消耗;另一方面,确定所有现实的成本可能非常麻烦。因此,经常使用面向时间的目标。最小-和时间对应于以效率为导向的标准,可以用于最大限度地缩减总完工时间,也可以用于近似最小化成本。相比之下,最小-最大方法代表了一种公平标准,旨在平衡旅行长度,有助于提高客户服务的质量。

3.2.2 算法总结

算法可从精确式算法、启发式算法和连续近似算法3大类分别进行讨论。在车辆和无人机协同配送模式中,现有运用的精确式算法主要包括动态规划法和基于剪枝操作加速求解的分支定界(branch and bound, B&B)、B&P和B&C算法。Dell’amico等[42]重新构建了FSTSP模式的目标函数,提出了三下标模型和二下标模型,并通过一组有效不等式加速了B&C的求解。尽管在精确式算法中采取了加速操作,但仍只能解决规模比较小的问题。基于启发式算法的算法又可以分为两类:经典启发式算法和元启发式算法。在使用经典启发式算法求解车辆和无人机协同配送问题中,主要包括节约里程算法和扫描算法。经典启发式算法简单普适,一般用于规划一个初始可行解,再结合元启发式算法进一步求解。元启发式算法又可以分为单点元启发式算法和多点元启发式算法[43]。在关于车辆和无人机协同配送问题的单点元启发式算法中,主要使用了邻域搜索算法、模拟退火算法、贪婪搜索算法。在关于车辆和无人机协同配送问题的多点元启发式算法中,主要使用了遗传算法和人工蜂群算法。连续近似算法通过不断逼近的近似方法来求解问题。在求解车辆和无人机协同配送问题的过程中,与精确式算法不同的是,求解时间在一个多项式时间内,与启发式算法不同的是,需要用严格的数学证明解的质量。相比于精确式算法和启发式算法,连续近似算法在解决车辆和无人机协同配送问题时面临一定的挑战。目前在一些数学规划优化器,如CPLEX、Gurobi中,已有通过运用上述算法来求解无人机和车辆协同配送问题的实例[44]。车辆和无人机协同配送模式中的算法归纳如图9所示。

图9 算法归纳图Fig.9 Algorithm induction graph

首先,由于无人机和车辆协同配送的问题较为复杂,属于NP-hard问题,可基于经典启发式、元启发式和精确式算法相结合的思想进行融合求解。林驿等[45]设计了一个基于最近邻思想的由改进节约里程算法与动态规划法构成的两阶段启发式算法,对时变网络下带时间窗的无人机-车辆路径问题进行了求解。杨航[46]设计了嵌入改进节约里程算法的人工蜂群算法,对单运输车辆搭载多无人机的配送模式进行了求解。

其次,大多数文献都采取多阶段策略进行求解。在对FSTSP类问题进行求解时,一般至少采取两阶段算法进行求解:第一阶段是将需求点划分为车辆配送点和无人机配送点,并寻找车辆的最短路径;第二阶段是在考虑无人机续航、载重等多约束情况下,得到无人机的任务分配,并寻找无人机的最短路径。在对VGDTSP类问题进行求解时,一般采取三阶段算法进行求解:首先,以改进的K-means聚类算法进行客户分类,将聚类中心设置为车辆停靠点;第二阶段,以所有车辆停靠点为研究对象,构建车辆最优初始行驶路线;第三阶段,结合无人机的任务分配,最终确定车辆和无人机配送路线。这种多阶段算法类似于路由算法中的分组分层思想,通常需要与动态规划算法相结合,以进行调整。VGDTSP和FSTSP虽然都使用了多阶段策略求解,但VGDTSP是基于先聚类后路径算法[47]的思想,而FSTSP是基于先路径后聚类算法[48]的思想。

3.3 参数讨论

在基于无人机和车辆协同配送的文献中,影响其目标值的参数包括:无人机飞行速度、车辆行驶速度、车辆数量、无人机数量、需求点数量、无人机和车辆的承载能力、无人机的续航能力等。本节将这些参数进行合并分析,得到对目标值影响最大的3个参数。

3.3.1 无人机和车辆的相对速度

无人机和车辆的相对速度之比(the ratio of speed of drone and truck, RS-DT)会在很大程度上影响运用模式,一般使用无人机的最大飞行速度和车辆的平均行驶速度进行对比:

(6)

RS-DT值越大,无人机进行交付的客户数量越多,更倾向于使用VGDTSP模式。当RS-DT值小于一定程度时,PDSTSP和VGDTSP将不可取,因为此时无人机的优势不存在;但无人机在FSTSP中仍然可行,只不过无人机在每次执行任务时与客户的数量关系更倾向于一对一,以避免车辆等待的时间过长。其次,RS-DT值会影响车辆和无人机的数量关系,当RS-DT值大到一定程度时,MTSPD可以转化为TSP-mD,而对目标结果影响不大,这将大大节省车辆所带来的成本。然而,RS-DT值并不是越大越好,因为当RS-DT值大到一定程度时,将会使无人机等待时间过长,反而导致效率降低。正如文献[19]结论所得:无人机与车辆协同使用的潜在收益(提高效率)与无人机和车辆之间相对速度的平方根相关。RS-DT的最优值将会根据具体的无人机和车辆运行模式和其他参数的不同而变化。

3.3.2 无人机数量和需求点数量

无人机数量会影响目标值,特别是影响最小完成配送时间的目标值。然而,无人机数量有上限,其上限受两个因素影响。一是需求点数量,这个决定因素是全局性指标,由需求点数量决定的无人机数量上限代表即使再增加一架无人机,也不会再优化目标值。但这不意味着需求点数量的增加一定会导致无人机数量上限的增大,这是因为无人机之间的协调将会使无人机数量上限具备一定的冗余,而且在高密度需求领域,无人机的使用和利用率会随着无人机潜在服务客户的增加而增加[49];二是车辆容量限制,这个决定因素是局部性指标,根据每辆车辆的长宽高与载重,决定每辆车辆的无人机数量上限。要想确切分析由此因素决定的无人机的数量上限,还要考虑根据实际需求数量而装载的物资,这将存在最优化装载问题。

无人机数量和需求点数量还会影响算法的优劣,部分算法只适用于小规模问题的求解。当需求点数量过多,基于小规模构建的算法将无法得到较优解;而当无人机数量增加时,每个无人机的任务分配将变得更加复杂,如何合理地使用并改进相关算法,将会直接影响目标值的好坏。

3.3.3 无人机续航能力

虽然在部分无人机和车辆协同配送模式中,假设无人机在执行一次配送任务时,只能前往一个客户,不考虑无人机续航能力,但当研究更实际化时则不需要此假设,如部分文献中无人机执行一次配送任务时能前往的客户数量将由其续航能力决定。

Dorling等[50]和Byung[51]等针对无人机配送问题(drone delivery problem, DDP),提出了无人机最大飞行时间与有效载荷近似呈线性关系,只不过后者的有效载荷考虑了电池和有效负载。两者利用MILP解决了无人机最小成本或最短时间配送问题。彭勇等[52]在Dorling基础上考虑了最大飞行时间受载重影响的TSP-D问题。

Liu等[53]为多旋翼无人驾驶飞机系统开发的模型,广泛用于包裹交付的飞机类型——证明了功耗是无人机速度和有效载荷的函数。在较低的速度下,功耗随着速度的增加几乎保持不变(或略有降低),但是在更高的速度下,功耗随着速度非线性地增加,即无人机功耗与飞行速度为非线性关系。Murray和Raj[54]基于Liu等开发的无人机续航模型,研究了多飞行伙伴旅行商问题(multi flying sidekick traveling salesman problem, mFSTSP)。然而,其文中的多功能飞行模拟器中的无人机速度是固定的,因此无法利用变速飞行节省时间。

Dukkanci等[36]最早提出无人机速度是决策变量,但其假设车辆在成本最小化的问题中不进行交付,只充当无人机返回的移动枢纽,即研究的模型基于VGDTSP。Murray和Raj[55]进一步基于mFSTSP提出可变mFSTSP,将无人机速度作为决策变量,在速度和航程之间进行权衡。其提供了一个三阶段算法,以最小化总交付时间为目标,动态调整无人机速度,以实现卓越性能。将无人机速度作为决策变量而不是参数,并革新了此前文献中的观念——无人机需要以最大飞行速度执行任务。之后,无人机执行任务的飞行速度将可取最大航程速度vL-max(使得无人机航程最大时的速度)和最大飞行速度vmax之间的所有值,如图10所示。无人机在飞行途中可根据实际情况在vL-max和vmax之间调节飞行速度,而小于vL-max的飞行速度由于不能带来任何收益,可以不予以讨论。

图10 无人机航程和飞行速度、载重之间的关系Fig.10 Relationship between drone range, flight speed and load

3.4 约束条件讨论

大部分文献目前对无人机与车辆协同配送约束条件的研究仍停留在一些基本的物理约束,如无人机续航能力、无人机载重能力、车辆容量等因素。只有个别文献研究了特殊的约束条件,如Jeong等[56]不仅考虑了有效载荷对能耗的影响,还考虑了存在禁飞区的约束情况;朱晓宁等[57]不仅考虑了无人机禁飞区的约束,还考虑了车辆限行的约束条件;Di和Guerriero[58]在MTSPD模型中引入了客户时间窗约束,这也是目前唯一一篇在无人机和车辆协同配送问题中引入时间窗约束的文献。

实际上，无人机和车辆协同配送问题中的约束条件可以基于车辆路径规划(vehicle route problem, VRP)和DDP问题中的约束条件进行归纳和拓展。一是基于装载限制的VRP问题中的约束,车辆的容量不仅要考虑物资的长、宽、高[59]、还要考虑无人机的长、宽、高,并设计好相对应的无人机和物资存放空间。这方面约束可以基于装箱问题(bin packing problem,BPP)进行深入研究,以增强货物尺寸的有效装载;二是基于动态需求问题中的约束,无人机每次执行任务的路线将会根据客户动态性进行调整,比如新增客户订单、配送地址变化和服务时间窗变化等情况;其次,交通、天气等环境因素也会动态性影响车辆或无人机的配送路线[60],特别是在战场环境下,此约束尤为重要。针对这方面约束,需要采取一些预测方法和备用方式,以尽可能减小动态因素所带来的损失;三是在DDP问题中,要结合三维航迹规划中的约束,如无人机的爬升/俯冲角约束、最小转弯半径约束、飞行高度约束等[61]。这些约束要结合物资尺寸和重量、无人机续航能力和风力等参数进一步分析,比如当物资重量增大时,无人机爬升需要的动力更大,则无人机最大爬升角会减小;当风作为阻力并且物资尺寸增大时,无人机转弯所需的向心力更大,则无人机最小转弯半径会增大。最后,根据丛书全等[62]和黄俊波[63]所阐述的无人机空气动力学原理,可知无人机重量会影响无人机飞行速度,当配送无人机装载物资时,可转化为配送无人机重量的增加。但目前关于无人机配送的文献并没有考虑这点,这将导致实验结果与理论存在偏差。除此之外,本文认为无人机有效载荷对无人机飞行速度的影响是呈非线性的,需要考虑动力冗余情况。

当无人机和车辆协同配送问题考虑了上述较为全面的约束条件时,该问题变得更为复杂,特别是考虑到无人机航迹规划时。目前,所有无人机和车辆协同配送模型和求解过程都没有考虑无人机航迹规划中的约束条件,未来这将是一个艰巨且必要的研究方向。针对多约束条件整合的复杂性,未来一个可行的方案是结合智能交通系统和人工智能技术,在预测的基础上进行降维分析,以同时满足各约束条件。

未来,要想在实际中运用无人机和车辆协同配送,必须从实际的参数和约束条件出发进行仿真分析。一是根据物资、车辆和无人机的实际物理大小、重量,判断出无人机和车辆的映射模式;二是根据需求点分布范围、车辆和无人机的实际续航里程,判断出适合无人机和车辆配送的模式;三是要结合无人机和车辆协同配送的具体应用场景,增加特殊的相关约束。

在满足实际性能分析的基础上,可以进一步研究异构无人机和车辆的协同配送映射模式。广义的异构无人机在《异构多无人机》一书中介绍为由不同飞行平台、搭载不同负载、具备不同信息处理能力的多种无人机[64]。异构无人机目前大多停留于侦察、打击、监测领域的应用,肖东[65]探讨了异构无人机用于打击的自主任务规划方法;严飞等[66]考虑了侦察和打击混合异构无人机的实时任务分配,提出了基于协同粒子群算法和协同函数、协同变量相结合的算法;田震等[67]则进一步以异构无人机对多目标执行侦查、打击和评估任务为背景,综合考虑异构无人机任务执行能力、任务执行时序和自身运动学等约束。而在无人机和车辆协同配送问题中,由于无人机只执行配送任务,所以本文将异构无人机狭义地定义为具有不同载荷能力、不同续航能力、不同飞行速度的多种配送无人机。异构无人机的优化可以从两个方面进行探讨:异构车辆和需求点分布网络。异构车辆会影响异构无人机的数量——车辆的容量会限制无人机的数量:一辆车辆在装载完物资后可以容纳2架规格较大的无人机,4架规格较小的无人机(载荷能力小、续航能力弱)。当允许混合使用异构无人机时,一辆车可以装载2架规格较小的无人机和1架规格较大的无人机。使用异构无人机后,可能会使得目标值更优,这就取决于需求点分布网络。当需求点分布网络较为分散时,使用规格较小的无人机、在每次执行任务时配送少量需求点的方案更优;当需求点分布网络较为密集时,使用规格较大的无人机、在每次执行任务时配送大量需求点的方案更优。但是,一个需求点分布网络从局部来看,其平均距离是不一样的,平均距离小的局部网络适用规格较大的无人机,而平均距离大的局部网络适用规格较小的无人机。异构无人机的使用不仅能优化目标值,还能扩大配送范围,但重点是要平衡规格较大无人机的配送能力优势和规格较小无人机的数量优势。

针对无人机和车辆协同配送研究所考虑的内容极多,求解空间较大,不仅可以采取自上而下的集中式算法,还可以采取自下而上的分布式算法,以满足求解空间剧增条件下的快速收敛优化[68]。比如,周晶等[69]设计了一个分布式高维多目标演化优化算法,以解决多无人机协同时的最优任务分配。

本文首先总结了TSP-D下的4种无人机和车辆协同配送模式下的相关文献,并基于VGDTSP总结了TSP-mD和基于FSTSP总结了MTSPD的相关文献;其次,针对3种映射模式的相同变体和不同变体进行了述评,并总结了目前无人机和车辆协同配送模式中研究的目标和算法,进而讨论了相关参数和约束条件;最后,针对目前无人机和车辆协同配送模式中的不足,提出对未来研究方向的展望。

在之后的无人机和车辆协同配送问题中,首先应确认无人机和车辆的映射模式,然后基于映射模式分析配送问题属于多种组合模式还是单一模式,并确定配送问题属于何种配送模式,最终再确定是否存在变体形式;其次,目前无人机和车辆协同配送问题中的求解算法较少,未来可尝试使用多种改良算法进行求解。改良算法最好能提前识别“不良”操作,例如某一决策将会导致无人机或车辆等待时间变长。再次,多种参数值不能自由选择,而应该根据实际情况分析取值范围,再根据可行范围内的值、多种约束条件和异构无人机等信息确定参数的最优值;最后,有必要基于无人机和车辆协同配送问题中的实际性能分析,进一步研究异构无人机能够带来的收益。针对异构无人机的优化而研究需求点分布网络时,有必要深入分析网络的拓扑性质、层次结构、节点重要性和相似性等网络特征[70],以进一步得到深层的潜在结论。

猜你喜欢协同车辆文献家校社协同育人 共赢美好未来新班主任(2022年4期)2022-04-27Hostile takeovers in China and Japan速读·下旬(2021年11期)2021-10-12蜀道难：车与路的协同进化科学大众(2020年23期)2021-01-18Cultural and Religious Context of the Two Ancient Egyptian Stelae An Opening Paragraph大东方(2019年12期)2019-10-20“四化”协同才有出路汽车观察(2019年2期)2019-03-15车辆小太阳画报(2018年3期)2018-05-14The Application of the Situational Teaching Method in English Classroom Teaching at Vocational Colleges科学与财富(2017年22期)2017-09-10The Role and Significant of Professional Ethics in Accounting and Auditing商情(2017年1期)2017-03-22冬天路滑 远离车辆阅读与作文（小学低年级版）(2016年12期)2016-12-22三医联动 协同创新中国卫生(2016年5期)2016-11-12

推荐访问:无人机 映射 协同