A stochastic programming approach for electric vehicle charging station expansion plans

The projected and current adoption rates of electric vehicles are increasing. Electric vehicles need to be recharged continually over time, and the energy required to ensure that is immense and growing. Given that existing infrastructure is insufficient to supply the projected energy needs, models are necessary to help decision makers plan for how to best expand the power grid to meet this need. A successful power grid expansion is one that enables charging stations to service the electric vehicle community. Thus, plans for power expansion need to be coordinated between the power grid and charging station investors. In this paper, we present a two-stage stochastic programming approach that can be used to determine a power grid expansion plan that supports the energy needs, or load, from an uncertain set of electric vehicles geographically dispersed over a region. The first stage determines where to expand the power grid, and the second stage determines where to locate charging stations. The key link between the first and second stage decisions is that charging stations can only be located in areas with sufficient power supply enabled by an expanded power grid. To solve the model, we utilize a hybrid approach that combines Sample Average Approximation and an enhanced Progressive Hedging algorithm. We enhance the Progressive hedging algorithm by applying rolling horizon and variable fixing techniques. To validate the proposed model and gain key insights, we perform computational experiments using realistic data representing the Washington, DC area. Our computational results indicate the robustness of the proposed algorithm while providing a number of managerial insights to the decision makers.