Multi-depot Electric Vehicle Routing Problem With Drones Under Time-dependent Networks

Under the environment of reducing carbon emissions,electric vehicles will become the main delivery tool of terminal logistics and become the future development trend.However,due to the limitation of the cruising range,it is necessary to replenish power by charging or replacing batteries in the delivery process to complete the delivery task,which leads to low delivery efficiency and high cost.The drone has high delivery efficiency and low cost,but its endurance is limited and its load capacity is small,so it is usually unable to accomplish the long-distance,large-demand and multi-customer delivery tasks alone.Based on this,this thesis proposes the multi-depot electric vehicle routing problem with drones under time-dependent networks.In the delivery process,the vehicle serves as a temporary warehouse,and a charging and replacement platform for the drone,and is jointly distributed with the drone.In the study of multi-depot electric vehicle routing problem with drones under time-dependent networks,this thesis divides the road types in the delivery area,considering the continuous change of road speed,the different vehicle speeds of different types of roads at the same time,and the nonlinear relationship between the energy consumption of electric vehicles,load and speed.A mixed integer programming model is formulated with the goal of minimizing the total cost.In the model,the minimum state of charge of electric vehicles,the delivery capacity of drones,the cooperative relationship between vehicles and drones,and the number of customer visits are taken as constraints.According to the characteristics of the problem,a hybrid genetic algorithm with large neighborhood search(GA＿LNS)is proposed to solve the mathematical model.On the basis of the traditional genetic algorithm,the initial population is randomly generated using integer coding,the customers that the drone can serve are screened by the maximum loading capacity and flight distance of the drone,and then determines the routing of vehicles and drones to generate the initial solution.And embed 2 groups of destruction and repair operators for evolutionary operations.At present,there is no benchmark instance of this problem,and determining the vehicle routing is the key to solving the proposed problem.Therefore,this thesis uses GA＿LNS to solve the MDVRP benchmark example to test the performance of the algorithm.Then,an example of the problem in this thesis is designed to solve it and analyzed the impact of the number of drones carried by vehicles and the speed of the vehicle on the formulation of the distribution scheme.The research results of this thesis can enrich and expand the research field of vehicle routing problems,and provide a theoretical basis for transportation and logistics enterprises to optimize the decision-making distribution scheme.