1 引言 在突发公共卫生事件的背景下,传统卡车配送不可避免会出现配送人员与收货人之间的接触,增加了安全风险。近几年各种“无接触”模式开始爆发式出现,基于无人配送的配送系统设计与应用受到了广泛关注。 无人配送多应用无人机、机器人等设备拓展传统卡车配送服务范围,取代配送终端人工上门服务,其应用历史可追溯至亚马逊公司在2013年提出的卡车无人机协同配送方案。送货机器人是无人配送中又一种常用设备。目前,Starship等公司开发的小型机器人可以在约定的时间内将订单传送给单个客户[1]。机器人在道路上行驶,大多数时候可以在自主模式下安全移动,或者在出现问题时切换到远程控制。一旦机器人到达门口,客户就会收到通知,然后取走货物。 最近文献中基于卡车无人机的协同配送备受关注。最初以单卡车单无人机组成的车组为任务执行单位执行配送任务,相关学术问题首先由Murray和Chu[2]进行研究。基于Murray和Chu[2]的研究,众多学者研究了单卡车单无人机配送路径问题[3-7],之后,在单卡车单无人机配送问题的基础上,一些学者对单卡车多无人机配送路径问题进行了研究[8~11]。其中,Luo Zhihao等[10]考虑多无人机旅行商问题的复杂性,将此问题分解为三个子问题,并提出了禁忌搜索算法和两级解决方案评估方法。Bruni等[11]虽然提出了一种基于逻辑的Benders分解的精确解决方案,但是他们假设无人机在同一个客户点发射和回收,这样,在无人机服务客户时,卡车需要浪费时间等待无人机。近年来,多辆卡车多架无人机组成的车组配送系统也受到了学者的关注[12~17]。其中,Kitjacharoen~chai等[16]放宽了卡车容量约束,建立了混合整数规划模型并设计了自适应插入启发式算法。Amine Mas~moudi等[17]扩展了Poikonen和Golden[9]的研究,考虑了无人机单次服务多个客户,虽然这是无人机技术的进步,但是每次服务一个客户,是更佳选择。此外,Amine Masmoudi等[17]假设无人机可以在不同的卡车之间发射和回收,在本文研究问题的应用背景下,将送货机器人和卡车以机组形式进行启动,更方便物流公司进行管理和轨迹追踪等。尽管已有文献试图在不同的情况和假设下有效地对卡车和无人机路线进行优化,但大多数文献将无人机发射和回收限制在客户点位置[2-17]。然而,卡车可以停在服务区等其他可行位置发射和回收无人机,UPS公司进行的卡车无人机配送系统的试点实验也证明了这一观点[18]。如果允许卡车在灵活的地点发射和回收无人机,卡车行驶的距离可能更短,无人机的利用率更高。此外,大部分研究假设卡车和无人机都可以为所有客户提供服务,但是在突发卫生安全事件背景下,假设所有的客户均由送货机器人进行服务,能最大程度上减少人员的接触。 相比于配送无人机,送货机器人的安全性更高,稳定性更强,不受城市低空空域管控限制,对不同天气条件及城市复杂交通流环境的适应性更强,因而更适用于人口密集城市区域的无人配送。与卡车和无人机协同配送类似,卡车机器人协同配送也已应用于实践中,亚马逊、京东等电商企业都在相关领域进行技术开发工作,并形成了各自的机器人技术体系,构成了卡车与送货机器人配送系统。本文针对卡车机器人协同配送中产生的应用问题展开研究。此配送系统中包含了多个由一辆卡车和多个送货机器人组成的卡车机组,卡车作为移动的仓库,携带送货机器人和货物从仓库出发,沿路网行驶,到达客户点附近的停靠点后,卡车上的送货机器人携带包裹,从卡车出发,向客户运送货物。送货机器人每次送货行程服务一个顾客,完成送货任务后,返回到卡车上[19,20]。卡车送货机器人联合配送系统运营过程中涉及路径规划、机器人调度等复杂问题,并在应用中出现了不同的调度模式。现有研究中,卡车在机器人出发执行配送任务时需原地等待机器人返回卡车,再前往停靠点执行下一任务[20.21]。为提高效率,减少卡车等待时间,本文选择了更为实际的一种调度方式,即送货机器人配送过程中,卡车不需在原地等待机器人返回,可沿路网继续向其他位置行驶,选取任意停靠点与机器人汇合,突破了卡车原地等待机器人的限制。相比现有研究而言,此配送过程更为复杂,需对卡车与机器人的平行独立运动及互相之间的关联进行深入分析与优化。 本文研究的多个由一辆卡车和多个送货机器人组成的卡车机组的配送问题,考虑了送货机器人在停靠点与卡车分离和汇合,减少了人员接触。此外,本文假设在送货机器人配送过程中,卡车不需要在原地等待机器人返回,可沿路网继续向其他位置行驶,选取任意停靠点与机器人汇合,突破了卡车原地等待机器人的限制。上述考虑因素导致决策优化维度多,解空间变大,同时增加了卡车和送货机器人的时间关联约束,从而使得卡车和送货机器人的配送路径难以高效规划。因此,本文以卡车送货机器人联合配送系统为研究对象,将复杂的多卡车机组的配送路径问题数学化并提出运营决策,研究了卡车和送货机器人联合配送模式下配送任务在不同卡车机组之间的分配决策、机器人任务分配决策以及卡车、送货机器人配送路径规划决策,运用数学规划方法建立数学模型。此外,为了高效求解数学模型,本文设计了变邻域搜索算法,并通过数值实验和敏感性分析进一步分析系统配置等问题。大量数值实验验证了算法的有效性和高效性,卡车数量和停靠点数量变化的敏感性分析,为管理者决策提供建议。