2021, Vol. 36
2. 长安大学 交通运输学院，西安 710064;
3. 长安大学 工程机械学院，西安 710064
2. College of Transportation Engineering, Chang'an University, Xi'an 710064, China;
3. College of Construction Machinery, Chang'an University, Xi'an 710064, China
电子商务的迅猛发展带动了快递行业的发展, 也推动了物流配送方式的持续变革. 无人机作为新兴配送工具而受到广泛关注. 2013年, 亚马逊公司首次提出无人机配送的概念[1], 并发布了PrimeAir无人机快递配送计划, 旨在为仓库周边的顾客提供服务. 随后, 谷歌的GoogleX实验室公布了Project Wing无人机送货研发项目[2], DHL快递公司也使用无人机为一个货车难以送达的小岛配送药品[3]. 在国内, 以顺丰为首的物流运输企业[4], 还有京东、菜鸟等电商平台, 以及饿了么、美团等即时配送平台[5], 也纷纷开始加大对无人机的研发力度, 推进无人机配送业务.
与传统的货车送货相比, 无人机配送具有较多的优势. 首先, 无人机飞行不受路况和地理条件的限制, 能有效拓展空间使用效率, 在交通拥堵的城市区域或地形复杂的偏远地区, 甚至是环境动态变化的灾区, 均可较快地完成配送任务; 其次, 无人机灵活性好, 操作方便, 在偏远地区配送能大幅减少人力成本; 同时, 无人机使用电池作为动力源, 更加节能环保. 然而, 无人机仍然存在载货量小、航程有限、易受干扰等不足之处, 单独使用无法满足现代物流的需求.采用无人机与地面车辆共同完成配送, 能使无人机在其能力范围内减少货车的送货任务, 使物流配送更加高效, 经济优势更加明显[6]. 因此, 研究车辆与无人机组合配送问题具有重要的理论和实践意义.
车辆与无人机组合配送问题可以看作是在旅行商问题(traveling salesman problem, TSP) 和车辆路径问题(vehicle routing problem, VRP) 的基础上引入无人机配送, 在实现配送更灵活、效率更高的同时, 也使模型更加复杂化和多样化, 是近几年各国学者关注的热点问题. Otto等[7]介绍了无人机在各种民用场景中的应用, 并针对配送场景, 对车辆与无人机组合配送模式进行归类. Viloria等[8]在前者的基础上, 分析了2005年~2019年有关无人机路径问题的研究, 从应用场景、约束条件、目标函数、求解算法等方面对问题进行归纳, 并提出了研究趋势和发展方向. Khoufi等[9]整理了有关无人机TSP和VRP的扩展问题. 这3篇综述均以无人机为研究对象, 指出车辆与无人机组合在不同行业的应用, 如: 军事侦查、数据收集、物流配送、人道主义救援等, 研究视角更为宏观, 但欠缺对配送路径问题的分析. 任新惠等[10]聚焦无人机和车辆组合在物流配送领域的应用, 总结了关键因素、优化目标等, 但未分析求解方法, 也没有详细梳理该领域研究的发展脉络和各研究之间的区别与联系, 研究文献相对较少.
鉴于车辆与无人机组合配送具有较好的应用前景, 而目前尚未有学者对该领域的学术研究做详尽的综述, 本文将通过研究2015年~2020年间发表的69篇国内外相关文献, 从运作模式、构成要素、求解方法、测试数据集等方面入手, 回顾其研究发展历程, 从而厘清车辆与无人机组合配送问题的研究现状, 把握未来可能的发展趋势.
1 问题模型车辆与无人机组合配送具有多种模式. 车辆与无人机均可参与配送, 也可仅由一方配送(另一方作为支持). 根据车辆与无人机在组合配送过程中角色的不同, 本文参考文献[7, 10], 将问题分为5种类型: 前4种如图 1所示, 分别是车辆与无人机协同配送、车辆与无人机并行配送、车辆支持无人机配送、无人机支持车辆配送; 第5种是混合模式配送, 包含两种及以上单一配送模式.
|
图 1 车辆与无人机组合配送模式分类 |
图 2展示了各配送模式在2015年~2020年的研究数量. 总体来看, 车辆与无人机组合配送问题的研究数量逐年增加, 且增幅较大. 其中: 车辆与无人机协同配送的研究最多, 共有44篇, 占总数的一半以上; 车辆支持无人机配送的研究数量次之; 车辆与无人机并行配送和无人机支持车辆配送的研究相对较少, 但也有小幅增长; 混合模式配送从2019年才开始出现, 是新兴的研究方向.
|
图 2 车辆与无人机组合配送研究数量 |
车辆与无人机协同配送是一种较为常见的模式(如图 1 (a)所示). 车辆搭载一架或多架无人机, 二者分别为各自服务的客户节点送货. 鉴于无人机续航能力差、飞行范围较小、载重量有限, 无法实现长距离、多客户配送, 车辆需在配送途中为无人机提供存储货物与充电服务. 无人机在完成某个节点配送任务后, 回到车辆上充电, 再从该车辆上起飞并继续为其他客户节点送货. 这一模式适合于城市中的末端配送、即时配送等场景. 在城市路网中, 一些客户位于道路狭窄、车辆难以通行的区域, 车辆配送效率低下, 用无人机替代更为方便灵活. 城市末端配送一般以小件包裹为主, 适合无人机配送; 车辆在装运大件货物的同时作为无人机的“移动仓库”, 可使二者形成优势互补. 城市即时配送的物品多为外卖、生鲜、日用品等, 强调时效性, 车辆在城市路网中可能受制于交通拥堵、限行区域等因素, 采用无人机更为快捷高效.
车辆与无人机协同配送可视为TSP(或VRP)的扩展问题, 车辆需满足与TSP(或VRP)一致的约束, 但仅负责配送部分节点, 剩余节点由无人机配送. 无人机在配送过程中依赖于车辆, 二者需考虑在何处对接, 因此, 对协同性的要求很高. 这与传统的拖挂运输问题(truck and trailer routing problem, TTRP)较为类似. TTRP的运载车队由卡车和甩挂运输车组成, 服务的客户可根据道路通行条件, 被分为仅允许卡车访问的客户和卡车或甩挂运输车均可访问的客户. 甩挂运输车分为卡车与挂车两部分, 二者均可承载货物, 但是挂车无动力, 必须附挂于卡车上. 卡车可将挂车卸下后单独运输, 也可与挂车接回, 以整车形式运输[11-12]. 可以看出, TTRP协调卡车与挂车之间的分离和连接, 与车辆和无人机考虑在何处对接以完成无人机起降类似. 但区别在于, TTRP中挂车与卡车分离后无法移动, 且每辆卡车只能挂一辆挂车, 而车辆与无人机可以独立运行, 且车辆可以搭载多架无人机, 这就增加了问题的复杂度.
根据车辆和车载无人机数量, 可将车辆与无人机协同配送问题划分为TSP-D (traveling salesman problem with a drone)、TSP-mD (traveling salesman problem with multiple drones)和VRP-D (vehicle routing problem with drones)三类, 如表 1所示.
|
表 1 车辆与无人机协同配送问题分类 |
Murray等[13]将一辆货车搭载一架无人机的协同配送称为FSTSP (flying sidekick traveling salesman problem), 规定无人机单程只能配送一个节点, 无人机与车辆分别沿欧氏距离和曼哈顿距离运行, 且车辆不得在同一节点处多次发射无人机. 他们以最小化完成时间为目标函数, 构建了混合整数规划(mixed integer linear programming, MILP)模型, 针对问题的NP难特性, 设计了一种启发式算法求解. 由于MILP模型求解时间长, 不适用于大规模计算, Agatz等[14]在前者的基础上, 构建了TSP-D整数规划模型. 与FSTSP略有不同, TSP-D假设无人机的空中飞行路线与车辆的地面行驶路线一致, 并且允许车辆在同一地点处多次发射无人机. Ha等[15]首次提出以最小化运营成本为目标的TSP-D模型, 运营成本包括运输成本和由等待而产生的时间成本.
Phan等[16]将模型扩展到一辆货车搭载多架无人机的情形, 并定义为TSP-mD. Campell等[6]发现TSP-mD更具有经济优势. Yoon[17]通过优化无人机数量以及车辆和无人机的路线来最小化无人机的成本. Moshref-Javadi等[18]构建了该问题的MILP模型. Murray等[19]在FSTSP的基础上, 假设无人机在飞行速度、载重、服务时间、飞行距离等方面具有差异性, 将该问题称为mFSTSP.
Wang等[20]进一步将车辆与无人机协同配送问题从单一车辆扩展到多车辆, 基于VRP模型提出了VRP-D. 他们从定量的方式出发, 通过设定车辆数、速度比和单车搭载无人机数3个参数, 分析VRP-D中的最差情况. 计算发现, 即使每辆车只配载一架无人机, 无人机和车辆具有相同的速度和距离矩阵, 协同配送模式也可缩短一半完工时间. Poikonen等[21]在前者的基础上, 放宽了模型的假设条件, 研究成本、电池使用时间、距离矩阵异同对完工时间的影响. Schermer等[22]最先构建了VRP-D的MILP模型, 并提出一些有效不等式以加速求解.
上述VRP-D模型均规定无人机必须起降于同一车辆. Daknama等[23]首先提出无人机可以起降于不同车辆的场景. Bakir等[24]在此基础上, 假设无人机可以多次访问客户节点. Kitjacharoenchai等[25]也采用该种模式, 但是规定一辆车在每个客户节点处只能释放或回收一架无人机. 此后, 这一假设也应用于文献[26-27]提出的模型中.
彭勇等[28]以新冠疫情为背景, 提出利用“卡车-无人机”协同配送模式为疫情高风险地区实行配送. 考虑到无人机最大飞行时间、载重以及道路条件的限制和客户需求的异质性, 将客户分为仅由卡车服务、仅由无人机服务和卡车与无人机均可服务3类. 对于车辆无法送达、而包裹重量超过无人机载重量的客户节点, 假设需求可拆分, 由无人机多次往返配送. Salama等[29]根据客户需求的重量, 将客户分为仅由车辆配送和可由车辆或无人机配送两种类型.
上述模型均假设无人机只能在配送中心或客户节点处从车辆上起飞或降落. Schermer等[30]在车辆路途中设置了一些离散的对接点供二者选择, 并将该问题定义为VRPDERO (vehicle routing problem with drones and en route operations). Wang等[26]考虑到无人机降落需要足够的地面空间和一些特殊的设备, 在模型中引入了专门的停靠枢纽(docking hubs)以供无人机和车辆对接. Marinelli等[31]提出车辆和无人机可在路途中任意位置对接. Salama等[29]将一辆车与多无人机的对接点设在车辆曼哈顿路径中的聚类中心.
也有部分文献通过引入约束条件, 研究协同问题的扩展问题. Di Puglia等[32]在VRP-D模型中引入客户时间窗约束, 建立了以最小化运输成本为目标的数学模型. Sacramento等[33]限定了每条路径的最大运行时长. Jeong等[34]研究了包裹重量对无人机飞行时长的影响, 并考虑部分配送区域在一些时段内禁止无人机飞行的情况.
图 3整理了TSP-D、TSP-mD和VRP-D的文献数量及趋势. 自2015年Murray等[13]提出FSTSP以来, 车辆与无人机协同配送的研究逐年增多, 其中TSP-D研究最为丰富, 因为它是协同配送模型的基础. VRP-D很容易在TSP-D的基础上对车辆进行扩展, 因此相关研究在2017年从零陡增. 但是TSP-mD的研究相对较少, 因为将单无人机扩展为多无人机后, 协同性从二维升至高维, 建模复杂度上升, 求解更加困难.
|
图 3 车辆与无人机协同配送研究趋势 |
目前, 车辆与无人机协同配送问题仍处于起步阶段, 大多数研究为简化模型, 设置较多假设条件, 而忽略了很多现实因素. 例如: 很多文献假设无人机单次行程只能配送一个客户, 但无人机的续航能力可能会满足多个节点配送的需求; 多数研究假设无人机因电池容量限制而有一个恒定的最大飞行距离或时长, 但在实际运行过程中, 无人机的续航与很多因素相关, 例如载重、风力等. 此外, 考虑多种约束条件的扩展研究较少, 仅有一篇研究了时间窗约束.
根据上述分析, 关于车辆与无人机协同配送问题的研究未来可从以下几个方面展开:
1) 考虑多车型车辆和多机型无人机. 车型和机型的多样化可以更好地匹配现实需求, 减少资源的浪费. 如果进一步考虑不同无人机每次起降于不同车辆, 则可使车辆与无人机之间的协同更为灵活, 配送更加高效.
2) 综合考虑影响无人机续航能力的因素. 目前考虑的影响因素主要是载重, 还可以进一步考虑风力、电池损耗等因素, 使能耗模型更加准确.
3) 扩展问题研究. 车辆与无人机协同配送问题作为TSP和VRP的扩展, 可以参考TSP和VRP的分支, 进一步丰富问题模型, 例如: 考虑带时间窗(软时间窗/硬时间窗)、同时取送货等场景; 或引入不确定性要素, 考虑无人机飞行过程中出现故障、车辆出现交通拥堵等情况; 研究动态、随机问题, 使模型更加符合现实场景.
1.2 车辆与无人机并行配送车辆与无人机并行配送是指车辆与无人机均参与配送, 但是二者是两个独立的运输单元, 各自作业, 互不影响. 图 1(b)展示了并行配送的运作模式: 无人机单独往返配送中心, “点到点”服务配送中心周围的客户; 而车辆一次性配齐货物, 服务距离较远的客户. 在这一模式下, 无人机只在配送中心取货和充电, 无需与车辆同步, 因此称之为并行配送模式. 研究发现, 如果大多数客户位于以配送中心为圆心的无人机飞行范围内, 则并行配送相比协同配送和VRP, 可大大缩短完工时间. 这种配送模式非常适用于郊区仓库的配送, 例如: 工厂直配或物流园区的配送, 无人机服务仓库周边客户, 车辆服务城市客户.
车辆与无人机并行配送问题最早由Murray等[13]提出. 他们研究了一辆货车和多架无人机配送的情形, 并称之为PDSTSP (parallel drone scheduling traveling salesman problem). 该问题可以分解为两个经典的运筹学问题: TSP和并行机调度问题(parallel machine scheduling problem, PMS). 首先, 为车辆服务的客户排序, 规划出类似于TSP的遍历路径; 然后, 将剩余客户分配给多架无人机, 分配过程可视为以最小化完工时间为目标的PMS, 即每个客户代表一个任务(job), 各任务的处理时间(processing time)由无人机往返配送中心与客户的飞行时间决定. 可以看出, 车辆与无人机并行配送问题通过分配客户给车辆或无人机, 将TSP和PMS两个问题关联. 若进一步扩展到多车辆配送, 则可分解为VRP和PMS两个子问题. 鉴于TSP、VRP和PMS均为经典的运筹学问题, 有大量研究可作为参考, 车辆与无人机并行配送问题求解难度较小, 只需考虑如何合理分配客户, 以实现完工时间最小化.
考虑到PDSTSP模型中无人机飞行里程有限, Kim等[35]在模型中加入了一个距客户较近而离配送中心较远的无人机站(drone station), 专门为无人机提供货物存储和充电服务. 无人机配送的货物先由车辆从配送中心送至无人机站, 再由无人机组配送; 无人机服务范围之外的客户则由车辆配送. 他们假设无人机站的位置已知, 构建了TSP-DS (traveling salesman problem with a drone station)的MILP模型, 研究发现TSP-DS比PDSTSP更为高效. Schermer等[36]在前者的模型基础上, 研究了无人机站的定位问题, 以最小化完成时间为目标, 构建了MILP模型, 使问题扩展为选址-路径问题(location-routing problem, LRP)的延伸.
Ham[37]在PDSTSP的基础上, 考虑了多车辆、多无人机与多配送中心的模型, 并增加了一些需要取货且带时间窗约束的客户节点. Ulmer等[38]在PDSTSP模型中引入了动态因素, 研究客户可在一天中任意时刻下单的“当日达”配送问题. 由于订单具有时间限制, 该模型的关键在于决定是否当日配送和采用何种交通工具配送.
目前, 车辆与无人机并行配送的研究较少, 多数文献研究了一辆车配送、无人机单程配送一个客户的情况. 目标函数以最小化完工时间为主; 相关的扩展研究仅有一篇考虑了取送货和时间窗, 还有一篇涉及动态场景. 因此, 车辆与无人机并行配送研究可从以下几个方面展开: 1)考虑多辆车和多架无人机的配送场景, 无人机可根据续航能力, 单程配送多个订单, 并可进一步扩展到多车型车辆和多机型无人机的情况; 2)考虑目标函数多元化, 例如: 车辆和无人机数量最小化、配送总距离最短等; 3)研究并行配送的扩展问题, 除取送货和时间窗以外, 还可以考虑多周期配送、多无人机场等场景, 并引入动态要素, 考虑客户需求变动、车辆旅行时间变动等情况, 使问题更加切合实际.
1.3 车辆支持无人机配送在车辆支持无人机的组合配送模式下, 仅有无人机执行配送任务, 车辆作为辅助, 为前者提供货物存储和充电等服务. 通常给定一些临时停靠点作为车辆与无人机的对接点, 以实现无人机的起降、充电和取货过程. 无人机往返于车辆与不同客户之间, 负责将货物从车上取出再送给客户. 在无人机送货的过程中, 车辆开往下一个对接点或停在原地等待无人机飞回. 这一模式适用于车辆无法直达客户地点的城市场景, 例如: 道路狭窄、不易通行的老旧社区、车辆限行区域、半封闭管理的学校、单位等, 也适合客户点分散、单位面积物流需求量小、道路条件较差的农村电商物流.
车辆支持无人机的配送问题通常需要首先确定对接点, 再分别规划车辆和无人机的路径, 这类似于LRP先确定仓库位置, 再规划配送中心到各仓库的一级路线和各仓库到客户的二级路线. 但是两个问题仍存在一些差异: 首先在空间上, LRP的两级路径是相互独立的, 而在车辆支持无人机配送问题中, 当车辆沿着既定路线行驶时, 无人机受其续航能力的限制, 只能访问车辆行驶路段周围的客户, 两者的行驶路径相互制约; 其次在时间上, LRP先规划一级路线, 再规划二级路线, 而车辆和无人机是相对同步的. 可以看出, 车辆支持无人机配送问题在决策对象上与LRP存在相似性, 可以借鉴一些LRP启发式算法的求解思想, 但二者并非同一问题.
Mathew等[39]定义该问题为HDP (heterogeneous delivery problem), 研究一辆货车支持一架无人机配送. Othman等[40]将HDP模型扩展成NW-TLSDP (no-wait transit last-stretch delivery problem)和TLSDP (transit last-stretch delivery problem)两个子问题, 前者禁止车辆在同一对接点处多次与无人机对接, 后者允许该情况出现.
上述研究为车辆和无人机提供了专门的对接点, 而Ferrandez等[41]将可行的对接点设置在客户节点处. 他们先利用
Othman等[44]在HDP模型的基础上, 假设车辆行驶路线已知, 以规划无人机路线为主要目标, 将问题细化成4种子场景: 第1、第2种场景假设无人机在车辆上取到货物后立即起飞, 但前者允许车辆在同一个节点等待无人机降落, 后者则不允许; 第3、第4种场景假设无人机在某个节点处降落后, 搭乘车辆的“顺风车”, 在另一个节点处起飞, 二者的区别与第1、第2场景一致. 考虑到车辆行驶路线已知, Boysen等[45]称该问题为DSP (drone scheduling problem), 研究如何安排无人机配送可使完工时间最小.
由于无人机载重量有限, 大部分研究假设无人机单程只能服务一个客户. Hu等[43]放宽了该约束, 假设无人机单次可以配送多个客户节点. Poikonen等[46]将该模式称为MVDRP (multi-visit drone routing problem), 并考虑了包裹的异质性, 即每个包裹重量不同.
在车辆支持无人机配送的扩展研究中, Karak等[47]研究了同时需要取送货的模型. Han等[48]考虑在特殊的救援场景中, 使用车辆搭载无人机和货物到达客户地点后, 由无人机垂直起飞将货物送达客户处.
当前有关车辆支持无人机配送的研究模型较为简单, 且研究侧重点在于对接点位置的选择, 这与LRP相似. 未来可以深入研究的方向如下: 1) 多车辆支持多无人机配送的场景. 现有研究集中于一辆车搭载无人机配送场景, 均假设车辆在对接点需回收完所有无人机才能行驶到下一个对接点. 在多车辆情形下, 车辆可以根据每架无人机的配送任务选择是否要在原地等待, 无人机也可以根据不同车辆的停靠情况选择合适的车辆降落. 这种场景对车辆和无人机的协同性要求较高, 但与协同配送仍有区别, 因为车辆支持无人机配送模式下, 车辆并不参与实际配送任务. 2)与前述1.1节和1.2节两种配送模式类似, 目前车辆支持无人机配送的扩展问题研究还非常少. 在带时间窗的配送问题中, 除了可以考虑客户时间窗外, 也可以进一步考虑各对接点含有服务时间窗的情况. 模型中还可以考虑一些不确定性因素, 例如: 车辆旅行时间变动、客户需求变动等, 从而使问题动态化, 也更加符合实际情况.
1.4 无人机支持车辆配送无人机支持车辆配送模式是指车辆执行配送任务, 由无人机作为辅助, 为车辆补货. 这种配送模式主要有两类适用场景: 一是车辆由于载重限制无法一次性完成订单配送, 需由无人机往返配送中心与车辆(或中转站)之间, 为车辆补充货物; 二是需求实时产生的场景, 如: 外卖平台、网络货运等. 车辆在配送过程中需要无人机及时补货, 以完成动态订单的配送.
Dayarian等[49]将该模式定义为VRPDR (vehicle routing problem with drone resupply), 提出无人机不断地从配送中心取货出发, 为配送途中的货车实时提供货物, 使货车能在给定的时间窗内配送更多的货物. 该模型具有高度动态性与实时性, 为了简化研究模型, 他们考虑了仅有一个配送中心、一辆货车和一架无人机的情况. Mccunney等[50]在模型中设置了一些转运点, 无人机先将货物运送到转运点, 然后在货车转运点处提货, 为指定区域内的客户服务. 他们根据订单到达时间、转运点数量、卡车数量和无人机数量的不同取值, 分别以农村和城市为例进行综合分析. 无人机支持车辆配送的研究非常少, 上述两篇文献在建模和求解方面也有较大差异: 前者聚焦于动态补货的场景, 本质上是在TSP的基础上考虑客户新增订单的动态要素, 通过无人机调度实现车辆的即时配送; 后者通过设置中转站, 提升配送效率, 类似于并行配送中Kim等[35]构建的局部模型. 无人机配送刚刚兴起, 相应的配套政策还不够健全, 短期内可能无法实现大规模无人机配送, 因此, 利用无人机支持车辆进行配送可能是一种较好的选择. 未来研究可以在Dayarian等[49]的模型基础上进一步考虑多车辆、多无人机和多配送中心的情况, 也可以根据客户订单的重量和尺寸考虑采用多机型的无人机组进行补货和调度.
1.5 混合模式配送混合模式是指采用两种及以上配送模式为客户节点提供配送服务.
Wang等[51]针对城市配送提出了融合两种配送方式的混合模式: 一方面采用TSP-D模式, 为环城公路沿线的客户节点配送; 另一方面, 利用车辆为城内剩余客户配送.
Wang等[52]提出了HTDD (hybrid truck-drone delivery)模型, 实现了车辆与无人机协同配送和并行配送两种模式的结合. 他们假设一部分客户由
|
图 4 混合模式配送 |
混合模式的研究目前还较少, 仍有较大的拓展空间. 例如: 城市中的客户位置分散, 可能分布于居民楼、写字楼、沿街店铺等各种地方, 若一些客户集中在同一个小区, 则可以采用车辆支持无人机的配送模式, 剩余客户可采用车辆与无人机协同配送的模式, 从而将问题分解为车辆与无人机协同配送和车辆支持无人机配送两种模式. 总之, 混合模式配送适合于更复杂的配送场景, 可根据具体问题进行设计.
2 构成要素车辆与无人机组合配送问题作为VRP的拓展问题, 其构成要素除了经典VRP定义的范畴外, 还具有一些特殊的属性. 因此, 首先根据VRP的特征, 从运载工具、道路网络、节点构成、弧段约束和优化目标等5个方面, 讨论车辆与无人机组合配送问题的经典要素; 然后, 结合车辆与无人机组合配送问题的特性, 提出速度比、无人机单程配送量和停靠策略3个拓展要素, 以全面分析其构成要素.
2.1 经典要素1) 运载工具.
VRP采用车辆作为运载工具, 建模时通常考虑其配送服务能力(行驶距离和容量两个方面). 在车辆与无人机组合配送问题中, 运载工具由车辆和无人机构成. 除少部分研究为使模型更符合实际情况, 限制了车辆的装载量[20-21, 33, 54-56]、行驶长度[48]或行驶时长[5, 33, 38], 大多数研究着重考虑无人机的配送服务能力. 由于无人机采用电池作为动力源, 续航能力较差, 限定无人机单程的飞行时长[18, 36, 46, 55, 57-59]或飞行距离[14, 22, 36, 43, 47, 60-61]的研究较多, 少量文献研究了无人机载重量对电池能耗的影响, 使无人机单程飞行时长或距离随载重量的变化而变化[28-29, 34-62]. 但是, 也有部分文献由于研究内容的侧重不同, 并未考虑电池容量的限制[23, 25, 37, 41]. 此外, 无人机由于机体较小, 还会受到装载量的限制. 一些研究为简化模型, 假设无人机单程只能装载一件包裹[13, 30, 40-42, 57, 63]; 也有文献研究同时考虑了无人机的装载量和货物的重量, 使无人机单程可以装载多件包裹[26, 46, 62, 64-66]. 与电池容量约束类似, 一些文献对无人机载重量不限[59, 66].
2) 道路网络.
道路网络包括节点和弧. 就节点而言, 传统VRP网络中一般只包含配送中心和客户, 但在车辆与无人机组合配送问题中, 除这两类节点外, 不同的配送模式可能产生其他类型的节点. 例如: 在协同配送和车辆支持无人机配送的模式下, 车辆和无人机会在专门设定的对接点对接; 在并行配送和无人机支持车辆配送模式下, 为扩展配送区域, 会设立专门的无人机站或中转站, 为无人机组或车辆提供货物存取等服务, 从而改善配送网络性能. 就弧而言, VRP中的弧通常用两节点之间的欧氏距离表示. 但车辆与无人机组合配送问题考虑到车辆沿地面道路行驶、无人机可沿直线往返两点之间, 因此规定了两类距离: 在任意两点之间, 车辆沿曼哈顿距离行驶, 无人机沿欧氏距离飞行. 也有研究针对城市区域的配送, 提出车辆和无人机均为曼哈顿距离.
3) 节点构成.
车辆与无人机组合配送问题的节点中, 除传统VRP网络中的配送中心和客户, 还可能包括为车辆与无人机的对接点, 以及为扩展配送范围而设定的无人机站和中转站. 配送中心可作为路径的起点和终点. 在协同配送问题中, 车辆搭载无人机从配送中心出发, 二者在完成最后一个配送任务后可一起回到配送中心, 也可以分别回到配送中心; 在并行配送问题中, 车辆单独从配送中心出发并最后回到配送中心, 无人机则可以多次往返于配送中心与不同客户之间; 在车辆支持无人机配送问题中, 车辆通常搭载全部无人机从配送中心出发, 并搭载全部无人机回到配送中心; 无人机支持车辆配送问题则需视情况而定. 客户节点具有一定的货物需求量, 其重量可能会决定是否只能由车辆配送[26, 46-47, 57, 62]; 同时, 客户可能还会有时间窗[32, 37, 48, 67]、取货需求等约束. 车辆与无人机的对接点用于无人机的起降、充电和取货, 这些节点通常是预先给定的, 只需根据实际配送情况选择部分即可. 无人机站和中转站可以突破现有运载工具的里程限制和载重限制, 进一步扩大配送范围, 一般是已知的, 仅少数文献研究了无人机站的选址问题.
4) 弧段约束.
车辆与无人机组合配送问题的弧段约束与VRP类似, 即每一条配送路径上的配送总量不能超过车辆或无人机的最大装载量. 一些文献根据实际情况或地区法律规定考虑了道路条件的限制, 比如: 部分区域车辆无法进入[28], 部分时段无人机禁飞[34]等.
5) 优化目标.
车辆与无人机组合配送问题的优化目标通常与时间、成本相关, 也有一些文献将配送距离、无人机数量等作为优化目标. 图 5给出了常见的优化目标的研究数量及分布情况.
在与时间相关的目标函数中, 不同的文献由于研究的模式和约束不同, 优化目标也略有区别. 最为常见的目标函数是最小化完工时间, 即车辆与无人机组合完成全部客户节点配送回到配送中心的时间[13, 19, 24, 35, 44-45, 50, 60, 62, 65, 68-70]. 无人机配送的主要优势在于反应速度更快, 可以减少配送时间, 提升配送效率, 因此完工最小化是一个合理的目标. 在Ferrandez等[41]车辆支持无人机配送的模型中, 完工时间是指车辆的行驶时间和每个集群内无人机的平均行驶时间之和. 此外, Daknama等[23]优化了无人机配送每件包裹的平均时间. Luo等[59]以最小化无人机飞行时间为目标函数. Kitjacharoenchai等[54]最小化所有车辆完成配送回到配送中心的总时间. Moshref-Javadi等[18]从客户满意度的角度出发, 将最小化客户等待时间作为优化目标.
|
图 5 优化目标的分布情况 |
此外, 成本也是一个重要的优化目标. 常见的成本优化有运输成本和运营成本. 运输成本[14, 16, 28, 32, 47, 62, 71-72]通常指车辆和无人机在运输过程中基于行驶距离产生的油耗、电力成本. 运营成本是在运输成本的基础上, 考虑一些其他因素, 例如: 劳动力成本[17]、车辆与无人机的等待成本[15, 73-74]、无人机的固定成本[29]、无人机站的固定成本[36]等.
还有一些学者提出了其他的优化目标, 如最小化总配送行驶距离[66-67]、最小化车辆与无人机的能源消耗[48]、最小化车辆数[48]、最小化车辆与无人机的能源消耗[48]、最大化客户数量[38]等.
一些研究对比了不同目标的优化模型. Schermer等[36]针对带有无人机站的PDSTSP模型, 分别构建了以成本最小化和以完工时间最小化为目标的数学模型. 之后, 他们又针对带有机器人站的混合配送模式[53], 分别构建了以成本最小化和以完工时间最小化为目标的数学模型. Ha等[74]针对TSP-D构建了以成本最小化和以完工时间最小化为目标的数学模型.
除了单目标优化以外, 少数文献也研究了多目标优化模型. Wang等[73]针对TSP-D构建了以最小化运营成本和完工时间为目标的双目标模型. Salama等[29]针对TSP-mD模型, 分别提出了以最小化完工时间和最小化成本为目标函数的单目标优化模型; 然后同时考虑这两个相互冲突的目标, 建立了双目标优化模型. Han等[48]提出了最小化车辆能耗、最小化无人机能耗和最小化车辆数量的三目标优化模型.
2.2 拓展要素1) 速度比.
无人机和车辆的速度, 以及二者的速度比决定了配送效率. 尤其是在协同配送和车辆支持无人机配送的模式下, 需要决定车辆与无人机在何处对接, 如果设定的位置不合理, 导致一方等待另一方的时间过长, 则会降低整个系统的效率. 因此, 考虑无人机与车辆速度比十分关键.
2) 无人机单程配送量.
当前多数研究为了简化模型, 规定无人机从车辆上起飞后只能为一个客户配送. 但实际上, 如果充分考虑无人机的续航、载重量, 可以实现无人机在单次航程中的多个节点配货, 从而进一步提高配送效率.
3) 停靠策略.
车辆与无人机的对接点包括配送中心、客户处或预先设定好的对接点. 停靠策略是指: 无人机完成配送任务后, 是否能在起飞的对接点处降落; 从车辆的角度看, 即把无人机放飞后, 能否在原地回收无人机. 在车辆支持无人机配送模式中, 一些研究要求车辆在对接点处回收完所有的无人机再行驶到下一个对接点, 而一些研究则允许无人机的降落点不同于起飞点. 文献[44]专门研究了这两种停靠策略的差异. 在车辆与无人机协同配送研究中, 一些研究考虑到城区配送不方便停车, 规定车辆必须在下一个节点回收无人机.
3 求解方法求解车辆与无人机组合配送问题的方法很多, 除了利用CPLEX、Gurobi等数学规划器对数学模型直接求解以外, 还包括精确算法、启发式算法、元启发式算法以及连续近似法等. 其中, 精确方法因能求得最优解而被广泛使用, 但通常求解时间长, 无法在可接受的时间范围内求解大规模问题. 还有一些文献利用启发式算法或元启发式算法求解, 能在较短的时间内得到满意解.
3.1 模型求解及精确算法车辆与无人机组合配送问题是TSP与VRP的扩展问题, 因此具有NP难特性. 基于数学模型利用CPLEX、Gurobi等数学规划求解器, 能够找到问题的最优解, 但是由于计算空间较大, 求解速度有限, 仅能处理小规模问题.
精确算法可以获取问题最优解, 但计算量大、耗时较长等, 即使部分算法, 例如: 分支定界(branch-and-bound, B&B)、分支定价(branch-and-price, B&P)等可以通过一些剪枝操作在一定程度上加速求解, 但仍难以在可接受的时间范围内获得最优解. 除B&B和B&P之外, 求解车辆与无人机组合配送问题常见的精确算法还有动态规划(dynamic programming, DP)、分支切割(branch-and-cut, B&C)、约束规划(constraint programming, CP)等. Bouman等[72]利用DP求解TSP-D模型, 并提出了一个适用于无人机配送的A*算法加速DP过程. Dell'amico等[57]改进了Murray等[13]提出的FSTSP数学模型, 分别提出了三下标模型和二下标模型, 重新构建目标函数, 并通过一组有效不等式加速B&C求解. 结果表明, 改进的数学模型可以显著提高下界, 并找到大多数算例的最优解. Schermer等[70]采用B&C算法求解了TSP-D模型. Poikonen等[58]采用B&B算法求解TSP-D模型. Roberti等[75]设计了基于集合划分的B&P算法求解TSP-D模型, 并针对主问题线性松弛后产生退化现象, 导致对偶变量取值不稳定, 通过约束对偶变量的范围来加速求解. Wang等[26]针对VRP-D构建了基于路径的数学模型, 并采用B&P求解.
3.2 启发式算法由于车辆与无人机组合配送问题具有NP难特性, 在面对较大规模的问题时, 采用启发式算法是一个较好的选择. 考虑到启发式算法通常根据问题特性设计, 本节针对不同的配送模式, 分别阐述启发式算法的有关研究.
3.2.1 协同配送启发式算法Murray等[13]为FSTSP模型设计了一种重新分配路线的启发式算法. 该方法首先利用多种TSP路径求解策略[76], 找到一条连接所有节点的车辆TSP路线; 然后选择符合无人机配送条件的节点, 将其从车辆路线中移除, 加入无人机路径中. 通过记录每一次移除再分配过程所节省的时间和路线长度来评价解的质量.
Agatz等[14]为求解TSP-D, 借鉴了Beasley[77]的先寻路-后分组(route-first, cluster-second, RFCS)方法, 提出了基于局部搜索(local search, LS)和DP的RFCS启发式算法. “寻路”过程的思路与Murray等[13]一致, 即连接所有节点构成一条初始TSP路线; “分组”过程是将TSP路线分割成车辆路线和无人机路线. 他们为“分组”过程设计了两种方法, 一是基于贪婪搜索的启发式分割策略, 二是基于DP的精确算法分割策略. 由于这两种方法依赖于初始TSP路径的质量, 引入3个LS算子改进TSP路径. Schermer等[55]基于RFCS方法, 提出两种启发式算法求解VRP-D模型. “寻路”阶段利用最近邻启发式(nearest neighbor heuristic, NNH)得到全部节点的初始车辆VRP路线. “分组”阶段分别设计了两步启发式(two-phase heuristic, TPH)和单步启发式(single-phase heuristic, SPH)策略: 前者基于LS算子改进初始车辆VRP路线, 随后针对每条车辆路线, 通过插入无人机路径形成VRP-D路径; 后者利用若干LS算子直接产生VRP-D解. 结果表明, 在大多数算例中, TPH得到的结果更好.
Yurek等[63]提出了一种求解TSP-D的精确方法, 并通过一个启发式过程加速求解. 该方法将问题分解为两个阶段: 第1阶段通过部分枚举生成TSP车辆路径, 每条路径为TSP-D提供一个下界; 第2阶段从最短车辆路径(最小的下界)开始, 以最小化车辆的总等待时间为目标, 确定最优无人机路径.
Murray等[19]针对mFSTSP提出了一种3阶段启发式算法: 在第1阶段, 根据客户的需求和位置信息, 将客户划分为无人机客户和车辆客户, 并确定车辆客户的最小数量; 在第2阶段, 根据无人机客户的数量, 确定每架无人机每次配送的起降点; 在第3阶段, 求解MILP模型, 以确定无人机起降和服务时间, 以及无人机配送次序. 在第3阶段结束后, 采用LS改善解的质量, 并增大车辆客户的数量, 扩大解空间, 找到更优解.
Kitjacharoenchai等[25]为解决TSP-D模型, 提出了ADI (adaptive insertion)启发式算法求解. ADI首先生成mTSP路径, 然后利用删除和插入算子构建mTSPD解. mTSP路径有3种构建策略, 包括遗传算法(ADI-GA)、
Murray等[13]为PDSTSP设计了一种启发式算法求解框架: 首先将客户集划分为车辆客户集和无人机客户集; 然后, 对车辆客户集规划类似于TSP的路线, 并类比PMS将无人机客户需求(作业)分配给无人机(机器); 最后, 利用一个改进策略重新分配客户到车辆客户集或无人机客户集, 以便更好地平衡车辆和无人机的运输活动.
Saleu等[61]设计了一个迭代两步启发式算法求解PDSTSP模型, 包括一个将解决方案转换为客户序列的编码步骤, 以及一个将客户序列分解为车辆路线和无人机路线的解码步骤. 解码问题表示为双准则最短路径问题(bicriteria shortest path problem), 并通过DP来实现.
Dell'Amico等[78]为求解PDSTSP模型设计了一种基于MILP模型的精确启发式算法. 首先利用启发式方法优化TSP车辆路线; 然后利用并行无人机调度(parallel drones scheduling, PDS)的MILP模型, 通过插入适当的无人机路径来调整车辆路线; 他们同时设计了迭代机制, 根据MILP模型重新优化车辆路径. 如果陷入局部最优, 则车辆路径中的部分节点会被移除, 并在新的搜索空间内继续迭代搜索.
3.2.3 车辆支持无人机配送启发式算法Luo等[59]提出了两种启发式框架求解一辆货车协助一架无人机配送的问题: 第1种是先用GA求解出连接所有客户节点的路径, 然后分割成车辆的子路径; 第2种是先用GA求解出连接所有对接点的路径, 然后根据客户节点的位置和无人机的飞行里程限制来规划无人机飞行路线.
Hu等[43]设计了一种3阶段启发式算法求解该问题: 第1阶段规划车辆路径, 先确定车辆必须通过的“关键点”以保证算法的可行性, 再设计一个成本函数来描述每条道路的质量, 并采用一种寻路算法, 连接所有的“关键点”, 形成车辆路径; 第2阶段规划无人机路径, 根据客户到车辆路线的距离对客户进行聚类, 再采用贪婪搜索构建初始无人机路径, 并通过预处理过程改进无人机路线, 保证其可行性; 第3阶段是优化过程, 采用动态调度策略调整无人机路径.
Poikonen等[46]为求解包含多架无人机的
元启发式算法因其通用性好、计算效率高等特点而在VRP相关的研究中得到了广泛应用. 用于求解车辆与无人机组合配送问题的元启发式算法主要有: 遗传算法(genetic algorithm, GA)、模拟退火算法(simulated annealing, SA)、贪婪随机自适应搜索算法(greedy randomized adaptive search procedure, GRASP)、自适应大邻域搜索法算法(adaptive large neighborhood search, ALNS)、变邻域搜索算法(variab-le neighborhood search, VNS)、禁忌搜索(tabu search, TS)等.
Peng等[65]提出了一个由种群管理、启发式种群初始化和种群培养3个部分组成的混合遗传算法(hybrid genetic algorithm, HGA), 求解TSP-mD模型. Sah[27]提出了一种伪节点插入法(pseudo node insertion method)来解决FSTSP的协同性, 并分别结合GA、SA以及贪婪搜索求解模型. 结果发现, 伪节点插入法与GA结合的效果最佳. Ha等[74]为求解TSP-D模型, 设计了一个基于分割算法、交叉算子和LS算子的HGA, 其中包括一种新的收敛恢复方法和自适应惩罚机制, 以及种群动态管理和自适应多样性控制过程, 以动态搜索可行解. Wang等[73]设计了改进非支配排序遗传算法求解多目标TSP-D模型.
Ponza[68]采用SA求解FSTSP模型. Liu等[62]为求解TSP-D模型, 先通过一个结合NNH和最小化成本的启发式策略生成可行解, 再利用基于TS的SA的算法寻求优化解. Moshref-Javadi等[79]为求解TSP-mD模型提出了一种基于SA和TS的混合算法.
Han等[48]采用一个改进的人工蜂群算法求解无人机协助车辆垂直配送的多目标模型.
Ha等[15]针对TSP-D模型, 设计了一种GRASP算法, 先从TSP路径中分解出TSP-D路径, 再利用LS算子优化TSP-D路径. 实验发现, GRASP算法得到的最优解质量优于Murray等[13]提出的算法, 但是计算时间更长. Marinelli等[31]改进了前者提出的GRASP框架, 用其求解VRP-D模型. Phan等[16]利用GRASP算法求解包含多架无人机的TSP-mD模型, 同时又提出一种ALNS算法. 实验结果表明, ALNS算法的效率优于GRASP.
Sacramento等[33]采用ALNS算法求解VRP-D模型; Moshref-Javadi等[18]基于ALNS算法框架求解TSP-mD; Freitas等[80]为求解FSTSP提出了随机变邻域下降的算法框架. 之后, Freitas等[81]又设计了一种混合VNS算法求解FSTSP和TSP-D模型. 首先, 通过TSP求解器确定TSP的最佳路线; 然后, 基于一个贪婪改进算法, 将客户从车辆路线转移到无人机路线中; 最后, 利用VNS算法进一步改进解的质量.
3.4 连续近似法连续近似法(continuous approximation, CA) 利用分析技术代替数值方法, 通过将问题简化为一组较小的设计参数集, 分析这些参数对问题结果的影响.
Campbell等[6]利用CA推导出TSP-mD的成本函数, 得到每条路线的最优车辆数、无人机数和单车搭载无人机数, 并将其与VRP模型进行比较. 结果表明, 无人机和车辆的运营成本以及客户的空间密度对总成本有显著影响. 此外, 单车搭载多架无人机可以节省大量成本, 特别是在中等密度的郊区. Carlsson等[82]使用CA对TSP-D进行分析, 发现车辆与无人机组合配送运行效率的提升与二者速度比的平方根成正相关. Li等[71]利用CA模型评估车辆支持无人机配送模式. 分析结果表明, 配送成本对六边形数、客户密度、成本比等关键参数较为敏感.
3.5 方法对比与总结综上所述, 车辆与无人机组合配送研究一般有两类研究点: 一类是决策问题, 主要的决策内容是车辆与无人机的服务节点和配送路径, 通常采用精确算法、启发式算法或元启发式算法来求解, 这类问题占绝大多数; 另一类是基于问题本身, 探究问题包含的参数对结果的影响, 一般使用连续近似法分析.
在决策问题中, 精确算法只适用于小规模路径规划问题, 当目标函数和约束条件较为复杂时, 精确方法很难在短时间内给出有效解. 启发式算法根据问题设计, 容易陷入局部最优; 元启发式算法有通用的求解框架, 其适用的问题也不同. 具体而言, 可将元启发式算法分为基于群体的元启发式算法和基于轨迹的元启发式算法. 前者以遗传算法、蚁群算法、粒子群算法为主, 每次迭代的对象为种群; 后者以各种邻域搜索算法为主, 每次迭代依赖于解的邻域. 协同配送更适合采用邻域搜索算法, 而并行配送和车辆支持无人机配送模式下, 基于群体的元启发式算法能一次提供多个解, 搜索效率更高. 但是在目前的文献中, 元启发式算法的应用并不多, 尤其是在并行配送模式下, 算法以精确算法和启发式算法为主. 鉴于元启发式算法具有良好的通用性, 能高效地求解大规模问题, 未来研究可以考虑如何改进算法, 提高求解效率. 此外, 一些扩展问题的相关算法也需进一步探究, 例如: 带时间窗的协同问题目前缺乏启发式求解方法, 如何快速构造可行的初始解进行迭代仍有探索空间.
4 测试数据集配送问题模型及算法的有效性需要实际案例数据或算例数据加以验证. 由于案例数据存在难以收集、普适性不强等问题, 学者一般通过构造一些测试数据作为算例来研究. 在车辆与无人机组合配送问题中, 数据构造需要考虑客户规模、客户分布、车辆与无人机数量比、车辆与无人机速度比等参数. 由于该问题研究历程较短, 国内外还没有统一的测试数据集. 表 2整理了目前应用较为广泛的测试数据集. 除了直接生成随机数据构成算例外, 还有一些学者在经典的TSP基准测试集TSPLIB基础上, 根据问题设置对数据进行适当改进, 从而构成其验证的算例[55, 61, 81].
|
|
表 2 常见的测试数据集 |
本文回顾了车辆与无人机组合配送问题相关研究, 根据车辆和无人机在配送过程中角色的不同, 将问题分为5类, 分别是: 车辆与无人机协同配送、车辆与无人机并行配送、车辆支持无人机配送、无人机支持车辆配送, 以及混合模式配送. 在对每类问题进行分析和归纳的基础上, 本文探究了组合配送问题的构成要素和求解方法, 并整理了常用的测试数据集. 目前, 车辆与无人机组合配送问题的研究尚在初步阶段, 不同的配送模式均有探索, 但研究深度不尽相同. 现有文献主要考虑了载重量、行驶时间、里程或时间窗等约束条件, 构建相应的数学规划模型, 并设计算法以高效地求解, 这为研究更复杂的车辆与无人机组合配送问题奠定了良好的基础. 随着智能运输和智慧物流的快速发展, 车辆与无人机组合配送问题还有一些值得探讨的问题和新的发展方向, 主要包括以下几个方面:
1) 进一步探究无人机性能对配送的影响. 现有文献对无人机特征的分析欠缺, 很多研究为简化模型而对无人机性能做了简化假设, 例如: 现有文献大多假设无人机单程只能配送一个客户, 无人机在电池限制下有固定的飞行时长或距离等; 同时, 只有极少数文献给出了无人机真实的性能参数. 在配送模型中考虑真实的无人机参数, 可以得出更有效和高效的解决方案. 因此, 未来研究应根据无人机的具体特性, 对问题做出更符合实际的假设. 例如: 考虑无人机在里程范围和荷载范围内单程服务多个客户的情况; 分析影响无人机续航的因素, 包括载重、风力、气温等; 也可以在此基础上进一步考虑无人机的载货尺寸, 判断多个客户的货物尺寸是否能够有效装载, 结合装箱问题(bin packing problem, BPP) 做深入探究.
2) 考虑无人机的安全性. 无人机飞行的政策和法规因地区而异. 在研究无人机配送时, 有必要考虑与安全相关的约束. 目前, 只有Jeong等[34]引入了禁飞区域的概念. 除了禁飞区以外, 还可以考虑最大允许飞行高度、允许飞行时段等因素. 此外, 无人机的不确定性也可以纳入研究范畴. 风力、气温对无人机的续航影响很大, 但是通常是未知的, 需要提前预测; 无人机在配送过程中可能因受到环境干扰, 出现机械故障等问题, 这些不确定因素同样影响无人机的配送安全性和可靠性, 因此, 研究包含无人机不确定因素的随机问题符合现实需求.
3) 考虑多要素融合和动态要素的研究. 目前, 大多数文献为了简化问题, 在构建模型时会忽略一些现实要素, 或考虑的要素较为单一, 仅有少量文献提出了基于时间窗、同时取送货、多配送中心的扩展问题. 而在实际配送过程中, 多个要素需要同时考虑的情况非常多, 例如同时考虑客户时间窗和取送货等, 因此, 多要素融合的组合配送扩展问题具有很强的应用价值. 此外, 目前的研究大多以考虑静态要素为主, 所有客户节点的需求已知且不变, 车辆与无人机各自以匀速状态行驶. 但在实际物流配送过程中, 可能会出现新增客户订单、配送地址变化和服务时间窗变化等情况. 在这样的环境下, 无人机可以利用自身优势, 快速进行实时调度和补货, 从而实现更为方便快捷和高效的配送. 目前, 只有Dayarian等[49]提出了一种针对动态客户请求的配送系统. 随着智能交通系统和新一代信息技术的发展, 各类动态信息已能及时获取, 未来可以研究在动态系统中使用无人机调度的问题, 并提出有效的算法来解决这个问题.
4) 考虑多模式组合的车辆与无人机组合配送问题模式研究. 现有车辆与无人机组合配送问题以单一配送模式为主, 仅有极少数文献考虑到现实需求, 将其中的两种模式进行结合, 构成混合配送模式, 从而实现更合理的配送服务. 由于物流配送的应用场景较为广泛, 不同地域、环境、客户需求、配送规模, 适合的配送模式也不同. 因此, 拓展更丰富的配送模式, 将不同模式组合以更好地为客户服务, 具有重要的现实意义.
5) 考虑目标多元化、多目标、多阶段的车辆与无人机组合配送问题研究. 现有关于车辆与无人机组合配送研究的优化目标以最小化完工时间和最小化成本为主. 在运营过程中, 还有很多其他更符合实际的考量也可以作为优化目标, 例如: 减少车辆与无人机的能源消耗、优化客户满意度等. 此外, 目前的研究以单目标模型为主, 而实际运营通常需满足多目标、多阶段的配送管理目标, 以实现物流配送过程中不同范围和级别的协同优化. 因此, 包含多目标、多阶段的优化模型有待深入研究.
6) 适用于大规模车辆与无人机组合配送问题的并行求解算法研究. 现有文献提出的算例客户数大都在100以下, 问题规模较小. 随着多核处理器的出现, 并行计算得到广泛应用, 大规模算例模型的求解计算量大, 对实时性要求高. 因此, 充分利用并行结构的优势, 加强并行算法研究, 设计出运算速度快、适用于大规模车辆与无人机组合配送问题的并行算法是一个值得深入研究的方向.
| [1] |
Rose C, Amazon's Jeff Bezos. Looks to the future[EB/OL]. (2013-12-01). https://www.cbsnews.com/news/amazons-jeff-bezos-looks-to-the-future/.
|
| [2] |
Stewart J. Google tests drone deliveries in project Wing trials[EB/OL]. (2014-08-28). https://www.bbc.com/news/technology-28964260.
|
| [3] |
Bryan V. Drone delivery: DHL "parcelcopter" flies to German isle[EB/OL]. (2014-09-24). https://www.reuters.com/article/us-deutsche-post-drones/drone-delivery-dhl-parcelcopter-flies-to-german-isle-idUSKCN0HJ1ED20140924.
|
| [4] |
顺丰科技. 顺丰无人机[EB/OL]. (2018). https://www.sf-tech.com.cn/product/uav.
|
| [5] |
36氪创投研究院. 无人配送领域研究报告[EB/OL]. (2020-08-17). http://www.199it.com/archives/1072522.html. (36Kr Research Institute. Unmanned delivery field research report[EB/OL]. (2020-08-17). http://www.199it.com/archives/1072522.html.) |
| [6] |
Campbell J F, Sweeney D, Zhang J. Strategic design for delivery with trucks and drones[R]. St Louis: Supply Chain Analytics Report SCMA (04 2017), 2017.
|
| [7] |
Otto A, Agatz N, Campbell J, et al. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey[J]. Networks, 2018, 72(4): 411-458. DOI:10.1002/net.21818 |
| [8] |
Viloria D R, Solano-Charris E L, Muñoz-Villamizar A, et al. Unmanned aerial vehicles/drones in vehicle routing problems: A literature review[J]. International Transactions in Operational Research, 2021, 28(4): 1626-1657. DOI:10.1111/itor.12783 |
| [9] |
Khoufi I, Laouiti A, Adjih C. A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles[J]. Drones, 2019, 3(3): 66. DOI:10.3390/drones3030066 |
| [10] |
任新惠, 岳一笛, 尹晓丽, 等. 无人机车辆组合物流配送路径规划探讨[J]. 飞行力学, 2020, 38(2): 88-94. (Ren X H, Yue Y D, Yin X L, et al. Theoretical discussion on the logistics route planning problem of UAV and vehicle combination[J]. Flight Dynamics, 2020, 38(2): 88-94.) |
| [11] |
Chao I M. A tabu search method for the truck and trailer routing problem[J]. Computers & Operations Research, 2002, 29(1): 33-51. |
| [12] |
Lin S W, Yu V F, Chou S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers & Operations Research, 2009, 36(5): 1683-1692. |
| [13] |
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. DOI:10.1016/j.trc.2015.03.005 |
| [14] |
Agatz N, Bouman P, Schmidt M. Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52(4): 965-981. DOI:10.1287/trsc.2017.0791 |
| [15] |
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. DOI:10.1016/j.trc.2017.11.015 |
| [16] |
Phan A T, Nguyen T D, Pham Q D. Traveling salesman problem with multiple drones[C]. Proceedings of the Ninth International Symposium on Information and Communication Technology. Danang City, 2018: 46-53.
|
| [17] |
Yoon J J. The traveling salesman problem with multiple drones: An optimization model for last-mile delivery[D]. Cambridge: Massachusetts Institute of Technology, 2018.
|
| [18] |
Moshref-Javadi 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. DOI:10.1016/j.apm.2019.11.020 |
| [19] |
Murray C C, Raj R. Themultiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones[J]. Transportation Research Part C: Emerging Technologies, 2020, 110: 368-398. DOI:10.1016/j.trc.2019.11.003 |
| [20] |
Wang X Y, Poikonen S, Golden B. The vehicle routing problem with drones: Several worst-case results[J]. Optimization Letters, 2017, 11(4): 679-697. DOI:10.1007/s11590-016-1035-3 |
| [21] |
Poikonen S, Wang X Y, Golden B. The vehicle routing problem with drones: Extended models and connections[J]. Networks, 2017, 70(1): 34-43. DOI:10.1002/net.21746 |
| [22] |
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. DOI:10.1016/j.trc.2019.06.016 |
| [23] |
Daknama R, Kraus E. Vehicle routing with drones[J]. 2017, arXiv: 170506431.
|
| [24] |
Bakir I, Tiniç G Ö. Optimizing drone-assisted last-mile deliveries: The vehicle routing problem with flexible drones[J]. Optimization-ouline.org, 2020, 1-28. |
| [25] |
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. |
| [26] |
Wang Z, Sheu J B. Vehicle routing problem with drones[J]. Transportation Research Part B: Methodological, 2019, 122: 350-364. DOI:10.1016/j.trb.2019.03.005 |
| [27] |
Sah B. Drone truck combined operation: Models and algorithm[D]. Binghamton: State University of New York, 2019.
|
| [28] |
彭勇, 黎元钧. 考虑疫情影响的卡车-无人机协同配送路径优化[J]. 中国公路学报, 2020, 33(11): 73-82. (Peng Y, Li Y J. Optimization of truck-drone collaborative distribution route considering the impact of epidemic situation[J]. China Journal of Highway and Transport, 2020, 33(11): 73-82. DOI:10.3969/j.issn.1001-7372.2020.11.009) |
| [29] |
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. DOI:10.1016/j.trc.2020.01.019 |
| [30] |
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. |
| [31] |
Marinelli M, Caggiani L, Ottomanelli M, et al. En route truck-drone parcel delivery for optimal vehicle routing strategies[J]. IET Intelligent Transport Systems, 2018, 12(4): 253-261. DOI:10.1049/iet-its.2017.0227 |
| [32] |
Di Puglia Pugliese L, Guerriero F. Last-mile deliveries by using drones and classical vehicles[C]. Proceedings of the International Conference on Optimization & Decision Science. Sorrento, 2017: 557-565.
|
| [33] |
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. DOI:10.1016/j.trc.2019.02.018 |
| [34] |
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. DOI:10.1016/j.ijpe.2019.01.010 |
| [35] |
Kim S, Moon I. Traveling salesman problem with a drone station[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 49(1): 42-52. DOI:10.1109/TSMC.2018.2867496 |
| [36] |
Schermer D, Moeini M, Wendt O. The traveling salesman drone station location problem[C]. World Congress on Global Optimization. Metz, 2019: 1129-1138.
|
| [37] |
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. DOI:10.1016/j.trc.2018.03.025 |
| [38] |
Ulmer M W, Thomas B W. Same-day delivery with heterogeneous fleets of drones and vehicles[J]. Networks, 2018, 72(4): 475-505. DOI:10.1002/net.21855 |
| [39] |
Mathew N, Smith S L, Waslander S L. Planning paths for package delivery in heterogeneous multirobot teams[J]. IEEE Transactions on Automation Science and Engineering, 2015, 12(4): 1298-1308. DOI:10.1109/TASE.2015.2461213 |
| [40] |
Othman M S B, Shurbevski A, Karuno Y, et al. Routing of carrier-vehicle systems with dedicated last-stretch delivery vehicle and fixed carrier route[J]. Journal of Information Processing, 2017, 25: 655-666. DOI:10.2197/ipsjjip.25.655 |
| [41] |
Ferrandez S M, Harbison T, Weber T, et al. Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm[J]. Journal of Industrial Engineering and Management, 2016, 9(2): 374-388. DOI:10.3926/jiem.1929 |
| [42] |
Chang Y S, Lee H J. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route[J]. Expert Systems with Applications, 2018, 104: 307-317. DOI:10.1016/j.eswa.2018.03.032 |
| [43] |
Hu M L, Liu W D, Lu J Q, et al. On the joint design of routing and scheduling for vehicle-assisted multi-UAV inspection[J]. Future Generation Computer Systems, 2019, 94: 214-223. DOI:10.1016/j.future.2018.11.024 |
| [44] |
Othman M S B, Shurbevski A, Karuno Y, et al. Routing of carrier-vehicle systems with dedicated last-stretch delivery vehicle and fixed carrier route[J]. Journal of Information Processing, 2017, 25: 655-666. DOI:10.2197/ipsjjip.25.655 |
| [45] |
Boysen N, Briskorn D, Fedtke S, et al. Drone delivery from trucks: Drone scheduling for given truck routes[J]. Networks, 2018, 72(4): 506-527. DOI:10.1002/net.21847 |
| [46] |
Poikonen S, Golden B. Multi-visit drone routing problem[J]. Computers & Operations Research, 2020, 113: 104802. |
| [47] |
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. DOI:10.1016/j.trc.2019.03.021 |
| [48] |
Han Y Q, Li J Q, Liu Z M, et al. Metaheuristic algorithm for solving the multi-objective vehicle routing problem with time window and drones[J]. International Journal of Advanced Robotic Systems, 2020, 17(2): 1-14. |
| [49] |
Dayarian I, Savelsbergh M, Clarke J P. Same-day delivery with drone resupply[J]. Transportation Science, 2018, 54(1): 229-249. |
| [50] |
Mccunney B, Cauwenberghe K. Simulation test bed for drone-supported logistics systems[D]. Boston: MIT SCM Capstone Project, 2019.
|
| [51] |
Wang C, Lan H J. An expressway based TSP model for vehicle delivery service coordinated with truck+UAV[C]. Proceedings of the 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC). Bari: IEEE, 2019: 307-311.
|
| [52] |
Wang D S, Hu P, Du J X, et al. Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones[J]. IEEE Internet of Things Journal, 2019, 6(6): 10483-10495. DOI:10.1109/JIOT.2019.2939397 |
| [53] |
Schermer D, Moeini M, Wendt O. The drone-assisted traveling salesman problem with robot stations[C]. Proceedings of the 53rd Hawaii International Conference on System Sciences. Hawaii, 2020: 1308-1317.
|
| [54] |
Kitjacharoenchai P, Lee S. Vehicle routing problem with drones for last mile delivery[J]. Procedia Manufacturing, 2019, 39: 314-324. DOI:10.1016/j.promfg.2020.01.338 |
| [55] |
Schermer D, Moeini M, Wendt O. Algorithms for solving the vehicle routing problem with drones[C]. Asian Conference on Intelligent Information and Database Systems. Dong Hoi City, 2018: 352-361.
|
| [56] |
Tavana M, Khalili-Damghani K, Santos-Arteaga F J, et al. Drone shipping. versus truck delivery in a cross-docking system with multiple fleets and products[J]. Expert Systems with Applications, 2017, 72: 93-107. DOI:10.1016/j.eswa.2016.12.014 |
| [57] |
Dell'amico M, Montemanni R, Novellani S. Drone-assisted deliveries: New formulations for the flying sidekick traveling salesman problem[J]. Optimization Letters, 2019, 1-32. DOI:10.1007/s11590-019-01492-z |
| [58] |
Poikonen S, Golden B, Wasil E A. A branch-and-bound approach to the traveling salesman problem with a drone[J]. INFORMS Journal on Computing, 2019, 31(2): 335-346. DOI:10.1287/ijoc.2018.0826 |
| [59] |
Luo Z, Liu Z, Shi J. A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle[J]. Sensors, 2017, 17(5): 1144. DOI:10.3390/s17051144 |
| [60] |
Kitjacharoenchai P, Min B C, Lee S. Two echelon vehicle routing problem with drones in last mile delivery[J]. International Journal of Production Economics, 2020, 225: 107598. DOI:10.1016/j.ijpe.2019.107598 |
| [61] |
Saleu R G M, Deroussi L, Feillet D, et al. An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem[J]. Networks, 2018, 72(4): 459-474. DOI:10.1002/net.21846 |
| [62] |
Liu Y, Liu Z, Shi J M, et al. Two-echelon routing problem for parcel delivery by cooperated truck and drone[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020(99): 1-16. |
| [63] |
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. DOI:10.1016/j.trc.2018.04.009 |
| [64] |
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. DOI:10.1016/j.trc.2020.02.030 |
| [65] |
Peng K, Du J Lu F, et al. A Hybrid genetic algorithm on routing and scheduling for vehicle-assisted multi-drone parcel delivery[J]. IEEE Access, 2019, 7: 49191-49200. DOI:10.1109/ACCESS.2019.2910134 |
| [66] |
Savuran H, Karakaya M. Route optimization method for unmanned air vehicle launched from a carrier[J]. Lecture Notes on Software Engineering, 2015, 3(4): 279-284. DOI:10.7763/LNSE.2015.V3.204 |
| [67] |
Kim G. Optimal vehicle routing for parcel delivery with considering two time periods[C]. Proceedings of the 2018 IEEE International Conference on Industrial Engineering and Engineering Management. Bangkok, 2018: 918-922.
|
| [68] |
Ponza A. Optimization of drone-assisted parcel delivery[D]. Padova: Università degli Studi di Padova, 2016.
|
| [69] |
Crian G C, Nechita E. On a cooperative truck-and-drone delivery system[J]. Procedia Computer Science, 2019, 159: 38-47. DOI:10.1016/j.procs.2019.09.158 |
| [70] |
Schermer D, Moeini M, Wendt O. A branch-and-cut approach and alternative formulations for the traveling salesman problem with drone[J]. Networks, 2020, 76(2): 164-186. DOI:10.1002/net.21958 |
| [71] |
Li Y S, Zhang G Z, Pang Z B, et al. Continuum approximation models for joint delivery systems using trucks and drones[J]. Enterprise Information Systems, 2020, 14(4): 406-435. DOI:10.1080/17517575.2018.1536928 |
| [72] |
Bouman P, Agatz N, Schmidt M. Dynamic programming approaches for the traveling salesman problem with drone[J]. Networks, 2018, 72(4): 528-542. DOI:10.1002/net.21864 |
| [73] |
Wang K Z, Yuan B, Zhao M T, et al. Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach[J]. Journal of the Operational Research Society, 2020, 71(10): 1657-1674. DOI:10.1080/01605682.2019.1621671 |
| [74] |
Ha Q M, Deville Y, Pham Q D, et al. A hybrid genetic algorithm for the traveling salesman problem with drone[J]. Journal of Heuristics, 2020, 26(2): 219-247. DOI:10.1007/s10732-019-09431-y |
| [75] |
Roberti R, Ruthmair M. Exact methods for the traveling salesman problem with drone[J]. Transportation Science, 2021, 55(2): 315-335. DOI:10.1287/trsc.2020.1017 |
| [76] |
Reinelt G. The traveling salesman: Computational solutions for TSP applications[M]. Berlin, Heidelberg: Springer Verlag, 1994.
|
| [77] |
Beasley J. Route first— Cluster second methods for vehicle routing[J]. Omega, 1983, 11(4): 403-408. DOI:10.1016/0305-0483(83)90033-6 |
| [78] |
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. DOI:10.1007/s10479-020-03562-3 |
| [79] |
Moshref-Javadi M, Lee S, Winkenbach M. Design and evaluation of a multi-trip delivery model with truck and drones[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 136: 101887. DOI:10.1016/j.tre.2020.101887 |
| [80] |
Freitas J C D, Penna P H V. A randomized variable neighborhood descent heuristic to solve the flying sidekick traveling salesman problem[J]. Electronic Notes in Discrete Mathematics, 2018, 66: 95-102. DOI:10.1016/j.endm.2018.03.013 |
| [81] |
Freitas J C D, Vaz Penna P H V. A variable neighborhood search for flying sidekick traveling salesman problem[J]. International Transactions in Operational Research, 2018, 27(1): 267-290. |
| [82] |
Carlsson J G, Song S Y. Coordinated logistics with a truck and a drone[J]. Management Science, 2018, 64(9): 4052-4069. DOI:10.1287/mnsc.2017.2824 |
| [83] |
Bouman P, Agatz N, Schmidt M. Instances for the TSP with Drone (and some solutions)[EB/OL]. (2018-03-20). https://zenodo.org/record/1204676.
|
| [84] |
Kitjacharoenchai. Drone-problem-sets[EB/OL]. https://github.com/pkitjach/Drone-Problem-Sets.
|
| [85] |
Ham. PDTSP DP[EB/OL]. https://drive.google.com/open?id=1ooWstfwP4wQ7qHAs_CY6otXZ904io0Ag.
|
| [86] |
Reinelt G. TSPLIB—A traveling salesman problem library[J]. ORSA Journal on Computing, 1991, 3(4): 376-384. DOI:10.1287/ijoc.3.4.376 |