Abstract: 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 cases with different customer scales, which verifies the correctness of the model and validity of the algorithm. In the numerical experiment section, we analyze the average number of customers served by the vehicle and the average delivery costs of different customer sizes. In addition, the sensitivity analysis of the maximum service duration of unmanned vehicles and vehicle travel speed on the delivery scheme decision is performed to illustrate the necessity of the proposed problem to consider the maximum service duration constraint of unmanned vehicles at parking nodes and the time dependence of the vehicle travel speed.
The conclusions are as follows: Firstly, the developed adaptive large-neighborhood algorithm adaptively selects destroy and repair operators according to their scores and weights, and introduces the inferior solution acceptance mechanism of the simulated annealing algorithm to accept inferior solutions with a certain probability. The experimental results show that the algorithm has strong optimization ability and can effectively solve the proposed problem. In addition, through the analysis of the maximum service time of unmanned vehicles and sensitivity to the speed of trucks, it can be seen that the delivery efficiency increases with an increase in the maximum service time. Logistics delivery enterprises should seize the development trend of “unmanned” terminal delivery. Enterprises need to use a reasonable collaborative delivery mode of trucks and unmanned vehicles according to the delivery status and the advantages and disadvantages of unmanned vehicles. Increasing the average number of service customers per truck under mass delivery is a way to reduce the average delivery cost of customers. Different vehicle speeds have a great impact on the formulation of delivery plans. When making delivery plans, companies should describe the speed of trucks as realistically as possible to avoid excessive use of vehicles and delivery personnel, resulting in a waste of delivery resources.
This paper is a further expansion of the truck and unmanned vehicle routing problem. In the future, the research will deepen the problem by considering factors such as dynamic demand, while optimizing the collaborative delivery model between trucks and unmanned vehicles. In addition, considering the charging demand of trucks and unmanned delivery vehicles is also a research direction.

Key words: electric truck, unmanned vehicle, vehicle routing problem, time-dependent, time windows, adaptive large neighborhood search

摘要： 针对卡车-无人车协同配送路径优化问题,综合考虑卡车行驶速度时间依赖性、客户时间窗的影响,以及速度、载重的变化对卡车能耗的影响等,以总配送成本最小化为目标构建卡车与无人车联合配送路径优化模型。根据问题特征,设计自适应大邻域搜索算法求解所建立的优化模型,该算法根据算子的历史表现和各阶段使用次数选择下一次迭代使用的算子,对原解进行摧毁重建操作,并引入模拟退火劣解接受机制以一定概率接受劣解。采用CPLEX和所设计的算法求解多组客户规模不同的算例,验证了模型的正确性和算法的有效性。在数值实验部分分析了不同客户规模下车辆可服务的平均客户数和客户平均配送成本,同时对无人车最大服务时长和车辆行驶速度对配送方案制定的影响进行灵敏度分析,说明所提问题考虑无人车在停靠站最大服务时长约束和车辆行驶速度时间依赖性的必要性。

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