Genetic Algorithm for Optimal Deployment of EV Charging Stations
With recent advances in battery technology and the resulting decrease in the charging times, public charging stations are becoming a viable option for Electric Vehicle (EV) drivers. Concurrently, wide-spread use of location-tracking devices in mobile phones and wearable devices makes it possible to track individual-level human movements to an unprecedented spatial and temporal grain. Motivated by these developments, we propose a novel methodology to perform data-driven optimization of EV charging stations location. We formulate the problem as a discrete optimization problem on a geographical grid, with the objective of covering the entire demand region while minimizing a measure of drivers' discomfort. Since optimally solving the problem is computationally infeasible, we present computationally efficient, near-optimal solutions based on greedy and genetic algorithms. We then apply the proposed methodology to optimize EV charging stations location in the city of Boston, starting from a massive cellular phone data sets covering 1 million users over 4 months. Results show that genetic algorithm based optimization provides the best solutions in terms of drivers' discomfort and the number of charging stations required, which are both reduced about 10 percent as compared to a randomized solution. We further investigate robustness of the proposed data-driven methodology, showing that, building upon well-known regularity of aggregate human mobility patterns, the near-optimal solution computed using single day movements preserves its properties also in later months. When collectively considered, the results presented in this paper clearly indicate the potential of data-driven approaches for optimally locating public charging facilities at the urban scale.
A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems’ quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000–7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer. Our results were obtained by simulation, using a tabu 1-opt solver, due to the huge number of runs required and limited quantum annealer time availability.