Research On Location And Routing Problem Of Electric Vehicle Recharging Station Based On Space-time-energy Network

Under the guidance of the new development concept which means “innovation,coordination,greenness,openness,and sharing”,China’s economic and social life is developing steadily.Electric vehicles have the characteristics of clean energy and low pollution.At the same time,due to their energy consumption characteristics,they need to be charged at recharging stations in the process of traveling,so as to expand their travel range and time.In order to solve problems such as the shortage of electric freight vehicles,the insufficient deployment of recharging stations,the circuitous route of vehicles,and the“anxiety” of mileage,many logistics companies hope to build an electric vehicle freight service network with recharging stations at a reasonable cost,so as to provide customers with high-quality transport services.The network needs to solve two key problems at the same time.One is how to optimize the location of alternative recharging stations according to factors such as vehicle routes.The other is how to optimize the path of electric vehicles based on customer needs,recharging station location,time-varying travel time of arcs and other relevant factors.In view of this,according to the practical problems mentioned above,this paper conducts research on the location-routing problem of electric vehicle recharging station based on space-time-energy network.The specific content is as follows:To describe the electric vehicle network for urban distribution.The paper implements analysis of characteristics of passenger and freight electric vehicle,as well as application scenarios of freight electric vehicles in urban distribution field.The paper also describes the demand arc corresponding to the demand node,and takes Nanjing as an example to explain the influencing factors of site selection.According to the analysis above and the analysis of the electric car recharge mileage and energy consumption,the basic theory of electric network is built.To establish the space-time-energy network.Based on the space-time network,the STE network is constructed by adding the “energy dimension”,which is used to describe the variation of energy in the process of traveling and charging.The steps of STE network construction include: dimensional discretization and establishment of node sets,construction of recharging arcs,setting of various arc sets and arc costs,and inputting parameters.In addition,STE network provides the network foundation for establishment of the model.To build the electric vehicle recharging station location-routing optimization model.In this paper,various practical problems in urban distribution are abstracted as the location-routing problem under STE network.A 0-1 integer programming model with the objective function of the minimum total travel cost is established.The constraints of the model include the flow balance constraints of each node,recharging station vehicle capacity constraints,recharging station construction cost constraints,customer demand satisfaction constraints,vehicle load constraints and binary constraints of decision variables.Finally,the constraint characteristics and scale analysis are performed to provide a basis for the selection of the algorithm.To use the Lagrangian relaxation and decomposition algorithm for the model.Aiming at the difficult constraint and the coupling constraint of the original model,the corresponding Lagrangian multipliers of the recharging stations’ capacity and the demand arcs are introduced to construct the relaxation model.The dual problem of the relaxation model is decomposed into two subproblems.To use dynamic programming algorithms for solving the subproblems.After Lagrangian decomposition,the two subproblems are the multi-vehicle routing problem with recharging stations and the recharging station location problem.The essence of the two subproblems are vehicle routing problem and knapsack problem.The dynamic programming algorithm one is designed to solve the recharging station location problem.Meanwhile,the dynamic programming algorithm two which includes the improved label-correcting algorithm,is designed to solve the multi-vehicle routing subproblem with recharging station.To employ the Lagrange multiplier method to associate subproblems.Firstly,the subgradient algorithm is used to update the LR multiplier.Secondly,the objective function value of the vehicle routing subproblem is solved as the lower bound of in the current iteration.Thirdly,without considering the multiplier value of the feasible paths,the total travel cost of all feasible paths based on the proposed recharging station in the original model is solved,which is the upper bound of the current iteration.Finally,the upper bound satisfying the stop condition is obtained by updating the LR multiplier,which is regarded as the global approximate optimal value of the original problem,thus optimizing the quality of the feasible solution.Case analysis of the location-routing optimization model.Aiming at the different situations of a simple network and a real complex network,the algorithm solving process based on Lagrangian relaxation and decomposition is realized.The small-scale example is better than GAMS software in solving speed and calculation scale.Meanwhile,the gap of the large scale example based on Xianlin sub-city in Nanjing is 34.1% and the vehicle routing scheme as well as the recharging station location scheme are obtained.The adaptability of the model and the effectiveness of the algorithm are verified by these cases.