Algorithm And Mechanism For Battery Distribution Of New Energy Vehicle

In the background of low-carbon economy,new energy vehicles have become the direction of the future.Charging problem is the indispensable part of the promotion process of the new energy vehicles.Battery-replacement is a development trend in the future due to the limited number of new energy charging stations.According to the actual demand,the vehicle can either go to the replacement station to replace battery or request distribution center to dispatch battery on the path of the vehicle directly.The distribution center need to dispatch batteries to replacement station and request vehicles respectively.Since the vehicle's request is unexpected,the battery distribution problem can be seen as a dynamic vehicle routing problem(DVRP).Similar to the driver of the traditional vehicle will looking for gas station while there is a certain amount of oil in the trunk,we suppose that the driver of the new energy vehicle will be in advance for a period of time to request the battery.Therefore,the real-time requirement of battery distribution is not high,distribution center can dispatch the requests which are received in a certain period of time centralized,then the DVRP can be divided into several continuous static vehicle routing problems(SVRP).We analyze the battery distribution problem from two aspects in this paper:battery distribution based on replacement station and direct delivery problem based on the moving vehicle:In the case of battery distribution based on replacement station,we propose the distribution algorithm based on forecast since the replacement station can use to store batteries.In this paper,we propose a forecast-based routing algorithm that distributes the requested vehicle at the next stage.The tabu search algorithm is used to solve the problem in each distribution stage.In the direct delivery problem based on moving vehicle,the distribution center directly carries out the battery distribution at the intersection of the requested vehicle's route.Since the requested vehicle is still running after the request is made,the distribution location at different times is also different.In this paper,the First Come First Serve algorithm and the shortest distance first algorithm are proposed to solve this problem.Then,the k-means is used to cluster the requested vehicle at the initial time,each distribution vehicle is responsible for a cluster's requested vehicles,and use FCFS and SPF algorithm for each distribution vehicle.Experiments show that using clustering algorithm is better than those without clustering.However,the k-means algorithm only clustering according to the location of the requested vehicle at the initial time of delivery,while requested vehicle is at high speed,it may initially locate in cluster i and be closer to cluster j at the time of dispatching.We consider to reassign this requested vehicle to the distribution vehicle corresponding to cluster j if it can get better target value.Experiments show that there exist requested vehicles that is closer to the other clusters and the target value can be optimized after the redistribution.Finally,a relocation strategy is proposed to allow the idle vehicle which have the remaining battery to the nearest intersection for a request.