《Drones》:Joint Fleet Sizing and Routing for Multi-Truck–Multi-Drone Collaborative Delivery
编辑推荐:
卡车-多无人机协同配送能够降低最后一英里成本,但车队规模与路径优化往往被分开处理,这使得在配送周期约束下难以实现资源与需求的匹配。本研究针对多卡车与多无人机协同配送场景,构建了一个集成车队规模与路径规划的两阶段优化框架。第一阶段采用排队模型与连续逼近,根据需求
卡车-多无人机协同配送能够降低最后一英里成本,但车队规模与路径优化往往被分开处理,这使得在配送周期约束下难以实现资源与需求的匹配。本研究针对多卡车与多无人机协同配送场景,构建了一个集成车队规模与路径规划的两阶段优化框架。第一阶段采用排队模型与连续逼近,根据需求强度和配送周期约束确定卡车与无人机的初始配置。第二阶段引入连续无人机投递与跨车辆回收以增强卡车-无人机协同的灵活性;在优化协同路径的同时,该框架根据路径可行性与设备利用率调整卡车与无人机的配置——增删资源——从而以最小化系统总成本为目标,实现运输能力与协同路径的联合优化。研究设计了节点-资源-流分离的三链编码以及自适应大邻域搜索-模拟退火算法(ALNS–SA)来求解模型。多尺度数值实验表明,与四种简化的车队规模策略相比,所提框架在中等和大规模算例中平均节省成本15.4%–15.5%。结果揭示了配送周期存在随节点规模移动的经济饱和点,以及车队规模与协同效率之间的非单调关系。该框架支持需求驱动的车队配置,并为成本有效的卡车-无人机最后一英里配送提供了操作指导。
论文解读:多卡车-多无人机协同配送的车队规模与路径联合优化
最后一英里配送是现代物流系统中成本最密集、运营挑战最大的环节,尤其在客户空间分散、订单量较小、时效要求严格的场景中,传统卡车配送受路网绕行和低停靠密度限制,而无人机受载荷、续航和服务半径限制,难以独立覆盖大规模区域。卡车-无人机协同配送结合了卡车的载运能力和无人机的速度灵活性,成为有前景的运营模式。然而,现有研究通常在给定车队规模下优化路径,将卡车和无人机数量视为外生输入,导致车队规模与路径优化分离,难以在配送周期约束下匹配资源与需求。更重要的是,车队规模与路径决策相互依赖:车队规模定义了可行路径空间,而高级协调机制如无人机多访问投递和跨车辆回收可能减少所需车队规模。因此,需要将车队规模与路径规划联合优化。
研究人员针对多卡车-多无人机协同配送系统,提出了两阶段“车队规模-路径优化”框架。第一阶段基于需求强度和配送周期约束,利用排队模型和连续逼近确定初始卡车和无人机数量;第二阶段在全局解空间中联合优化卡车路径、客户服务分配和无人机流转方案,并根据路径可行性和设备利用率动态调整车队规模,实现运输能力与协同路径的联合优化。研究设计了节点-资源-流分离的三链编码和自适应大邻域搜索-模拟退火算法(ALNS–SA)求解模型。多尺度数值实验表明,与四种简化车队规模策略相比,该框架在中等和大规模算例中平均节省15.4%–15.5%的成本。研究还揭示了配送周期经济饱和点随节点规模右移,以及车队规模与协同效率的非单调关系,为需求驱动的车队配置提供了操作指导。该研究发表在《Drones》。
主要技术方法包括:两阶段框架中,第一阶段采用连续逼近、M[X]/G/k批量到达排队模型和有限源闭合排队模型,将地理区域划分为子区域,根据需求强度、配送周期和等待约束求解局部最优车队规模;第二阶段设计了“节点序列-服务归属-无人机流”分离的三链编码,表示跨车辆无人机分配和连续流转,并采用ALNS–SA元启发式算法,嵌入动态车队修复机制,根据路径可行性和设备利用率增删卡车或无人机。数值实验使用50、75、100节点三种规模各5个随机实例;县级案例采用陕西汉中留坝县(73个客户节点)和略阳县(145个客户节点),数据由汉中邮政提供,卡车距离基于OpenStreetMap路网最短路径,无人机距离采用大圆距离。
研究结果分述如下:
配送周期对车队配置的影响:通过分析三种规模实例在配送周期T∈[0.5, 6]小时下的车队配置和固定成本变化,发现呈三阶段模式:T∈[0.5, 2]小时时车队需求高度敏感,延长T使卡车数和总成本下降;T∈[2, 4]小时时边际收益递减,50节点在T=3小时达到拐点,75和100节点延迟至4小时;T≥4小时后成本曲线平缓。据此选择T=3小时作为后续实验基线。
不同优化算法的比较:将ALNS–SA与Gurobi、变邻域搜索(VNS)、禁忌搜索(TS)、遗传算法(GA)在15个实例上比较,结果显示ALNS–SA在中等和大规模实例中平均成本更低、结果稳定性更好,并能有效控制配送周期违约;Gurobi和GA无法在时限内求解75和100节点实例,TS无法求解100节点实例,而ALNS–SA在60分钟内获得高质量解。
第一阶段验证实验:比较经验法、载荷下界法、车队过剩、车队短缺和所提排队论五种初始车队策略。结果表明,在75节点和100节点实例中,排队论策略比四种简化策略平均节省15.5%和15.4%的成本,但在50节点实例中成本高于载荷下界策略,说明小规模下排队模型估计偏保守。车队修复机制能双向调整初始偏差,即使初始配置不准确也能获得满足配送周期的可行解。
模型消融实验:在75节点实例上禁用核心机制,比较全模型(多访问投递+跨车辆回收)、同车回收、纯卡车和单次投递+同车回收四种模式。结果显示,无人机多访问投递是成本节省和车队压缩的主要机制,禁用后总成本上升43.1%,车队从(2, 4)扩展至(3, 6);跨车辆回收仅带来0.28%的直接成本改进,但增强了调度灵活性;相比纯卡车,全模型成本降低37.1%。
不同服务周期下的优化方案比较:在T=2、3、4、5小时下比较成本结构和协同深度,发现总成本随T延长先快速下降后趋平,拐点随规模右移。适度延长T激活无人机多访问投递潜力,可大幅压缩车队而不降低覆盖率;T≥5小时后系统退化为纯卡车模式,无人机覆盖率降至10%–19%。
敏感性分析:基于中等规模实例分别改变地理聚集强度、卡车-无人机速度比、会合等待阈值Zmax和重包裹比例。结果表明,节点过密或过疏均不利于协同;无人机速度略高于卡车时效果最佳;Zmax过窄降低覆盖率,过宽导致配送时间超限;重包裹比例低时协同效益明显,高时需增加无人机载荷或卡车数量。
县级案例分析:留坝县在T=4小时下初始配置2辆卡车和4架无人机,无需调整,最终成本2260.94元,无人机覆盖率39.7%;略阳县在T=5小时下初始4辆卡车和3架无人机无法满足要求,经修复调整为5辆卡车和5架无人机,最终成本4882.28元,覆盖率27.6%。两案例均满足会合和配送周期约束。略阳节点数为留坝1.99倍,但卡车行驶距离为3.89倍,表明山区道路绕行显著增加地面运输负担。
总结讨论部分指出,配送周期不仅影响车队规模,还影响协同深度。过短周期需要更多运力满足时效,适度延长可释放无人机多访问投递和跨车辆回收的节省潜力,但超过经济饱和点后进一步延长的成本收益甚微。不同节点规模对应不同的经济配送周期范围,因此管理者应根据节点规模和服务时效要求选择配送周期,再据此配置卡车和无人机数量。敏感性分析进一步表明,当无人机速度适中快于卡车、客户节点适度聚集、会合等待阈值与无人机任务时长匹配、重包裹比例较低时,卡车-无人机协同配送的成本优势更为明显。
研究结论翻译如下:本研究针对规定配送周期下的多卡车-多无人机配送问题,考虑无人机多访问投递和跨车辆回收,提出了两阶段“车队规模-路径优化”框架。第一阶段根据需求强度,利用连续逼近和批量到达排队模型确定初始卡车和无人机数量;第二阶段在全局解空间中联合优化卡车路径、客户服务分配和无人机转移方案,并根据路径可行性和资源利用率动态调整车队规模。为有效表示跨车辆无人机分配和连续转移,设计了“节点-资源-流”分离的三链编码,并结合动态车队修复机制的ALNS–SA算法求解。通过15个不同规模数值实例和留坝、略阳两个县级案例验证了框架和算法的有效性。算法比较表明,ALNS–SA在平均成本、解稳定性、计算效率和可扩展性方面表现均衡。与四种简化车队策略相比,所提基于排队的策略在中等和大规模实例中平均节省15.5%和15.4%的成本。县级案例表明,山区道路弯曲和绕行会增加地面运输负担,实际车队决策应显式考虑真实路网距离。多尺度和多周期实验揭示了配送周期、节点规模与车队规模之间的耦合规律,为管理人员提供了“按节点规模选配送周期、按周期配车队规模”的决策原则。研究局限性包括未考虑需求和时间不确定性、单基地和同质车队,以及恶劣天气、空域限制等动态条件,未来可扩展至多基地异构车队和动态运营场景。