Locating electric vehicle charging stations under uncertain battery energy status and power consumption

Fostering the adoption of electric vehicles (EVs) by private drivers requires the development of a wide network of fast charging stations in which drivers traveling long-distance trips will be able to easily recharge their battery within a few minutes. However, due to their high installation costs, the number of stations that can actually be deployed with the available investment budget is strongly limited. It is thus necessary to carefully choose their location so that the charging demand satisfaction is maximized. This leads to the formulation of a facility location problem known as the flow refueling location problem (FRLP). In this paper, we study the FRLP and seek to take into account uncertainties on the vehicle driving range in the problem modeling. We propose to relax several modeling assumptions previously used in the literature to handle this problem. First, we allow the power consumption on a road segment to depend on the crossing direction. Second, we take into account uncertainties related to the energy available in the battery after recharging at a station as well as uncertainties related to the power consumption on each portion of the road network. Finally, we consider statistical dependencies between the stochastic power consumption on different arcs of the network. We focus on the chance-constrained flow refueling location model, which seeks to maximize the number of drivers for whom the probability of running out of fuel when carrying out their trip is below a certain threshold. To solve the resulting stochastic optimization problem, we propose to use a solution approach based on a partial sample approximation of the stochastic parameters and compare its performance with the one of a previously published approach based on Bonferroni's inequality. We carry out numerical experiments on a set of medium-size randomly generated and real life instances. Our results show that the proposed partial sample approximation approach outperforms the Bonferroni approach in terms of solution quality and gives station locations which provide a significantly improved demand coverage in practice.