Modeling And Optimization Of An Electric Vehicle Routing Problem With Split Delivery

As increasingly widely used distributional tools in the field of logistics,electric vehicles have the advantages of saving energy,protecting environment,lowering noises,convenient utilization,and high efficiency of energy.Due to the limited endurance mileage of electric vehicles,when to recharge and which power station to choose are important issues when planning distributional routes.As an important branch of the vehicle routing problem,the thought of split delivery not only can effectively reduce the number of vehicles used in the distributional process and reduce the total distance,but also solve the problem that the demand of customers is greater than the maximum capacity of vehicles.Therefore,an electric vehicle routing problem with split delivery(EVRPSD)is studied in this thesis.The main research contents are as follows:(1)A large number of domestic and international journals and conference proceedings are consulted.The main attention is paid to traditional vehicle routing problems,the study status of electric vehicle in logistics,and the problems of split delivery.(2)Considering the route planning problem of electric vehicles and the thought of split delivery,the thesis proposed a problem of delivery that uses electric vehicles as a distributional tool and the demand of customers can be delivered in batches.The object is to use the fewest vehicles and minimize the total distance traveled by all vehicles.An integer programming mathematical model is established.Based on a large number of instances that are randomly generated,the correctness and speed of solution of the model are validated.(3)An ant colony algorithm is designed for the mathematical model established in content(2).The algorithm has two layers of loops.The outer loop is the basic structure of the ant colony algorithm.The inner loop is moving strategy of single ant.Each inner loop obtains a feasible solution to the problem.The algorithm introduced the attribute of cargo into the probability of transfer,and limited the number of splits according to the relationship between the current load of the ant and the demand of customer.A large number of randomly generated instances are solved to search the optimal combination of parameters,and the instances in content(2)are solved.The effectiveness of the algorithm is verified by comparing the experimental results.Finally,the effect of optimization with split delivery is analyzed.(4)A method for solving the electric vehicle routing problem with split delivery and time windows(EVRPSD-TW)is studied.This problem based on the issues studied in content(2)and add a hard time window.The object is to optimize the total time consumed and the total travel distance,it is converted into a single object by weighting method.A new mixed integer programming model is established.After the linearization of the objective function,the correctness of the model is verified.A new ant colony algorithm with time constraints is designed based on the algorithm in content(3).The selection and transfer of nodes take time as an important influencing factor.Finally,the effectiveness of the model and algorithm is verified based on a large number of randomly generated instances.