A Modified Adaptive Large Neighborhood Search Algorithm For Shared Electric Vehicle Relocation Problem

The development of the industrial during the past few decades leading to the inevitable environmental pollution.Environmental pollution has become a serious problem,and the shared travel and electric vehicles have become more and more popular.The combination of the two factors has become the inevitable result of the development of The Times.With pure electric vehicles replacing the original fuelpowered vehicles in the field of shared transportation,a better travel model appears and quickly becomes a hot research issue.One-way car-sharing service,which supports different stops,is considered the most likely to be widely promoted.The model proposed that every site equipped with a number of charging pile,and the site distributed in different areas of the city,users can start in any a site and then parked his car to any other site.Allowing customers to pick it up at any station and parking bring convenience for the user at the same time also create new challenges.At first,the number of cars are evenly distributed in each site,but with the running of the system vehicles converge to a handful of sites and the other sites become insufficient,this resulting some sites no car available.In order to solve the problem,a large number of workers relocate vehicles between site,but facts have proved that the high frequency of relocate of vehicles is inefficient,and lead a high cost.Maintaining the balance between supply and demand of vehicles at each station in the sharing system while reducing the huge operation cost caused by vehicle relocation has become a serious problem faced by the sharing trolley enterprises.In order to take full advantage of service capacity of the sharing system as well as reduce the loss of the company’s profit,we designs an efficient algorithm considering the global information to solve the uneven spatial and temporal distribution of trams’ problem.In order to reduce the huge operation cost caused by vehicle relocation process in the sharing system,this paper will use mathematical modeling and heuristic algorithm to solve the problem.First of all,this paper defines the research problem as:aiming at maximizing corporate profits,the vehicle relocation problem considering the constraints of electric quantity,time window and working hours of the worker.By abstractly modeling the problem and generating instance data of large,medium and small scales according to the real geographical location,CPLEX solver is used to solve the model on different data sets.In order to overcome the problem that CPLEX cannot efficiently solve medium and large scale data sets,an improved large neighborhood search algorithm is developed,and a customized constraint judgment formula is added into the algorithm to greatly improve the speed and accuracy of the solution.Through a large number of comparative experiments,the effectiveness of the improved large neighborhood algorithm in solving this problem is proved.