An exact solution algorithm for the bi-level optimization problem of electric vehicles charging station placement

Abstract

This work addresses electric vehicle (EV) charging station placement through a bi-level optimization model, where the upper-level planner maximizes charging revenue by selecting station locations under budget constraints, while EV users at the lower level choose routes and charging stations to minimize travel and charging costs. To account for battery range limitation, we construct a battery-expanded network and apply a shortest path algorithm with Frank-Wolfe traffic assignment. Our primary contribution is developing the first global solution algorithm for large scale EV charging station placement problems. We propose a Branch-and-Price-and-Cut algorithm enhanced with value function cuts and column generation. Our exact algorithm delivers solutions provably within the reported optimality gap of the global optimum with mathematical certainty. Computational experiments on the Eastern Massachusetts network (74 nodes, 248 links), the Anaheim network (416 nodes, 914 links), and the Barcelona network (110 zones, 1020 nodes, and 2512 links) demonstrate exceptional performance. Our algorithm terminates in a reasonable runtime while achieving optimality gaps below 1% across all instances. Controlled benchmarks against two genetic algorithms on identical instances confirm that the proposed algorithm finds equal or better solutions in less computation time across all tested networks. The algorithm successfully handles problems with over 300,000 feasible combinations, transforming EV charging infrastructure planning into a tractable optimization suitable for practical decision making on real-world networks with optimality guaranteed.