The Urban Recharging Infrastructure Design Problem With Stochastic Demands and Capacitated Charging Stations

Abstract

In this study we develop an exact solution method to optimize the location and capacity of charging stations to satisfy the fast charging needs of electric vehicles in urban areas. Stochastic recharge demands, capacity limitations of charging stations and drivers’ route preferences (deviation tolerances) are simultaneously considered to address this challenging problem faced by recharging infrastructure planners or investors. Taking a scenario based approach to model demand uncertainty, we first propose a compact two stage stochastic programming formulation. We then project out the second stage decision variables from the compact formulation by describing the extreme rays of its polyhedral cone and obtain (1) a cut formulation that enables an efficient branch and cut algorithm to solve large problem instances (2) a novel characterization for feasible solutions to the capacitated covering problems. We test our algorithm on the Chicago metropolitan area network, by considering real world origin-destination trip data to model charging demands. Our results attest the efficiency of the proposed branch and cut algorithm and provide significant managerial insights.