The urban recharging infrastructure design problem with stochastic demands and capacitated charging stations

• Published in: Transportation research. Part B: methodological 2019-01, Vol.119, p.22-44
• Main Authors: Yıldız, Barış, Olcaytu, Evren, Şen, Ahmet
• Format: Article
• Language: English
• Subjects: Algorithms; Branch and cut; Capacitated covering; Charging; Charging station location; Electric Vehicles; Flow covering; Green transportation; Infrastructure; Integer programming; Metropolitan areas; Recharging; Stations; Tolerances; Urban areas
• ISSN: 0191-2615; 1879-2367
• DOI: 10.1016/j.trb.2018.11.001

•We propose a comprehensive approach to model urban recharging station infrastructure design.•We jointly consider: Stochastic recharging demands, Capacity limitations for the recharging stations, EV drivers’ route deviation tolerances to solve infrastructure design problem.•We develop a novel methodology to solve realistic, large size problem instances.•We present a novel solution characterization for flow covering problems that can be useful to develop efficient solution approaches.•We find high quality of service levels can be achieved by deploying a relatively small number of recharging stations and multi-period investment strategies can be viable alternatives to deal with the uncertainty related to the future demand levels. 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.