A bi-level optimization model for the EV charging stations location problem using a tripartite graph representation

Abstract

We propose a bi-level mixed integer program to model the optimal location and sizing of Electric Vehicle (EV) charging stations deployment in an inter-urban area, aiming to accommodate inroute charging demand. Our key step is a network simplification, allowing to model the charging behavior through a tripartite graph of origins, charging stations, and destinations. We apply a heuristic to find a high-quality solution, where parametric versions of the two levels are independently solved. While the upper level is a linear integer program, the lower level is suitably solved through a user equilibrium model, highly benefiting from the compact network. Our methodology is validated in the Quebec network and shown to achieve a robust solution in a short running time. Charging stations were located between the primary population centers, serving the main share of the demand. Layout alternatives and parameters changes can be easily evaluated due to the model simplicity.