A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles
This addresses the challenge of efficient route planning for electric vehicle drivers by providing a novel algorithmic approach, though it is incremental in applying existing bandit methods to a specific domain.
The paper tackles the problem of long-distance navigation for electric vehicles with unknown stochastic charging station availability, developing a combinatorial semi-bandit framework to learn queue time and charging power distributions, and demonstrates its performance in simulations across Norway, Sweden, and Finland with concrete results.
In this work, we address the problem of long-distance navigation for battery electric vehicles (BEVs), where one or more charging sessions are required to reach the intended destination. We consider the availability and performance of the charging stations to be unknown and stochastic, and develop a combinatorial semi-bandit framework for exploring the road network to learn the parameters of the queue time and charging power distributions. Within this framework, we first outline a pre-processing for the road network graph to handle the constrained combinatorial optimization problem in an efficient way. Then, for the pre-processed graph, we use a Bayesian approach to model the stochastic edge weights, utilizing conjugate priors for the one-parameter exponential and two-parameter gamma distributions, the latter of which is novel to multi-armed bandit literature. Finally, we apply combinatorial versions of Thompson Sampling, BayesUCB and Epsilon-greedy to the problem. We demonstrate the performance of our framework on long-distance navigation problem instances in country-sized road networks, with simulation experiments in Norway, Sweden and Finland.