Incremental expansion of large scale fixed and mobile charging infrastructure in stochastic environments: A novel graph-based Benders decomposition approach

As electric vehicle (EV) adoption increases worldwide, the growing charging demand necessitates a well-thought expansion of public charging infrastructure; insufficient or improperly deployed infrastructures pose a real risk of slowing down the adoption of EVs. Public charging networks are likely to develop into very heterogeneous systems with, for example, fixed and mobile chargers. This paper proposes a multi-period mixed-integer programming formulation for optimally placing different types of fixed and mobile chargers to meet time-varying stochastic charging demands at a minimum cost. As this formulation leads to an NP-hard problem, we develop a Benders decomposition for solving large-scale examples of the problem. In addition, a novel graph-based algorithm is proposed to get exact dual-variable solutions of sub-problems in Benders decomposition in a shorter computational time than the classical solution. Numerical experiment results confirm the effectiveness of our approach and demonstrate its ability to solve large-scale instances of the problem efficiently. Furthermore, an optimization-simulation framework is introduced to implement this method in a real-world scenario. This involves generating energy demand scenarios from an existing agent-based simulation of EVs based on the Frederiksberg municipality and then using large-scale demand scenarios to find the optimal expansion of fixed and mobile charging stations. Two optimal expansion strategies are considered: one deploying only fixed chargers and another involving a combination of fixed and mobile chargers. These two scenarios are compared with the existing charging infrastructure based on cost, coverage, and ability to meet stochastic charging demands. The findings indicate that a combination of fixed and mobile chargers offers cost-effectiveness and efficiency for an EV charging infrastructure.