Research On Electric Unmanned Vehicle Delivery Algorithm Considering Charging Scheduling

With the vigorous development of major e-commerce platforms and the rise of a new round of technological revolution,electric unmanned vehicles have shown strong development potential in the logistics industry with their unique advantages of high efficiency,low cost and zero emissions.The routing planning and charging scheduling problems of electric unmanned vehicles have become hot research issues in recent years,but most domestic and foreign studies have not limited the number of charging stations,and the objectives are to minimize the total distance travelled by unmanned vehicles,minimize the number of unmanned vehicles used,etc.This thesis investigates the routing problem of electric unmanned vehicles with limited number of charging stations,while the unmanned vehicles need to satisfy the loading capacity constraint and the battery power constraint,with the objective of minimizing the maximum electric unmanned vehicle distribution path length.Then construct a math-ematical model of this problem,design solution algorithms,and evaluate the algorithm performance.Firstly,a mixed integer programming model is established considering charging,and a dynamic programming algorithm is used,which can accurately solve the problem.It is proved that the time complexity of the proposed algorithm is(?).Then,the effectiveness of the proposed exact algo-rithm is verified by a Solomon example,which can obtain the optimal solution in a relatively short time for the small-scale examples.Secondly,according to the Christofides algorithm idea,the approximation algorithm is designed.A tree-based partitioning algorithm is first given,which divides all customers into at mostparts and allocates them to each vehicle,so that no electric unmanned vehicle visits the subset of customers without exceeding the loading capacity constraint.Then,a circular cover is obtained,starting from tree cover and gradually converted to,satisfying the battery power constraint.It is proved that the approximation ratio of the algorithm is at most(?),whereis the approximate ratio of the TSP problem,(?)represents the distanc(?)between the charging stationand the farthest customer point.The gap between the approximate solution and the optimal solution is also illustrated by solving the same examples with the designed approximate algorithm.Finally,genetic algorithm and simulated annealing algorithm are combined to improve the heuristic algorithm to solve the model and use the algorithm to plan the driving path and charging schedule of unmanned vehicles.Then,a numerical example is used to separately compare the min-max and min-sum driving distance results of the electric unmanned vehicle fleet,and the waiting time for the unmanned vehicles to be charged at a charging station is also taken into account in the exper-iment.Comparative analysis shows that the optimization results obtained by the improved algorithm are significantly superior to the simple genetic algorithm.In addition,the sensitivity analysis of rele-vant factors further illustrates the feasibility and rationality of the algorithm.The electric unmanned vehicles are well considered in this thesis,which satisfying a series of constraints.The routing schedule of unmanned vehicles are studied,minimizing the maximum distri-bution path length of electric unmanned vehicles.Three algorithms are designed to solve the routing problem.The research content can provide theoretical support for urban unmanned logistics path planning and improve logistics distribution efficiency.