Time-dependent Truck and Unmanned Vehicle Routing Problem with Time Windows
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 aver-age 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 collabora-tive delivery model between trucks and unmanned vehicles.In addition,considering the charging demand of trucks and unmanned delivery vehicles is also a research direction.
electric truckunmanned vehiclevehicle routing problemtime-dependenttime windowsadaptive large neighborhood search
国家科技期刊平台
NSTL
万方数据
