车辆与无人机协同配送路径规划问题研究进展

随着电子商务产业的飞速发展，物流行业业务量持续增长。物流行业业务量的增长对物流企业的调度能力提出了更高的要求。同时，像智能物流机器人、自动化分拣包装设备、无人驾驶车辆以及无人机等以新一代信息技术为支撑、运作管理更为高效、货物运输更为便捷的智慧物流在我国快速发展，为物流业转型升级提供了更多可能。在此背景下，一种车辆与无人机协同进行配送的模式受到了物流行业和学术界的广泛关注，车辆与无人机组合模式如图1所示。车辆与无人机协同进行配送的模式有效地结合了无人机速度快、通行能力强的优势以及传统运输车辆优秀的载重、续航能力，为物流配送降本增效提供了新的解决方案。本文将从数学模型以及求解算法两个方面对车辆与无人机协同配送路径规划问题进行综述。

 

图1 车辆与无人机组合模式示意图   

 

1 车辆与无人机协同配送路径规划模型

图2 车辆与无人机协同配送模式示意图   

 

车辆与无人机协同配送路径规划问题主要分为单车辆与无人机协同配送路径规划问题(Traveling Saleman Problem with Drones, TSPD)和多车辆与无人机协同配送路径规划问题(Vehicle Routing Problem with Drones, VRPD)。Murray和Chu[1]首先对车辆与无人机协同配送车辆路径规划问题展开研究，提出了无人机协同配送的旅行商问题(the Flying Sidekick Traveling Saleman Problem, FSTSP),并建立了以最小化总配送时间为目标的混合整数规划模型(Mix Integer Progroming, MIP)。在其研究中车辆与无人机协同进行物流配送，车辆在运输包裹的同时，作为一个承担无人机发射、回收以及更换电池任务的移动平台。此外，配送任务由一辆仅配备一架无人机的车辆承担，且无人机单次发射仅能服务一个客户，无人机可以在某个客户点处从车辆进行发射，并在完成计划的配送任务之后，在另外一个与发射点不同的客户点处与车辆进行汇合。车辆与无人机协同配送模式如图2所示。该模型的提出受到了国内外学者的广泛关注，随后的相关研究基于不同的应用场景分别从优化目标、约束等角度对于车辆与无人机协同配送路径规划模型进行了拓展。

 

1.1 优化目标

在关于车辆与无人机协同配送路径规划模型的相关研究中，从优化目标来看，最常见的优化目标主要包括配送时间、配送成本以及碳排放量等。

 

针对车辆与无人机协同配送路径规划问题，Murray和Chu [1]建立了以最小化总配送时间为目标的混合整数规划模型，即使车辆和无人机完成对所有客户的配送服务后回到配送中心的时间最短。Wang等[2]同样以最小化总配送时间为目标对车辆与无人机协同配送路径规划问题进行了研究，其研究结果表明，与仅使用车辆进行配送相比，无人机的使用可以节省大量时间。Luo等 [3]同样以最小化总配送时间为目标对车辆与无人机协同配送的路径规划问题展开了研究，其研究中考虑了车辆可以搭载多架无人机且无人机单次发射可以服务多个客户的情况，与无人机每次发射仅能服务单个客户相比，允许无人机每次发射可对多个客户进行服务可有效减少配送时间。

 

Sacramento等[4]基于Murray和Chu提出的FSTSP模型建立了在满足容量和时间约束的前提下以最小化总成本为目标的混合整数规划模型。其中，总成本包括车辆和无人机的配送成本。此外，在考虑车辆和无人机的配送成本的基础上，高娇娇和郭秀萍[5]进一步将车辆、无人机的固定成本纳入考虑。而Ha等[6]则将无人机和车辆在客户点处相互等待的时间作为惩罚成本纳入到总成本当中。

 

此外，Chiang等[6]和Kuo等[8]还以减少碳排放为优化目标对车辆与无人机协同配送路径规划问题展开了研究，证明了无人机参与配送对于减少碳排放的积极作用。据统计，交通运输业产生的碳排放占全球碳排放总量的14%,而公路运输则占据了交通运输业碳排放的四分之三[9,10]。因此，减少物流配送过程中产生的碳排放具有重要意义。

 

1.2 约束条件

约束条件的设置是对问题背景环境的复现，是模型中不可或缺的部分。由于应用场景的不同或是出于简化模型的目的，各项研究中约束条件也不尽相同。

 

在车辆与无人机协同配送的路径规划问题中，所使用的车辆与无人机的数量对相关约束的构建有着重要影响，是研究人员们关注的重点。在Murray和Chu[1]的研究中，仅由一辆搭载一架无人机的车辆承担配送任务，且无人机每次发射只能对一个客户进行服务。随后的相关研究从多个角度进行了拓展，如增加车辆可搭载的无人机数量[11,12]或是假设无人机每次发射可以对多个客户进行服务[3,13]等。而Wang等[2]进一步将FSTSP问题拓展为多车辆与无人机协同进行配送的车辆路径规划问题，该项研究中由一队搭载无人机的车辆承担配送任务。

 

在车辆与无人机协同配送的路径规划问题中，如何构建无人机的续航模型也是车辆与无人机协同配送路径规划问题中备受关注的一点。在现有研究中通常使用最大飞行距离、最长续航时间以及依赖于包裹重量的线性能量消耗模型[14]对无人机的续航进行表征，而这些过于简化的续航模型可能会对无人机的续航能力带来错误的估计。Murray等[11]在其研究中引入了Liu 等[15]推导的以无人机包裹重量以及无人机飞行速度为自变量的非线性能量消耗模型对无人机的续航能力进行表征。其对比了上述四种不同的无人机续航模型，发现相较于非线性能量消耗模型，应用其它几种续航模型有较大的风险导致求解结果为不可行解。

 

此外，在实际的物流配送场景中，客户可以接受服务的时间通常位于一个时间区间内，该时间区间可以用时间窗约束进行表示[16]。目前，针对考虑时间窗约束的车辆与无人机协同配送路径规划问题的研究较少。针对该问题，Kuo等[17]建立了一个混合整数规划模型，其研究中假设车辆、无人机对客户进行服务的时间需要位于客户点的时间窗内。其研究结果表明，对于时间窗的考虑会使得配送成本进一步增加，但相比于仅使用车辆的配送模式，无人机的使用可以有效降低配送成本。

 

2 求解算法

2.1 精确算法

部分文献采用精确算法对车辆与无人机协同配送路径规划问题进行求解，包括采用Gurobi、CPLEX等商业求解器对车辆与无人机协同配送路径规划模型直接进行求解、设计分支定界算法(branch-and-bound algorithm, B&B)以及设计动态规划(Dynamic Programming, DP)方法等。车辆与无人机协同配送的路径规划问题属于NP-hard问题，精确算法在小规模算例的求解上表现出色，可以确保找到最优的解决方案，但在大规模问题上的计算复杂度较高，需要大量的计算资源。在针对车辆与无人机协同配送路径规划问题的相关研究中，常使用商业求解器对所构建数学模型在小规模算例上进行求解，并将求解结果作为对照以验证所设计算法的精确性和高效性。而Wang等[18]开发了能够找到高质量解的分支定价算法(Branch-and-Price algorithm, B&P)来求解车辆与无人机协同配送路径规划问题。而Bouman等[19]和Tang等[20]则分别采用动态规划和约束规划(Constraint Programming, CP)方法来求解车辆与无人机协同配送路径规划问题。

 

2.2 启发式算法

对于大规模问题，若采用精确算法求解，即使花费大量时间也很难找到可行的解决方案。与精确算法相比，启发式算法可以在较短的时间内为大规模问题找到的近似最优的解决方案。Ha等[6]设计了一种贪婪随机自适应搜索算法(Greedy Randomized Adaptive Search Procedure, GRASP)用于解决优化目标为最小化总配送时间或最小化总配送成本的车辆与无人机协同配送路径规划问题，该算法可有效求解客户数量多达100个的大模型算例。Poikonen等[21]设计了四种基于分支定界算法的启发式算法用于求解车辆与无人机协同配送路径规划问题，针对包含200个节点的大规模算例，该算法的平均求解时间不超过15秒。而Sacramento等[4]提出了一种自适应大邻域搜索算法(Adaptive Large Neighborhood Search, ALNS)用于求解车辆与无人机协同配送路径规划问题，该算法通过采用多种针对问题特性设计的破坏算子和修复算子对当前解进行重构以改进当前解。针对考虑时间窗的车辆与无人机协同配送路径规划问题，Kuo等[17]提出一种变邻域搜索算法(Variable Neighborhood Search, VNS)对该问题进行求解。研究结果表明，相对于Sacramento设计的自适应大邻域搜索算法，变邻域搜索算法具有更好的性能，且两者间的差距随着算例规模的增大而增大。

 

3 总结

本文综合车辆与无人机协同配送路径规划问题的相关研究，回顾了车辆与无人机协同配送路径规划问题的常见优化目标，包括配送时间、配送成本和碳排放量等，探究了车辆与无人机协同配送路径规划模型的约束中考虑的影响因素，如车辆与无人机的数量、无人机续航模型以及时间窗。此外，基于已有文献回顾了用于求解车辆与无人机协同配送路径规划问题的常见算法，包括精确算法和启发式算法。

 

综合来看，车辆与无人机协同配送路径规划问题的研究为提升物流企业的调度能力，使其能高效地进行路径规划提供了重要的理论支持。在今后研究中应关注如何设计适用更广泛场景的数学模型以及更灵活高效的算法。此外，机器学习算法已经成功应用于车辆的路径规划问题当中，而现有针对车辆与无人机协同配送路径规划算法的研究中大多都是采用精确算法或者启发式算法进行求解，机器学习算法在车辆与无人机协同配送路径规划问题中的应用有待进一步加强。