Research On Electric Vehicle Routing Problem With Multi-trip

With the improvement of the economic level and the improvement of the national living standards,the number of car ownership in China is increasing year by year,and a large number of fuel vehicles have brought pollution problems in urban development.Unlike other urban pollution sources,pollution caused by automobiles cannot be solved by simply space transfer and purification devices.To solve this problem,countries around the world and automobile manufacturers have begun to implement the ban on traditional fuel vehicles and the technological innovation of new energy vehicles.New energy vehicles,represented by pure electric vehicles,will gradually replace traditional fuel-driven passenger and commercial vehicles,and even some logistics freight vehicles,for the foreseeable time.Electric vehicles have the disadvantages of battery life,and the application of electric vehicles as logistics vehicles brings certain challenges to the path planning of enterprises.This paper starts from the actual operation of the enterprise,considers the situation of using the electric vehicle in the logistics distribution behavior and other constraints such as capacity constraints and time constraints,and considers the situation of multiple installations of the vehicle,and considers the multi-loop and time window.The mathematical model of electric vehicle routing problem and the algorithm based on column generation are designed,which is also the main highlight of this paper.Firstly,the article reviews the necessity and feasibility of using electric vehicles to engage in logistics behavior,and introduces the research on vehicle routing optimization,which prepares the basics for the follow-up of the article.The arc-based mathematical model of the problem is constructed through reasonable assumptions and mathematical descriptions of the actual requirements of the enterprise.In order to solve the problem on a large scale,the arc-based mathematical model is transformed by Danzig-Wolf decomposition,and the column generation algorithm is used to solve the problem.In the process of solving the column generation sub-problem,the depth-first labeling method based on the dynamic programming is designed,and some heuristic constraints are used to accelerate it.However it takes a long time solving by labeling,an ant colony algorithm architecture is designed to solve the problem.Ant colony path-finding algorithm with resource constrained shortest path problem.In the case analysis part,through the several examples,the quality and efficiency of the algorithm are compared.The validity of the problem hypothesis is also verified.The problems studied in this paper have reference significance for enterprise development and operation.The algorithm proposed in this paper can effectively solve this problem.