Electric Vehicle Routing Optimization Models And Algorithms Under Uncertain Environment

Emissions from land transport,i.e.,road vehicles,are hazardous to the atmosphere and significantly influence the climate change.In this context,the governments of China,US,Japan,EU,and other countries have strongly popularized electric vehicles(EVs)and encouraged supply chains to adopt EVs to construct a sustainable logistics distribution network.Thus,it is becoming increasingly important to design effective routing schedules for EVs.Unlike conventional vehicles,the driving range of an EV is short because of its limited battery capacity.In practical application,the EV may have to visit either a charge station to recharge the battery,or a battery swap station(BSS)to replace the existing battery with a fully charged one.However,previous studies related to the electric vehicle routing problem(EVRP)were carried out in a deterministic environment,and uncertain factors that often affect the outcome was overlooked.Thus,the study aims to propose optimization models for EVRP with considering the bottle of battery technology and integrating uncertain factors.In order to address EVRP in various situations,this study formulates two mathematic models by stochastic optimization technology and fuzzy optimization technology,respectively.The applying of stochastic optimization model is based on collecting sufficient historical data.The stochastic optimization model considered extending classical recourse policy and preventive restocking policy for route failure.The applying of fuzzy optimization model can be applied without collecting sufficient historical data.The fuzzy optimization model applied fuzzy number to describe the uncertain parameters and introduced the chance constraint.The fuzzy simulation method is also applied to estimate the solution.The contributions of this study are follows:(1)The study presented a stochastic optimization model for the EVRP under certain environment,with the aim to determine a minimum cost scheme including the optimal number and location of battery swap stations(BSSs)with an optimal route plan based on stochastic customer demands.Furthermore,the classical recourse policy and preventive restocking policy are extended by considering the influences of both battery and vehicle capacity simultaneously.Subsequently,the concept of Pareto optimality is applied to the EVRP to expedite the selection of BSS sequences.To solve such a hybrid problem,a hybrid variable neighborhood search(HVNS)algorithm is proposed,which integrates the binary particle swarm optimization and variable neighborhood search to solve the location and routing problems interactively.The experiment results show that the performance of HVNS algorithm in presented model is better than other standard heuristic algorithms.(2)The study presented a fuzzy optimization model for an EVRP under certain environment.Although the stochastic optimization method is effective for addressing the uncertain parameters,it is difficult in practical applications to describe these parameters as random variables because of the lack of sufficient historical data to analyze them.Instead,fuzzy variables can be applied to address these uncertain parameters.In the presented model,fuzzy numbers are used to denote the uncertainties of service time,battery energy consumption,and travel time.Moreover,the partial recharge is allowed under the uncertain environment.To solve the model,an adaptive large neighborhood search(ALNS)algorithm enhanced with the fuzzy simulation method is proposed.In the proposed ALNS algorithm,four new removal algorithms are designed and integrated for addressing the presented model.To further improve the algorithmic performance,the variable neighborhood descent algorithm is embedded into the proposed ALNS algorithm and five local search operators are applied.The experiment results show that the performance of ALNS algorithm in presented model is better than other standard heuristic algorithms.Thus,the study for EVRP under uncertain environment is significant for popularizing EVs in practical application,optimizing logistics resources,relieving urban traffic jam and avoid environmental pollution.