摘要：研究带软硬时间窗的车载无人小车协同配送路径问题，卡车在停靠点释放回收无人小车，在考虑包裹质量、体积的基础上，小车必须在硬时间窗范围内为客户配送包裹，且在小的软时间窗外服务时带有惩罚成本。针对该问题，构建以行驶成本和时间窗惩罚成本之和最小为目标函数的整数规划模型，并在大规模邻域搜索算法（Large Neighborhood Search，LNS）的基础上引入一种自适应机制，设计一种改进的自适应大邻域搜索算法（Adaptive Large Neighborhood Search，ALNS）进行求解。对比ALNS、LNS和遗传算法（Genetic Algorithm，GA）在调整后的Solomon算例中的求解表现。结果表明，所提算法的解质量更好，相对于LNS、GA的平均优势分别是14.6%、32.4%，且能在更短的时间内得到最优结果，求解效率良好。所设计的算法能解决带软硬时间窗的车载无人小车协同配送路径问题。
关键词：车载无人小车,时间窗,路径优化,多行程协同配送,自适应大邻域搜索算法
0引言
随着科技的飞速发展，无人小车逐渐走入人们的视野，无人配送也成为了现实，这极大减轻了末端物流人员的工作负荷。在无人小车参与末端物流的情况下，物流体系框架维持着“配送中心－快递站点－无人小车”的三级结构。
随着城区租金的上涨，快递站点的维持成本也随之上涨，取消快递站点则有利于降低成本。然而，配送中心通常位于郊区，距离城区较远；无人小车续航有限，无法进行从郊区到城区的长距离行驶；卡车因城市规划在部分城区行驶受限。对此，廖毅等[1]提出一种车载无人小车的配送模式，即卡车搭载无人小车前往城区的停车点，于多个停车点释放或回收无人小车，小车则从停车点出发前往客户位置进行配送服务，完成后前往一停车点与卡车汇合并被回收。这种配送模式是具备协同性的多行程两级车辆路径，不仅扩大了无人小车的服务范围，还能帮助末端物流实现降本增效。廖毅等的研究未考虑客户包裹质量和体积，此外，现实中客户会期望在提前知晓的时间范围内被服务，即便有延误，延误时间也需在客户可接受的范围内。因此，为更贴近现实，有必要研究考虑客户包裹质量、体积和时间窗的车载无人小车协同配送路径问题。
车载无人小车协同配送路径问题是两级车辆路径问题（Two-Echelon Vehicle Routing Problem，2E-VRP）的变体，同时结合了多行程车辆路径问题（Multi-Trip Ve⁃hicle Routing Problem，MTVRP）的特点。国内外学者对2E-VRP和MTVRP的关注也比较高。2E-VRP问题的研究有考虑车辆固定成本、时间窗惩罚成本和油耗成本的[2]，加入驾驶员工资成本、燃油成本和装卸成本考虑因素的[3]，加入多车型约束的[4]，允许同时取送货的[5]，考虑同时取送货和碳排放成本的[6]，考虑车辆固定成本、运输成本、制冷成本和客户满意度的[7]，加入客户分类考虑的[8]。Boysen等[9]提出卡车作为移动基地，携带自主机器人进行最后一公里包裹配送的模式，卡车在一地点派出自主机器人前往客户点服务后需等待机器人回来后再前往下一地点。Liu等[10]研究了混合车辆的2E-VRP，传统货车作为一级车辆既进行配送服务也负责释放和回收自主配送车，自主配送车作为二级车辆只进行配送服务，且起点和终点均在同一位置。Anderluh等[11]提出混合货车和货运自行车的配送模式，货车和货运自行车从不同的车库出发，货车负责配送服务和给货运自行车补货，货运自行车则接收货物并配送给其车库附近的客户。Jennings等[12]提出人行道自主送货机器人和特殊送货车的组合来交付包裹的模式。YU等[13]提出大车携带小型无人车进行配送的模式，大车负责接送小型无人车，只有小型无人车前往客户点服务，每个大车与小型无人车的组合只有一次行程。MTVRP的研究有考虑取送货的[14]，考虑车辆成本、充电成本以及同时取送货的[15]，加入异构车辆考虑的[16-17]，以及加入了配送中心定位问题考虑的[18]。宋慧心等[19]和吴廷映等[20]研究了考虑多时间窗的MTVRP，即每个客户提供多个可接受货物的时间窗，配送过程中从中选择一个时间窗范围对其进行服务。然而，具备协同性的多行程两级车辆路径问题研究还比较少。
鉴于此，为更贴近现实，本文在车载无人小车协同配送路径问题的基础上加入客户包裹重量、体积以及无人小车续航约束的考虑，并且引入一种软硬结合的客户服务时间窗约束，针对此问题构建目标函数以行驶成本和时间窗惩罚成本之和最小的整数规划模型，并设计一种改进的自适应大邻域搜索算法进行求解，通过数值实验进行算法对比，证实了所设计算法的有效性。
文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/ligonglunwen/81026.html
