# A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles

arXiv: https://arxiv.org/abs/2301.07156 · HTML: https://mlsanity.com/paper/2301.07156/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 63 references that are in the map.
- First posted on arXiv 17 Jan 2023.

## Builds on (most cited first, 12 of 12)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Prior-free and prior-dependent regret bounds for Thompson Sampling](https://mlsanity.com/paper/1304.5758/) (2013)
- [On Bayesian index policies for sequential resource allocation](https://mlsanity.com/paper/1601.01190/) (2016)
- [Online Learning of Network Bottlenecks via Minimax Paths](https://mlsanity.com/paper/2109.08467/) (2021)
- [An Online Learning Framework for Energy-Efficient Navigation of Electric Vehicles](https://mlsanity.com/paper/2003.01416/) (2020)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [Stochastic Online Shortest Path Routing: The Value of Feedback](https://mlsanity.com/paper/1309.7367/) (2013)
- [Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles](https://mlsanity.com/paper/1910.09812/) (2019)
- [Steady-State Simulation for Combined Transmission and Distribution Systems](https://mlsanity.com/paper/1907.12725/) (2019)
- [Electric Vehicle Charging Station Search in Stochastic Environments](https://mlsanity.com/paper/2012.00883/) (2020)

## Abstract (arXiv)

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.