带时间窗的时间依赖型卡车-无人车协同配送路径优化  

Time-dependent Truck and Unmanned Vehicle Routing Problem with Time Windows

作　　者：范厚明 王琪 张跃光 范昊 FAN Houming;WANG Qi;ZHANG Yueguang;FAN Hao(Transportation Engineering College,Dalian Maritime University,Dalian 116026,China;School of Transportation and Logistics,Dalian University of Technology,Dalian 116024,China)

机构地区：[1]大连海事大学交通运输工程学院,辽宁大连116026 [2]大连理工大学交通运输学院,辽宁大连116024

出　　处：《运筹与管理》2024年第10期28-35,共8页Operations Research and Management Science

基　　金：国家社会科学基金后期资助重点项目(23FGLA010);国家社科基金应急管理体系建设研究专项(20VYJ024)。

摘　　要：针对卡车-无人车协同配送路径优化问题,综合考虑卡车行驶速度时间依赖性、客户时间窗的影响,以及速度、载重的变化对卡车能耗的影响等,以总配送成本最小化为目标构建卡车与无人车联合配送路径优化模型。根据问题特征,设计自适应大邻域搜索算法求解所建立的优化模型,该算法根据算子的历史表现和各阶段使用次数选择下一次迭代使用的算子,对原解进行摧毁重建操作,并引入模拟退火劣解接受机制以一定概率接受劣解。采用CPLEX和所设计的算法求解多组客户规模不同的算例,验证了模型的正确性和算法的有效性。在数值实验部分分析了不同客户规模下车辆可服务的平均客户数和客户平均配送成本,同时对无人车最大服务时长和车辆行驶速度对配送方案制定的影响进行灵敏度分析,说明所提问题考虑无人车在停靠站最大服务时长约束和车辆行驶速度时间依赖性的必要性。Unmanned delivery vehicles offer automation,safety and low cost,but their slow travel speed and low load capacity prevent them from efficiently completing high-volume delivery tasks alone.As the mobile warehouse and mobile charging station for unmanned vehicles,trucks can be combined with unmanned vehicles for delivery,which can not only overcome the disadvantages of unmanned vehicles,but also reduce delivery costs and improve delivery efficiency.This paper proposes a study about the time-dependent truck and unmanned vehicle routing problem with time windows.The research adopts the mixed truck and unmanned vehicle delivery in which both unmanned vehicles and the delivery truck can visit customers.Some deliveries like bulky goods are not suitable for unmanned vehicle delivery and must be made by the delivery truck.The truck carrying unmanned vehicles departs from the depot and is driven to parking nodes to launch unmanned vehicles.The vehicle must complete the delivery service within the customer’s time window and return to the depot by the latest moment requested.During the delivery process,the travel speed of the truck is time-dependent,and that of the unmanned vehicle is constant.Parking nodes are used for the truck release and pick-up of unmanned vehicles.A parking node allows trucks to visit many times and there is no limit to the number of launches of unmanned vehicles.For the truck and unmanned vehicle routing problem,an optimization model is formulated to minimize the total cost.According to the characteristics of the problem,an adaptive large neighborhood search algorithm is developed to solve the proposed problem.The algorithm selects the operator for the next iteration to destroy and repair the feasible solution based on operator performance and the frequency of use in each stage.In addition,the simulated annealing inferior solution acceptance mechanism is used in the algorithm to accept inferior solutions with a certain probability.We use CPLEX and the developed algorithm to solve several groups of c

关 键 词：电动卡车 无人配送车 路径优化 时间依赖型 时间窗 自适应大邻域搜索算法 

分 类 号：F252[经济管理—国民经济] TP18[自动化与计算机技术—控制理论与控制工程]