The Vehicle Routing Problem Of Mobile Charging Vehicles And Shared Electric Vehicles Considering Mobile Charging Service

As an emerging mode of transportation,shared electric vehicles(EVs)improve the utilization rate of vehicles by staggering the time of a group of users to drive a same car,which helps reduce the number of private cars and ease traffic congestion.In recent years,EVs have been developing rapidly.Howerver,the construction speed of the charging facilities can not keep pace with the growth speed of EVs.The unmatched charging capacity has become the bottleneck of the development of shared EVs.Mobile charging vehicle(MCV),as a novel charging mode,can provide additional charging capacity for EVs.By dwelling in the stations,the MCVs can flexibly increase the charging capacity of stations and relieve the charging pressure of stations,which can further reduce the waiting time of EVs for charging.The involvement of MCVs provides more flexibility and possibilities for the planning routes of EVs.How to reasonably plan the charging routes of MCVs,as well as the charging process and travel routes of EVs,is of great significance for the operation of shared EVs.The vehicle routing problem of the shared EVs and MCVs is formulated based on the time-space modeling method,which can depict the time-space trajectories of EVs and MCVs as well as the state of charge of EVs over time.On the premise of satisfying the time-space flow constraints of EVs,the time-space flow constraints of MCVs,user demand fulfilment constraints,EV battery capacity constraints,and the constraints of number of charging EVs at stations,planning the reasonable routes for EVs and MCVs as well as the charging process of EVs to maximize the total profit of the operator of shared EVs.A customized Lagrangian relaxation-based algorithm is devised to solve the proposed optimization model.The relaxation model of the primal problem is obtained by relaxing the user demand fulfilment constraints and the constraints of number of charging EVs at stations in the primal problem.According to the characteristics of the relaxation model,the primal problem is essentially divided into three subproblems,which are user demand assignment problem,the routes planning problem of EVs,and the routes planning problem of MCVs respectively.Then,the corresponding algorithms are designed for the three subproblems.The solution of the user demand assignment problem is based on the greedy algorithm.The routes planning problem of EVs can be regarded as the resource-constrained shortest path problem of EVs considering the charging cost,and the routes planning problem of MCVs is the shortest path problem with time constraint,which can both be solved by the label setting algorithm based on the dynamic programming.Noted that the relaxation solution of the relaxation model may not be the feasible solution of the primal problem,the feasible solution generation algorithm is then designed.Then,the values of Lagrange multipliers are iteratively updated by the subgradient algorithm to reduce the gap between the upper bound and the lower bound.And the near-optimal solution can be obtained.To verify the performance of the proposed model and algorithm in this paper,a case study is conducted in the stations of EVCard in Hefei.The results show that the algorithm converges well in solving two cases with different cases.The involvement of MCVs can flexibly increase the charging capacity of stations and increase the state of charge of the EVs in the stations with insufficient charging capacity,which can further improve the the rate of user demand fulfilment and increase the total profit of the operator of shared EVs.A series of sensitivity analyses are conducted for the important parameters in the model,and some managerial suggestions are provided for the operators of shared EVs.