Profit Maximization with Customer Satisfaction Control for Electric Vehicle Charging in Smart Grids

As the market of electric vehicles is gaining popularity, large-scale commercialized or privately-operated charging stations are expected to play a key role as a technology enabler. In this dissertation, we study the problem of charging electric vehicles at stations with limited charging machines and power resources. Our electric vehicle charging station is composed of a central controller, multiple charging machines, and a plurality of parking lots. Each parking lot has a plug connectable to an arbitrary charging machine through a switching bar system. The switching bar system allows the station owner to serve a larger number of customers at the same time by enabling dynamic connections, where the number of charging machines could be much less than the number of plugs. The central controller collects all the information provided by the customers in advance or on the fly and decides when to activate or de-activate a machine-to-plug connection, how fast the vehicles should be charged, and how much energy should be delivered to each vehicle. The purpose of this study is to develop a novel profit maximization framework for charging station operation in both offline and online charging scenarios, under certain customer satisfaction constraints. The main goal is to maximize the profit obtained by the station owner and provide a satisfactory charging service to the customers. The framework includes not only the vehicle scheduling and charging power control, but also the managing of user satisfaction factors, which are defined as the percentages of finished charging targets. The profit maximization problem is proved to be NP-complete in both scenarios, for which two-stage charging strategies are proposed to obtain efficient suboptimal solutions. Competitive analysis is also provided to analyze the performance of the proposed online two-stage charging algorithm against the offline counterpart under non-congested and congested charging scenarios. Finally, the simulation results show that the proposed two-stage charging strategies have remarkable performance gains compared to the exhaustive search and other conventional charging strategies with respect to not only the unified profit, but also other practical interests, such as the computational time, the user satisfaction factor, the percentage of electric vehicles serviced, the power consumption, the competitive ratio, and the load factor