Scheduling and Routing of Mobile Charging Stations to Charge Electric Vehicles in a Smart-City

摘要

We introduce the concept of mobile charging stations to charge electric vehicles. The mobile charging stations are vehicles carrying fast DC-DC chargers and battery bank. These mobile charging stations are scheduled and routed to service spatially and temporally heterogeneous electric vehicle charging requests. We formulate the optimization problem to minimize the cost of charging while satisfying the constraints of mobile charging stations and deadline constraints of charging requests. We show that the optimization problem which we have formulated is a combination of Bin–packing problem and a multi-city travelling-salesman-problem hence it is NP-hard and cannot be solved in reasonable CPU time, unless P=NP. We thus propose the modified Clarke and Wright Saving’s heuristics to solve this problem. Numerical results show that our algorithm requires less number of mobile charging stations and can appreciably reduce the cost of charging while simultaneously increasing customer satisfaction.