  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.
