A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles
Authors: Niklas Åkerblom
Morteza Haghir Chehreghani
Venue: Accepted by TMLR ()

Abstract: 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 method for transforming the road network graph into a graph of feasible paths between charging stations to handle the constrained combinatorial optimization problem in an efficient way. Then, for the feasibility 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 large-scale country-sized road networks, with simulation experiments in Norway, Sweden and Finland.

Published in Transactions on Machine Learning Research (11/2023)
A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles
Niklas Akerblom
niklas aelllss.deeroom@@@vvvoorr.ooo
Volvo Car Corporation
Chalmers University of Technology
Morteza Haghir Chehreghani
Chalmers Universily of Technology
Reviewed on OpenReview: https: openreview. net/ pet//formm id id=ndu90phMM9
Abstract
In this work, we address the problem of long-distance navigation for battery electric ve- hicles (BEVs), where one or more charging sessions are required to reach the intended destination. We consider the availability and performance of the charging stations be unknown and stochastic, and develop a combinatorial ceni-bandit framework for exploring the road network to learn the parameters of the queue time and charging power distribu- lions. Within this framework, we first outline method for transforming the road work graph into graph of feasible paths between charging stations to handle the constrained combinatorial optimization problem in an efficient way. Then, for the fcasibility 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 novel multi-armed bandit literature. Finally, we apply combinatorial versions of Thompson Sampling, BayesUCB and ppsilon--reeddy to the problem. We demonstrate the performance of our framework on long-distance navigation problem instances in large-scale country-sized road networks, with simulation experiments in Norway, Sweden and Finland
1 Introduction
In the coming years, it will be crucial for society to shift the transport sector (personal and commercial) towards electrification, to reach global targets on reduced greenhouse gas emissions. Range anziety still major obstacle the widespread adoption of battery eloctric vehicles (BEVs) for transportation. This phenomenon be characterized exceeding the electric range of their vehicle before reaching either their destination charging station, thus being stranded with an empty battery.
the fear that (potential current) BEV drivers might. feel about
There is another, perhaps less commonly discussed, but potentially more relevant issue called charging anriety. Whereas the range of typical electric vehicles, while still shorter than that of combustion engine vehicles, has been steadily increasing, the act of charging the battery is still, often, a cumbersome task. Even locations with fast chargers, various factors may severely impact the total travel time of particular trip. At the highest possible charging power, charging BEV battery from nearly empty to close to maximum capacity may take more than 30 minutes. However, maximum power might not always be provided, in practice. Furthermore, queues to charging stations may appear due to the (relatively) long charging times and few charging locations. Issues like these might diminish public trust in BEVs as viable alternatives to combustion engine vehiclos.
1 Quu code available htte:://gtthh..ccaooaattaaerrrrr

---

Published in Transactions on Machine Learning Research (11/2023)
In this work, we attempt to mitigate any charging anxiety arising due to the aforementioned factors by developing an online sell-learning algorithmic framework for navigation of BEVs, capable of taking such charging issues into account. We view the task as a sequential decision-making problem under uncertainty and model it as a combinatorial semi-bandit problem to address the trade-off between exploring charging stations to learn more information about. them and exploiting previously collected knowledge to select charging stations that are likely to be good. Within this framework, we employ a Bayesian approach, with conjugate priors novel bandit literature. To our knowledge, our work is the first study that addresses the challenging real-world problem of charging station selection in the partial information setting using multi-armed bandit (MAB) methods. Thereby, our work provides a novel framework to develop and investigate advanced multi- armed (combinatorial) bandit methods. As mentioned, our work is also one of the few large-scale real-world applications of multi-armed bandits, specifically in the combinatorial setting. To achieve such scalability, we transform the road graph into a feasibility graph, where feasible paths between charging stations are pre- computed to improve run-time efficiency. Such a transformation of the problem instances for the purpose of computational efficiency is novel to the MAB community.
2 Related work
Several works have studiod shortest path algorithms to address the problem of energy efficient navigation, e.g.: Artmeier et. al. (2010); Sachenbacher et. al.] (2011), focusing on minimizing energy consumption, and Baum et al. (2015), studying how to minimize travel time while ensuring that battery energy is not fully depleted (utilizing charging stations, if necessary). [Swoda et al. (2017) outline a Dynamic Programming (DP) approach for adaptive routing of electric vehicles, and model charging station availability and quene / waiting times, but assume that all distributions are known in advance. A similar work by Guillet et al. (022)) formulates charging station selection as a stochastic search problem, addressed with a DP-based approach. BEV navigation problems (including charging station selection) have been modelled as detailed reinforcement learning problems (Lee et al. 2020; Qian al. 2020), but often with high computational demands making them infeasible for long-distance navigation. To our knowledge, this problem has not been studied in the partial information setting using multi-armed bandits, and our work is the first contribution of this kind. Prior works on multi-armed bandits for energy-efficient navigation, e.g., Akerblom et al. (2020) 2023a), are significantly simplified without considering travel time and charging. Dealing with charging, in particular in a computationally efficient way, requires considerably more sophisticated models and methods, beyond the existing applications of (combinatorial) multi-armed bandit methods, as will be demonstrated in this paper.
In general, the multi-armed bandit problem is versatile way of describing how to utilize limited resources to balance exploration of an environment to gain new knowledge and usage of previously collected knowledge to increase long-term reward. Thompson Sampling (Thompson 1933) is an early algorithm attempting to address this trade-off, which has recently increased in popularity due to demonstrated experimental performance (Graepel et al.) 2010; Chapelle & Li. 2011) and proven theoretical performance guarantees (Agrawal & Goyal 2012 2 Kaufmann et al., 2012b Bubeck & Liu. 2013 Russo & Van Roy 2014].
Another lype of method commonly used for sequential decision-making problems is the Upper Confidence Bound (UCB) [Auer 2002) algorithm. Like Thompson Sampling, this method has been adapted to many different settings, including combinatorial optimization problems (Chen et al.] 2013). UCB methods have also been used for MAB problems with sub-exponential rewards (Jia et al.) 2021). e.g., for selection of bike rental companies with exponential service times, but not in combinatorial settings as far as we are aware.
3 Model
In this section, we describe how to represent the road network as a graph and how to transform it inlo a graph of feasible paths between charging stations to allow for computationally efficient charging station selection. Furthermore, we outline an approach for probabilistic modelling of the qucue time (i.c., the time spent waiting for an occupied charging station) and the charging power of each charging station. In Appendix A we include summary of the notation used throughout this work.
2

---

Published in Transactions on Machine Learning Research (11/2023)
3.1 Road network graph
We model the underlying road nelwork using a directed and weighted graph groad (yroad, g ; Each vertex u E yroad corresponds to either an intersection or some other important location of the road network (o.g., a charging station). Each directed edge e E groad represents a road segment from a location u E proad to another location u' E yroad, which we may also indicate by writing e = (u, u'). We further denote the travel time of each road segment e E groad as -road and the vector of all edge travel times as roodd Additionally, each road segment e E groud has an associated energy consumption s which is the energy needed by given vehicle to traverse the complete road segment. A convention we follow throughout the paper is to indicate vectors with bold symbols, with individual elements indexed by edge or vertex subscripts. Furthermore, we let ycharge C yroad be the set of locations which contain charging stations. Each charging location u E ycharge is associated with a maximum charging power g which the charging station is able to provide. We also assume that there is a corresponding value for the minimum charging power en available at each station. With the exception of the actual charging power e ocharge E [e ewax]] C R and the queue time = qqueee E RR, both of which we consider stochastic and unknown, all other parameters mentioned in this work (except the charging time, which directly depends on en echarge) are assumed to be fixed and known by the learning agent.
A connected sequence p of edges (or vertices, equivalently) is called path through the graph. Given source vertex w E yroad and a target vertex u E proad (both assumed to be fixed and known), we denote the set of all paths starting in ure and ending in t as P(ue uure" Assuming that we aim to find a path which minimizes the total travel time, we let, for each edge E groad the edge weight be rroad Then, the shortest path problem, given ure, tht and groud is defined as
p' = arg min proad (utr))
Σ road Ccp
Te
(1)
which may be addressed by one of several classical methods, e.g., Dijkstra's algorithm (Dijkstra) ra 1959), the Bellman-Fore algorithm (Shimbel 1954 Ford Jr| 1956; [ellman 1958) or the A algorithm (Hart et al., 1968). The A algorithm, in particular, can be described as best-first search method (sec e.g., Dechter & Pearl 1985), where a provided heuristic function is used to guide the algorithm towards promising solutions. An admissible heuristic function should be able to provide an underestimate of the total weight of any path between a pair of given vertices. For a road network graph with travel time edge weights, such as groad we can use a function which calculates a travel time value based on the maximum allowed speed in the road network and the beeline distance between the two vertices. When a good heuristic function used, the A algorithm is computationally more efficient than Dijkstra's algorithm, while still guarantccing that the optimal path is found.
3.2 Construction of feasibility graph
The model described in the previous scction is sufficient for many applications. Since fossil fuel stations are ubiquitous in most road networks, and since the time required for refueling is typically negligible, the model can be used for navigation of combustion engine vehicles without significant modifications. For BEVs, however, charging can take more than 30 minutes, and multiple charging sessions may be required for longer trips. These factors, combined with the relative sparsity of the charging infrastructure, means that charging should not be disregarded in the navigation problem.
The time spent on charging depends on the amount of energy needed and the charging power provided. Furthermore, queues may occur if all charging stations at a particular location are occupied at the same time. The rrsource-constraine shortest path problem (RCSPP) (Joksch] [966) is a variant of the shortest path problem where each edge is associated with one or more resources, in addition to the weight. The problem, which is known to be NP-complete (Handler & Zang 1980) for even a single resource per edge, is to find the shortest path (w..tt. the weights) such that the accumulated resources for the path do not exceed specified constraints. The single-resouree version of RCSPP is special case of our problem (with consumed energy as the resource and battery capacity as the constraint), where it is also possible to replenish (recharge) the resource at a subset. of the vertices, making it necessary to approximate the problem.
3

---

Published in Transactions on Machine Learning Research (11/2023)
In this work, for simplicity, we assume that each charging session has to fully charge the battery. We also assume that the paths between charging stations should be chosen to minimize travel time, even if there are alternative paths with less energy consumption. For clarity, throughout this work when the battery is stated to be either empty or fully charged, the battery state of charge is actually 10% or 80%, respectively, for safety and durability reasons.
With the aforementioned two assumptions, it is possible to transform the road graph into a feasibility graph, where feasible paths between charging stations are pre-computed to improve run-time efficiency. We denote this directed and weighted graph gfousible (y Efeusiibee , feussible). In order to construct the feasibility graph, we start by letting yfeassblee = yeharge be the set of charging stations. Then, for any given path p through groad, let Tpaa = Eeep Teand be the travel time of the path and Ep spad = Emep stoad be the total energy consumption of the path. We create a new set of edges Eoath {(u,u') E Vieasible x yfessible], ). where each edge (u, u') E Eoath corresponds to the shortest path P(u,w") arg mimpmerone apond between the (u.a')
road and ((,,ee) = = "Pa...''' Finally, charging stations (computed as in Eq. 1 where we denote T(u,e') = "P(a...)
given a maximum battery capacity emax and minimum battery capacity e'iin, we define the set of feasible edges as the set of shortest paths between charging stations where the battery capacity exceeds the energy consumption, i.e.,
gleasible = =fe E goath |
epath
< - g
Moreover, we define a vector of travel times for the edges of the feasibility graph, feasible For each edge (u.'') E Eleasible, we let
feasible = T(I,e))
-aahh + Tma (u,nec)
queue charge
+ (u,,")
where the charging time chaargo = (a.ur)/ Lu" e depends on both the energy consumed on the edge (u, u') and the provided charging power at u', while we assume that the queue time T queue only depends on w'.
charge charge since we assume that the energy we need to charge at w' is the same as Note that (ayarr "(uad)) ev"
the energy consumed while traversing the preceding path w').
We emphasize that even though assumee each charging session fully charges the battery, the construction of the fcasibility graph (and the entire online learning framework presented in this work) can be extended in straightforward way to allow for partial charging. If the battery energy available at the start of each path is discretized into a finite number of eneryy levels, vertices can be added for these to each charging station, where edges between them represent partial charging choices. Then, feasibility graph layers may be constructed for each of the energy levels, without increasing the number of unknown parameters that an agent needs estimate. See, e.g., [wwda et al. (2017), for another approach using discretized charging levels for partial charging, applied to a sctting with fixed and known parameters.
3.3 Probabilistic queue and charging times
As stated earlier, we consider both the queue time and the charging power of each charging station to be stochastic and unknown, only to be revealed after the station has been visited. The charging power can easily be measured using internal signals of the vehicle, while the queue time can be inferred from the time spent in close proximity to the charging station (e.g., using a GPS sensor or an odometer) before charging, In contrast, we assume that we are given the travel time and energy consumption of each road segment in the road network graph (and, in practice, that they are fixed and known by the agent). We further assume that the queue time and charging power are independently distributed, both with respect to each other, as well as between different charging stations. In reality, they exhibit a complex interdependence, where low charging power might cause queues to appear, and the simultaneous charging of many vehicles may cause the available power to decrease.
3.3.1 Queue time model
The queuing behavior at a particular charging location may be complex, depending on the characteristics of the location. A charging location has few or many charging stations, where each may have multiple
4

---

Published in Transactions on Machine Learning Research (11/2023)
connectors. The stations may also differ in the maximum charging power provided, well as the price of charging. These, and other factors, impact the preferences of drivers towards different stations, especially if many of the stations at the same location are occupied simultaneously.
Rather than modelling the queues in detail, we take inspiration from a simple model queuing theory, the M/M/1 queue (Kendall, 1953), and assume that the queue time gg of each charging station yleasible is exponentially distributed according an unknown rate parameter Dy Aqueue, The likelihood function of the queue time model can then be defined as
P (T
queue Aa queuee = Exp(Aa
(4)
We also take Bayesian view and assume that the rate parameter is drawn from a known prior distribution. Even when both the parameter value and the prior distribution unknown, may, in practice, utilize partial information available (e.g,, occupancy information for some charging stations) to assign prior beliefs for the parameters using this approach (enabling more efficient exploration of the charging stations). In principle, any suitable (positive support) distribution can be used as prior, but for this likelihood and parameter, the gammaa distribution is a conjugate prior (meaning that the posterior distribution given observations is also a garma distribution, and thereby the posterior parameters can be efficiently computed). The prior is then given by
P (An
(qqueu
w.0 : :P,00 -uppee
queue
= Gamma (0,0 , (0g
queue
(5)
Given a sequence of obscrved queue times y1, .. Yt, the paramcters a queue and gqueue of the gamma postcrior u.t
distribution are given by aquune aqgure + and Pu,t of the parameters can be performed using Outt -u 1 + and Pa.t Putt-1 + yt.
Au 34,00 + D Vi- Similarly, incremental updates queue queue
gqueue
3.3.2 Charging power model
Idcally, which is also often the case, any given charging station u E Vffessibe should be able to provide the specified maximum charging power gmax, Occasionally, however, some charging stations provide less power. Reasons for this may include, e-g., intermittent high load in the surrounding electric grid, limitations of the charging station, etc, Moreover, in this work, we assume that the vehicle is able to fully utilize the charging power provided by the charging station. Again, we note that some of this information may be available the agent a priori and can potentially be used to assign prior beliefs to the parameters.
While Gaussian model could be sufficient for the anomalous cases described here, it would have to be truncated or rectified to represent the sharp peak in density at max for charging station functioning as intended. Then, conjugacy properties may not be used for efficient posterior parameter updates. An alternative, which we describe here, is to use a gamma distribution to model the charging power. In practice, we still rectify the charging power distribution below @ in Section to prevent negative or zero charging power, but this should have relatively minor impact on the results since the density of the charging power distribution often concentrated close to g likelihood function
max with the prior distributions that consider. We define the
P
max (aa
charge Du
charge geharge) = Gamma (a charge geharge
(6)
A conjugate prior distribution for both parameters of the gamma likelihood was derived by Damsleth 1975 and further analyzed by Miller (9800), which Damsleth 1975) refers the Gamcon-ll prior. The joint
prior distribution over a charge and geharge has set of parameters Fu,0
charge
charge and geharge 0, Ju,0
where charge charge 1. Decomposed, the conjugate prior over geharge conditional on a V T2.0
charge is also
gamma distribution, defined as
P geharge charge charge ccharge =
la (a
7n.0 -S,00
Gamma E o y Tu,0
charge charge
(7)
5

---

Published in Transactions on Machine Learning Research (11/2023)
Whereas the prior distribution over Seharge has convenient form for both sampling and moment computa- tion, only the unnormalized probability density function for the marginal conjugate prior distribution over a charge is available. It is defined as
P (a gharrg
charge charge charge echarge exp
charge In
charge echarge charge In Ta,0
charge
"au N,, $5,0
Qu
uuo
Of
(8)
echarge
In (harr))) + In
(chhare (uu.0 au ccharge)
where (-) the well-known gamma function. The joint unnormalized prior distribution over a charge and geharge then the product Eq. and Eq. With an observed charging power 2t, the incremental updates for the parameters of the joint posterior are given by Tu, charge
charge zcharge (e_=ax - =1), Tn.
charge
Tu,t-1 + (o - 24) and used efficiently find the mode of the posterior, since it is log-concave on the (positive real) domain. An
Sa,t echarge <charte + 1. Despite lacking a normalization constant, Eq. 8 can be
unnormalized density function can also be used in adaptive rejection sampling methods to efficiently generate exact samples from the posterior distribution.
4 CMAB formulation
We formulate the problem of selecting paths and charging stations through the road network as a sequential cettsinn-mkingg problem under uncertainty. Specifically,
see it combinatorial semi-bandit (CMAB) problem (Cesa-Bianchi & Lugosi 2012: Gai et al. 2012), a variant of the classical multi-armed bandit (MAB) problem. For a finite horizon T, and each itcration E [T], the agent has to select and execute an action. In the CMAB setting, this action consists on which subsets are allowed to be selected by the agent. The enviromment gives feedback for each of the objects selected (called semi-bandit feedback), the of which determines the reward received by the agent for taking the action.
subset of objects from a ground sel. Often, there are constraints
In our setting, the ground set corresponds to the set of edges in the feasibility graph, ie., ffeasible For source vertex a E ffeasible and target vertex " E flessibe fixed for particular problem instance, the set of allowed actions corresponds to the set of paths Pfousible (r"e from the source to the target in the feasibility graph. In each iteration E [T], the agent selects and travels a path p. PPeassile (w")) and receives the path path travel time (u,x')) queue time queee and charging time ccarge o
[(u,w') as feedback for each edge (u, u') E Pt. Since the shortest path problem is a minimization problem, we say that an action has a loss instead a reward,
where the loss of the traveled path is
(p(p))
Σ
feusible
(u,aa)
(a,a))Ep
charge Let 0 be an arbitrary vector of model parameters for the entire where Nleasihie path + T.. + (a,aa)) ((a.a')
-quuee
feasibility graph, where for each vertex u yleasible we let O,, = (Aqueue, a charge geharge). Then, we define the expected loss function of path p as
fo(p)
Σ
(u,ar)
path
+ quene + I I go ae (u, nd)))
X
(10)
(u,w))pp
where
9 charge gohange (u, u') = E ( /max Low
ea
charge)
a
charge geharge
(11)
is the expected charging time, given the parameters aw denominator rectified below the minimum charging power min Throughout this work, I Ja geaure (u, u²)
charge and geharge, Here, the charging power in the

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm CMAB charging station selection
Input: 0,0 u,0
queue gqueue
Tu, '7,00 Su,0
charge
/oloree echarge
1: for t ....,, do
9:
for each travelled edge (u, u²) ps do
2: for u E Dleasible do
Observe feedback Tu² Tiu and Taaare
10:
&charge and Geharge using 3: Compute Faucue, a
11:
a u
queue
+ at w'_-11
queue
+1
specified CMAB method and current poste- rior parameters du,t-1 gqueue charge charge and cu
12:
+ u 1-11 + TT²
gqueue
queee
"u,t- 7u,t-1
charge
13:
Ou
"(u,a))
4: end for
5: for (u,'²) v')
E gleasible do
14:
charge ue 1
2l "
charge
On
max
Lu
charge
6:
fleasible
quene
15:
Tu't ,
charge
charge
Li
max
Lu
charge
Dachange ii acharge (u, v²) end for
16: Suharge + Sa'tt1 +
17: end for
P. f- arg min plasuile
Afonsible E (u.u))p (u,x))
(usre (ttee)
18:
end for
is approximated as chares B gehasge (u, u²) using Monte Carlo estimation, by averaging over charging time values computed with samples from the charging power model defined in Eq. 6
MAB algorithms usually evaluated using the notion of regret until horizon T, which is defined as the over all iterations E [2'] of the difference in expected loss of the best action p* (defined in Eq. but for the feasibility graph) and the action Pt selected by the algorithm, such that
(egret(T)) = Σ
(Jo- - So- (p")), LE[T]
(12)
where 0" is the true underlying parameter vector (in which the parameters of the queue time and charging power distributions assumed to be drawn from their respective prior distributions). The objective is to find a policy that minimizes the expected regret, where sub-linear growth with respect to T is generally desired.
5 CMAB methods
We adapt three CMAB algorithms for problem setting: Epsilon-groedy, Thompson Sampling and BayesUCB. For all three algorithms, shortest path algorithm is used to find the shortest path through the feasibility graph. This is usually called an oracle in CMAB literature. While Dijkstra's algorithm is a commonly used oracle for CMABs with shortest path problems (see e.g., , Gai et al. 2012 Liu & Zhao 2012 Zou et al. 2014 Akerblom et al. 2020), we may use the more efficient A algorithm since the feasibility graph admits suitable heuristic function. Since the vector of path travel times path fixed and known, the direct (boeline) distance between each pair of charging stations can be divided by the maximum allowed speed in the road network (e.g., 120 km/h) to get value which guaranteed to underestinate the travel time between those stations. We do not explicitly consider the queue time or charging time in the heuristic function, but clearly, both are non-negative and implicitly underestimated by zero.
All three algorithus follow the same general structure, as outlined in Algorithm [ which closely corre- sponds to the CMAB description in Section 4 while also including explicit posterior parameter updates and other details. The primary bottleneck in the computational efficiency of Algorithm [ is the short- est path computation on the feasibility graph, with a run-time complexity for each iteration t E [T] of O [[gfeasible] D log [ if Dijkstra's algorithm is used.
7

---

Published in Transactions on Machine Learning Research (11/2023)
5.1 Epsilon-grest greedy
In each iteration t E [2], the Epsiion-greedy MAB algorithm selects actions either greedily, according to current parameter estimates the loss distributions, or uniformly at random. It selects uniform exploration with a small probability & (decreasing with 1) and greedy otherwise.
In line of Algorithm we retrieve qqueue acharge and Beharge through MAP cstimation, i..,, by finding the mode of each posterior distribution. This can be done analytically for the gamma prior / posterior Eq. such that fqueue < / (0 1), where we assume that queue u,t-1 > 1. For &charge and Jeharge, the Gamcon-ll prior posterior over a charge in Eq. g has no analytical formula for the mode, but it can be found numerically. With the mode acharge, we can calculate 3charge <- (gcherre - &charge dh
In greedy iterations, the calculated estimates used directly in line g to find path to travel. In ex- ploration iterations, however, line g is changed to provide random exploration of the feasibility graph. Chen et al. (2013) (supplementary material) introduced CMAB version of Epsilon-greedy, which we adapt here. First, a vertex u rrand
E Vlensible is selected uniformly at random. Then, we find the paths min pepfenatbl
Pt (1) + arg min pePinable
(rand) ((npeee *loasible and P;
(2) + arg min (uronddaatn ((ua(e Alosstlee which we
concatenate to get Pt.
5.2 Thompson Sampling
Thompson Sampling Thommson 1933 is one of the oldest MAB algorithms, which has recently been adapted
to CMAB problems (Wang & Chen 2018). including shortest path problems with stochastic edge weights for
various applications [Wang & Chen 2018
Akerblom et al. 2020 2023b). Like Epsilon-greed greedy, it performs randomized exploration, but does so in every iteration and in a more guided way. It utilizes the knowledge encoded in the prior and posterior distributions, by sampling paths according to the probability that they are optimal (given the prior beliefs and the observations from the environment).
In Algorithm only line X needs to be adapted to this method. Here, the expected queue time f 4queue and charging power parameters &charge and Beharge are calculated using parameters sampled from the current posterior distributions. For the queue time prior distribution in Eq. 5 sampling the rate parameter Âquene from the gammna distribution is straightforward, which gives an expected queue time of Æqueue + 1/Agueue Similar to the mode calculations in Section 5.1 sampling &charge from the Gamcon-II prior and postcrior distribut ions is not as convenient. However, we can utilize adaptive rejection sampling (ARS) (Gilks & Wild 1992) generate exact posterior samples, since it only requires (Iog-concave, but not necessarily normalized) probability density function, like Eq. g In this work, we specifically use an extension called transformed density rejection (TDR) (Hörmann 1995
Once a sample of acharge is obtained, the conditional
gamma prior distribution in Eq. 7 can be used sample Jeharge
5.3 BayesUCB
MAB algorithms based on upper confidence bounds (UCB) Auer 2002) use high probability overestimates of actions' expected rewards to explore the environment. By doing this, UCB methods follow the principle of optimism in the face of uncertainty to select promising actions. UCB methods have been shown to have good performance in many different problem settings, and have been adapted to CMAB settings CCen et al. 2013), including shortest path problems.
We adapt a Bayesian version of UCB called BayesUCB (Kaffmann et al. 2012a Kaufmann setting so that we can utilize the prior distributions for exploration. Again, like for Thompson Sampling, we only have to modify line 3 of Algorithm to implement this method. BayesUCB uses (lower, in this case) quantiles of the posterior distributions over expected action losses as optimistic estimates. Given a probability distribution X and a probability v, the quantile function Q (v, x) is defined such that Prawx {a S Q (v, x)x v. For the queue time Aqueue a high rate parameter Yqueue results in a low expected travel time fqueme + //Squeue Hence, an upper quantile of Eq. should be sought, i.e.,
2018 to this
8

---

Published in Transactions on Machine Learning Research (11/2023)
queue +
(1-11//1 Q1-1// P (Agguuu 1 (9.-111)
queue
(13)
where we the probability value (1 (1-10 1/t) suggested by Kaufmann et al. 2012a Since the Gamcon-II prior and posterior distributions do not admit a convenient way of computing quantile values, we settle on using the mode of Eq. to obtain acharge. However, we utilize the mode ácharge to compute an upper d confidence bound for geharge using Eq. 7 such that
Ad
ccharge c- Q (1 11-1/1, 1/t,
acharge, charge sche-re)) 1 (gcharge (echargeaacharee Tu,3-1 Sa,t-1
(14)
Then, as before, we can calculate an optimistic (low) estimate of the mean charging time.
6 Experiments
To evaluate the feasibility graph construction procedure described in Section 3 and the CMAB methods out- lined in Section 5] we perform realistic experiments in country-sized road networks. We define three different problem instances, characterized by their origins and destinations, across the northern European countrics of Sweden, Norway and Finland. We utilize open datasets for the road nelwork map data (OpenStreel contributors 2022 and the charging station data (Open Charge Map. 2022) of each country.
6.1 Energy consumption and travel time
For the vehicle energy consumption, we use simplified vehicle longitudinal dynamics model based on Guzzella et al. (2007), where we only consider the maximum speed of each road segment in the road network, i.e. disregard accelerations, decelerations and altitude changes. The vehicle parameters that we use are (arbitrarily) for a medium duty truck, similar to the one used by Akerblom al. (2020). For an edge groad, the model is defined as
road mgC,d droad + 0.5C. (omaad y2
(15)
3600g)
where m is the vehicle mass (13700 kg), 9 is the gravitational acceleration (9.81 m//²), Cr is the rolling resistance coefficient (0.0064, assumed to be the same for the entire road network), droud is the length of the road segment (m); Ca is the air drag coefficient of the vehicle (0.7), A is the frontal surface area of the truck (8 m²), p is the air density (1.2 kg/m², assumed be the same everywhere), of groa is the maximum speed of the road segment (m/s), and 17 is the battery-to-whek wheell energy conversion efficiency (assumed to perfect, i.e., 1). The battery capacity (2.5 10 ss 69.4kWW of the vehicle is assigned to be very low, so that it is required to charge often. The travel time of the edge is assumed to be --oad = droad /uroad
6.2 Experimental setup
First, each of the country road network graphs is transformed into feasibility graph according to the procedure described in Section 3 For simplicity, we remove all charging stations with lower specified power than 10 kW, since slower charging stations should be less relevant for long-distance travel. Furthermore, we assume that each charging location has a single charging station (by removing all except the one with the highest specified charging power, as well as any duplicates). Table shows the number of vertices and edges in the initial road graph groad (jroodd groad) and constructed feasibility graph gleasible (yfeessible gleasible) of each problem instance. Figures la Ic and Le visualize all edges of the road network graphs of Sweden, Norway and Finland, respectively, as well as examples of the explored paths and charging stations visited when Thompson Sampling is applied to the problem. Figures Ib [ddand] (and[Tssoow graphs for each of the networks. In the feasibility graphs, we can see that some parts of the road networks are unreachable from the rest of the road network, given the specified battery capacity 69.4 kWh.
show the corresponding feasibility
For each vertex E feasihle and the queue time prior distribution defined in Eq. we assign the prior parameters as 200
quene 2 and P0,0 2400, and for the charging power prior distribution in Eq. 7 and Eq.
9

---

Published in Transactions on Machine Learning Research (11/2023)
(a) Road graph: Sweden.
(b) Feasibility graph: Sweden.
(c) Road graph: Norway.
(d) Feasibility graph: Norway.
(e) Road graph: Finland.
(f) Feasibility graph: Finland.
Figure 1: Road and feasibility graphs for each of the problem instances in blue, with Thompson Sampling exploration of paths in red and charging stations green, where the opacity indicates degree of exploration for both.
10

---

Published in Transactions on Machine Learning Research (11/2023)
Instance proad
grood
Yeasible
(eealbble
Sweden 6.8 10
1.5 106
1.7 10a
1.6 105
Norway
3.6 10
7.6 10
1.1 10a
8.5 10*
Finland
4.3 10
9.5 10
5.5 102
7.0 7.0-104
Table 1: Sizes of the road and feasibility graphs for all problem instances.
charge = 300 and cctor 3. Furthermore, we scale we set the paramcters so that charge = exp (13.5), Yu.0 The samples and expected values of the gamma distribution in Eq. G by 300 to achieve a sufficiently high charging power variance. For the rectification of the charging power below enth, we assume e.0h = e=xx/ /2. We choose N = 1000, and can then estimate the expected charging time using Monte Carlo sampling, such that
N
path (u,w²)
i charren grbarer (u, vl) w
(16)
N
max
0minn mmax 300ez)
where 2k ~ Gamma Og2 19
charge ggharge
For Epsilon-Greedy, we let e, = 1/Vl. Moreover, for Thompson Sampling, we experience that TDR occa- sionally fails to produce samples when the posterior distribution over au after few hundred observations. When this happens, we switch to the mode of the distribution for the specific charging station u, while continuing posterior sampling for all other charging stations. Besides Epsilon-Greedy (F-GR), Thompson Sampling (TS) and BayesUCB (B-UCB), also include pure greedy method (GR) in the experiments (i.e., Epsilon-Greedy with e, 0), as a baseline.
acharge gets too concentrated, typically
6.3 Results
We run all experiments with a horizon T = 1000. We include the following problem instances: Sweden (Gothenburg to Stockholm), Norway (Oslo to Trondheim) and Finland (Helsinki to Vaasa). For all pairs of problem instances and CMAB methods, we run the same experiment 10 times, with different random seeds. The regret results are summarized in Table 2 as well as through regret plots with standard error regions in Figures 2a
2b
and 2c
Method
Sweden
Norway
Finland
GR
1.8 18% 108)
6.2 6.2-10 10s)
1.8 10 10%)
E-GR
4.4 10
3.2 3.2 109)
2.3 10% 105)
TS
4.0 100..770-2
2.2 22-10
1.4 105)
B-UCB
7.6 (=2.4-100)
2.7 2.7-10
108)
5.2 5.2-10 108)
Table 2: Final average (+: standard deviation) of regret at iteration T = 1000 for all problem instances.
In Table we report the average and standard deviation of the per-iteration run-time (in scconds) of cach method and problem instance. The CMAB methods are implemented with Python using the SeiPy library, for implementations of statistical functions, including the Transformed Density Rejection method (Hörmann 1995), and the NetworkX library (Hagberg et al.] 2008). for the implementation of the A algorithm. All run-time measurements were performed on a single core of a laptop with an Intel Core(TM) 17-10850H CPU (2.70 GHz) and 32.00 GB RAM.
In general, the Epsilon-Greedy method incurs the highest final regret of all the methods, for all problem instances. This can be explained by the uniformly random selection of charging stations, which means that the method takes very long detours, sometimes to the other side of the country. Following close behind is
11

---

Published in Transactions on Machine Learning Research (11/2023)
4.0c1066
3.0c-166
rogett
agent GR
cumulaaiiv regiet
agent
3.0e+066
GR
E-GR
0.0c+06
E-GR
2.0e+066
T
1.0e06
1.0c106
0.0e000
500 Itenaion (1)
250
1000
Iteration
(a) Cumulative regret: Sweden.
(b) Cumulative regret: Norway.
2.0c+06
agent
GR
cumulatvv
B-GR
L.
ileratinn
(c) Cumulative regret: Finland.
Figure 2: Plots of cumulative regret averaged over 10 runs (with standard error regions), as a function of the iteration t, for each of the problem instances, and the CMAB methods Greedy (GR), Epsilon-Greody (E-GR), Thompson Sampling (TS) and BayesUCB (B-UCB).
Method
Sweden
Norway
Finland
GR
2.04(#0.18)
2.61
3.09(+0.37)
E-GR
2.80(=0.51)
3.38(=0.77) 2.83(=0.79)
TS
2.79(+0.78)
2.92(+0.62)
2.93 +..36)
B-UCB
3.47(+0.32)
2.97(+0.37)
3.46(+0.42)
Table 3: Average (over 1000 iterations) per-iteration run-time (s) (+ standard deviation) of each CMAB method, for different problem instances.
the Greedy method, which quickly converges to sub-optimal paths. This becomes even more apparent in the regret plots, which show the regret (averaged over 10 runs) as a function of the iteration t. For each of the problem instances, the Greedy method cxhibits lincar increase in regret, while the other mothods (even Epsilon-greedy) continuously find better paths. For all problem instances, Thompson Sampling performs slightly better than BCyesUCB, which may be due to the more optimistic exploration of BCyesUCB resulting in wider spread of explored paths (and consequently, occasionally more regret incurred).
7 Discussion and conclusion
The key benefit of the feasibility graph structure is to reduce the number of unknown parameters that the learning agent needs to estimate. While the set of basc arms in CMAB online shortest path problems often correspond to the set of edges (see e.g., Akerblom et al. 2023a), in this case, the total number of charging stations is orders of magnitude lower than the paths between them (see Table I Since the mrors-case expocted regret of CMAB methods usually scales with the number basc arms (Chen al.) [0133] Wang & Chen 2018), keeping this number low desirable. Even with the extension for partial charging mentioned in Section 3.2 the number of base would stay the same (ensuring scalability).
12

---

Published in Transactions on Machine Learning Research (11/2023)
While the assumptions in this work are relatively strong (c.g., the assumption of mutually independent charging time and quene time with fixed distributions, or the M/M/11 queue assumption), we emphasize that, in principle, the feasibility graph structure enables more expressive models associated with each charging station. One such possible extension of this work can be to take accessible real-time information on the congestiin levels of surrounding roads into account (which both the charging time and queue time likely depend on); by casting the problem as a CMAB version of the contextual MAB problem (Lu et al. 2010
In conclusion, this work introduces novel and extensible combinatorial semi-bandit framework for navigation and charging station selection in road networks where the queue time and charging power of each charging station are stochastic with unknown distributions, the paramcters of which are generated from known prior distributions. We utilize conjugate prior distributions for the exponential and gamma models to estimate the loss distributions and induce exploration. Finally, we demonstrate the performance of our framework on several country-sized road and charging networks.
Acknowledgments
This work is funded by the Strategic Vehicle Research and Innovation Programme (FFI) of Sweden, through the project EENE (reference number: 2018-01937). Map data copyrighted OpenStreet contributors and available from hattps:/www/ http://wwwwooensteetttag/ org The structure of our simulation framework was originally based on the code of Russo al. (2018), though has since been completely rewritten.
References
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.), Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machône Learning Research, pp. 39.1 39.26, Edinburgh, Scotland, 25-27 Jun 2012. PMLR.
Niklas Akerblom, Yuxin Chen, and Morteza Haghir Chehreghani. An online learning framework for energy- efficient navigation of electric vehicles. In Proceedings of the Covnty-Nintth International Joint Conference on Artificial Intelligence, IJCAT-20, pp. 2051-2057, Jul 2020. doi: 234466//jcaii2022
Niklas Åkerblom, Yuxin Chen, and Morteza Haghir Chehreghani. Online learning of energy consumption for navigation of electric vehicles. Artificial Intelligence, 317, 2023a. doi: 10.1016/j.artinn::223. 103887.
Niklas Åkerblom, Fazeleh Sadat Hoscini, and Morteza Haghir Chehreghani. Online learning of network bot- tlenecks via minimax paths. Machine Learning, 112(1):131 150, 2023b. doi: 00.10077/100944-02--007700
Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. The shortest path problem revisited: Optimal routing for electric vehicles. In Rüdiger Dillmann, Jürgen Beyerer, Uwe D. Hanebeck, and Tanja Schultz (eds.), KI 2010: Advances in Artificial Intelligence, pp. 309-316, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. ISBN 978-3-642-16111-7 doi: 111007/978---641-16111
Peter Auer. Using confidence bounds for exploitationneexllratii trade-offs. J. Mach. Learn. Res., 3:397 422, Mar 2002. ISSN 1532-4435.
Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf. Shortest feasible paths with charging stops for battery electric vehicles. In Proceedings of the 23rd SIGSPATIAL Inter- national Conference on Advances in Geographic Information Systems, SIGSPATIAL '15, New York, NY, 2820086..
USA, 2015. Association for Computing Machinery. ISBN 9781450339674. doi:
URL http:://dooi.org//// 1145/2820782.... 011////20000111111.114/99992333 2820826
Richard Bellman. On routing problem. Quarterly of applied mathematics, 16:87-90, 1958. doi: 10.1090/ qam/102435.
Sébastien Bubeck and Che-Yu Liu. Prior-free and prior-dependent regret bounds for thompson sampling. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1, 11PS'13, pp. 638 646, Red Hook, NY, USA, 2013. Curran Associates Inc.
13

---

Published in Transactions on Machine Learning Research (11/2023)
Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404-1422, 2012. ISSN 0022-0000.
doi:
2012.00.000.0000000.... JCSS Special Issue: Cloud
Computing 2011.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Proceedings of the 24th International Conference on Newral Information Processing Systems, NIPS111, pp. 2249 2257, Red Hook, NY, USA, 2011. Curran Associates Inc. ISBN 9781618395993.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 151-159, Atlanta, Georgia, USA, 17 19 Jun 2013. PMLR.
Eivind Damsleth. Conjugate classes for gamma distributions. Scandinavian Journal of Statistics, 2(2):80-88 84, 1975. ISSN 03036898, 14679469. URL http://www. http://wwwwjjtoooooororoo ott.///ataaeee/41550000
Rina Dechter and Judea Pcarl. Generalizod best-first search strategics and the optimality of at J. ACM, 32(3):505 536, Jul 1985. ISSN 0004-5411.
doi: 10. 10.1145/3825.383))
Edsger W Dijkstra. note on two problems in connexion with graphs. Numerische mathematik, 1:269-271. 271, 1959. doi: 10.1007/BF01386300
Lester R Ford Jr. Network flow theory. Technical Report P-932, Rand Corporation, Santa Monica, CA, 1956.
Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking, 20(5):1466 1478, 2012. doi: 10.1109/TNET..0111 2011.
W. R. Gilks and P. Wild. Adaptíve rejection sampling for gibbs sampling. Journal of the Royal Statistical Society; Series C (Applied Statistics), 41(2):337 348, 1992. doi: https://doi.org 10.2307 10.2307/2347566 /2347565.
Thore Gracpel, Joaquin Quiñonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click- through rate prediction for sponsored search advertising in microsoft's 's bing search engine. In Proceedings of the 27th International Conference International Conference Machine Learning, ICML'10, pp. 13 20, Madison, W1, USA, 2010. Omnipress. ISBN 9781605589077.
Marianne Guillet, Gerhard Hiermann, Alexander Kröller, and Maximilian Schiffer. Electric vehicle charging station search in stochastic environments. Transportation Science, 56(2):483 500, 2022. doi: 10. /trsc. 2021.1102.
Lino Guzzella, Antonio Sciarretta, et al. Vehicle propulsion systems. Springer, 2007. doi: 10.1007/
978-3-540- 74692-8.
Aric A Hagberg, Daniel A Schult, and Pieter Swart. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference (SciPy2008), pp. 11-15, 2008
Gabriel Y. Handler and Isracl Zang. A dual algorithm for the constrained shortest path problem. Networks, 10(4):293-30) 0098,,0000000 1980. doi: https://doi.org/ m00.1000//tt..333000000000
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-100 107, 1968. doi:
10.1109/SSSC.198833000 300136.
Wolfgang Hörmann. rejection technique for sampling from t-concave distributions. ACM Trans. Math. Softw., 21(2):182-19) jun 1995. ISSN 0098-3500. doi: 10. 10.1145/2030992223300. URL https://doi.org:
10. 1 1445/2030822... 203089
Huiwen Jia, Cong Shi, and Siqian Shen. Multi-armed bandit with sub-exponential rewards. Operations Research Letters, 49(5):728 733, 2021. ISSN 0167-6377.
14

---

Published in Transactions on Machine Learning Research (11/2023)
H.C. Joksch. The shortest route problem with constraints. Journal of Mathematical Analysis and Applications, 14(2):191-197 1966. ISSN 0022-247X. doi: http:://bbaccoo///oo.00002222220
URL https:
//www www..e/eeneccireet..coo//o///eee wwt.ppcwww........e.aaaaa.aaaaaa
Emilie Kaufmann. On bayesian index policies for sequential resource allocation. The Annals of Statistics, 46(2):842-863) 2018. ISSN 00905364, 21688966.
Emilie Kaufmann, Olivier Cappe, and Aurelien Garivier. On bayesian upper confidence bounds for bandit problems. In Neil D. Lawrence and Mark Girolami (eds.), Proceedings of the Fifteenth International Con- ference on Arlificial Intelligence and Stalislics, volume 22 of Proceedings of Machine Learning Research, pp. 592-60 290, La Palma, Canary Islands, 21-23 Apr 2012a. PMLR.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Nader H. Bshouty, Gilles Stoltz, Nicolas Vayatis, and Thomas Zeugmann (eds.); Algorithmic Learning Theory, pp. 199 213, Berlin, Heidelberg, 2012b. Springer Berlin Heidelberg. ISBN 118-3-642-34106--- doi: 10.1007/978-3 00000/9977-------38-- -44-34106-99
David G. Kendall. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded markov chain. The Annals of Mathemalical Stalistics, 24(3):338 354, 1953. ISSN 00034851.
URL http://www.jstttt
horg/stalle///// org/stablee2236285 2236285
Ki-Beom Lee, Mohamed A. Ahmed, Dong-Ki Ki Kang, and Young-Chon Kim. Deep reinforcement learning based optimal route and charging station selection. Energies, 13(23). 2020. ISSN 1996-1073. doi: 10.3390/ en13236255. URL
62555
Keqin Liu and Qing Zhao. Adaptive shortest-path routing under unknown and stochastically varying link states. In 2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoe and Wireless Networks (WiOpt), pp. 232-237, 2012.
Tyler Lu, David Pal, and Martin Pal. Contextual multi-armed bandits. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 485-492, Chia Laguna Resort, Sardinia, Italy, 13 15 May 2010. PMLR.
Robert B. Miller. Bayesian analysis of the two-parameter gamma distribution. Technometrics, 22(1):65 69, 1980. doi: 10.1080/00400 000/00000100.111900 190000.611000.111102200000000000
Open Charge Map. Open Charge Map the global public registry of electric vehicle charging locations.
httpp:///ppeccaargemap org. 2022.
OpenStreetMap contributors. Planet dump retrieved from hutps///planet..omm.rr https://www openstreetmap.oom org. 2022.
Tao Qian, Chengcheng Shao, Xiuli Wang, and Mohammad Shahidchpour. Deep reinforcement learning for charging navigation by coordinating smart grid and intelligent transportation system. IEEE Transactions on Smart Grid, 11 (2)):17144-172, 2020. doi:
11SG.2019.0942550
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathemaliccs of Operalions Research, 39(4):1221 -221112333 2014.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018. ISSN 1935-8237. doi: 10. 1561/2200000070.
Martin Sachenbacher, Martin Leucker, Andreas Artmeier, and Julian Haselmayr. Efficient energy-optimal routing for electric vehicles. In Proceedings of the Twenly Fifth AAAI Conference on Artificial Intelligence, AAAI'11, pp. 1402-1407, AAAI Press, 2011.
Alfonso Shimbel. Structure communicatin nets. In Proceedings of the symposium on information net- works, pp. 199 203. Polytechnic Institute of Brooklyn, 1954.
15

---

Published in Transactions on Machine Learning Research (11/2023)
Timothy M. Sweda, Irina S. Dolinskaya, and Diego Klabjan. Adaptive routing and recharging policies for electric vehicles. Transportation Science, 51(4):13661344) 2017. doi: 10.1287/urs:22016.0722
W.R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3 44::245-222444 1933. doi: 10.2307
Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In Jennifer Dy and An- dreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5114-5122. PMLR, 10-15 Jul 2018
Zhenhua Zou, Alexandre Proutiere, and Mikael Johansson. Online shortest path routing: The value of information. In 2014 American Control Conference, pp. 2142 2147, 2014. doi: D0.1009/AC.2014.0000
16

---

A vertex A vertex (alternative) Source verlex Target vertex An edge A path Shortest path (implicitly between specified source and target vertices) Shortest path between vertices and u' Set of paths in road graph between source and target vertices Feasibility graph Feasibility graph vertices Feasibility graph edges Published in Transactions on Machine Learning Research (11/2023)
A Appendix
Notation
Description
Groad
Road graph Road graph vertices Road graph edges Vector of road graph edge travel times Road graph travel time of edge e Road graph travel time of path p Road graph energy consumption of edge e Road graph energy consumption of path p Charging station vertices Charging station power (actual) of vertex Charging station maximum power of vertex Charging station minimum power of vertex
yroad
grood
road
proad
road
'p
toad
eroad
V ceharge
Qu charge
La max
u
u'
are
trg
p
p
P(a,a")
Proad
atte)
Gfeasible
Disssible
gleasible
Epath
Edges corresponding to shortest paths between charging stations in road graph Path travel time between vertices and u' Charging time required for travel between vertices and u' Qucue time required for charging station at vertex Feasibility graph travel time of edge e Path energy consumption between vertices u and u' Maximum battery capacity of vehicle Minimum battery capacity of vehicle Queue time distribution rate paramcter of vertex u Shape prior parameter for queue time rate parameter, of vertex u Rate prior parameter for queue time rate parameter, of vertex u Shape posterior parameter for queue time rate parameter, at time / and vertex Rate posterior parameter for queue time rate parameter, at time & and vertex Charging power distribution shape parameter of vertex Charging power distribution rate parameter of vertex First prior parameter for charging power parameters, of vertex u
path
(u.a")
charge
(u,a")
Ta quene
Te foasible
path
gmaa
etin
queue i
a 0.0
gqueue
4.0
a utt
gquene
at charge
gcharge
charge
u,,0
7a.0
charge
Second prior parameter for charging power parameters, of vertex Third prior parameter for charging power parameters, of vertex First posterior parameter for charging power parameters, at time t and vertex u
ccbarge
Sa.0
charge
n uut
Tutt
charge
Second posterior parameter for charging power parameters, time t and vertex Third postcrior parameter for charging power parameters, time t and vertex
chaage
Sa.t
Table 4: Summary of the notation used throughout the paper.
Continued on the next page
17

---

Published in Transactions on Machine Learning Research (11/2023)
Notation
Description
t
Time step Time horizon
T
Pt
Path (action) selected by CMAB algorithm at time & Loss of path p at time f Vector of all parameters fcasibility graph True underlying (unknown) vector of all parameters of leasibility graph Vector of parameters (Aqueue, oeharge, (gcharge) of vertex Expected loss function, w.r.t. parameter vector 0, applied to path p Expected charging time of edge (u, u'), given parameters a and Estimated charging time of edge (u, u'), given parameters a and B Regret of CMAB algorithm at horizon T Exploration probability of the Epsilon-greedy CMAB algorithm
Le(p)
o"
On
Se(p)
ga,o(u, u()
Ja,elu, w²)
(egret(T)
Fqueue
Estimate mean queue time, for vertex u
Aqueue
Estimate of queue time rate parameter, for vertex Estimate of charging power shape parameter, for vertex u Estimate of charging power rate parameter, for vertex Quantile function for distribution and probability value Vehicle mass Gravitational acceleration Rolling resistance coefficient Length of the road segment, for edge Air drag coefficient Frontal surface area of vehicle Maximum speed of the road segment, for edge e Air density
a ccharge
Geharge
(v,))
m
g
C,
droad
Ca
A
road
p
y
Battery-to-wheel energy conversion efficiency Table 4: Summary of the notation used throughout the paper.
18


Reviews:
[{"review_id": "vBXb61gZFu", "reviewer": "Reviewer_r8md", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This study is the first to address the challenging real-world problem of charging station selection in a partial information setting using a multi-armed bandit approach.\n\n2. This work gives an example of a large-scale real-world application of multi-armed bandit. To achieve such scalability, they introduce the transformation of the road graph into a feasibility graph and precompute feasible paths between charging stations to improve run-time efficiency.\n\nConcerning point 2, I believe this work is a very interesting and important adaption of combinatorial bandits to solve real-world problems.\n\nHowever, there are some issues to be considered in the revised version.\n\nMajor issue:\n１：Presentaion\n\nThere needs to be a clear separation between the definition of notations and quantities and the formulation of the problem, such as what is given as the bandit problem.\nIn other words, in Section 4: CMAB formulation, please be more explicit about which parameters are known, and for which parameters, when and how the observations are obtained, and the assumptions about the observations.\n\nPresentation for the static problem formulation also has issues:\nSection 3.1 merely defines the path problem in Equation 1. Charging stations and energy consumption are not relevant here. Or did you use quantities related to charging stations and associated energy consumption in the modeling of Equation 1?\n\nIn the paragraph \"The general resource-constrained shortest path problem (Joksch, 1966) (with energy as the resource) is still computationally hard, especially when resource ....\"\nCould you please specify the exact assumptions when you refer \"with these assumptions\", to consider computational efficiency? Without a definition of  “resource-constrained shortest path problem”, the statement of this graph is unclear.\n\nBecause of the above\nIt is very unclear to understand the \"3.3 Probabilistic queue and charging times\" formulation.\n\n\n2: Why a Bayesian approach is more desired here? \n\n\nIt is unclear why a Bayesian approach was taken to solve this problem, whereas the frequency-based approach is a standard solution in CMAB literature. In particular, [Chen 2013] proposed the CUCB algorithm that can be used with approximate oracles, and subsequent studies propose a variant of CUCB for extensions. HOWEVER, unless I am missing something, this study does not apply CUCB to solve their problem, and it is unclear why.\n\n\nMinor issue:\n\n1.What is the domein for \\varepsilon_e^{road} and \\tau_2^{road}? Is it in \\mathbb{R} or \\mathbb{N}?\n\n2. Which set of location of charging stations \\mathcal{V}^{charge} are known to the agent?\n\n3. \\varrho^{max} and \\varrho^{min} are known to the agent?\n\n4. Are a maximum battery capacity ε_max and minimum battery capacity ε_min are known to the agent?\n\n5. Can you write this assumption “we assume that each charging session has to fully charge the battery.” with mathematical formulation?\n\n\n6. Weighted directed graphs can be given in the form G=(V,E,w). Superscripts such as {road} reduce readability.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this study, they develop an online self-learning algorithmic framework for BEV navigation. They view the task as a sequential decision-making problem under uncertainty, between exploring charging stations to learn more information about them and using previously collected knowledge to select charging stations that are likely to be good charging stations. To address the trade-off, they model it as a combinatorial semi-bandit problem. Within this framework, this paper adopts a Bayesian approach with conjugation that is new in the bandit literature.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the major and minor issues above.", "broader_impact_concerns": "I do not see a negative social impact by this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NU79ZZjXMg", "reviewer": "Reviewer_243U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThe considered problem, long-distance navigation for battery electric vehicles, is very interesting and important in transportation applications. The proposed formulation, especially the formulation of travel time, queue time and charging time, is novel and effectively characterizes the time cost of battery electric vehicles.\n2.\tThis work provides extensive experimental results on real-world country-sized data, including road network data for Norway, Sweden and Finland. This demonstrates the practical performance of the proposed algorithmic framework, and makes a nice empirical contribution to the multi-armed bandit community.\n\n**Weaknesses:**\n\n1.\tIt seems that this work does not provide theoretical analysis for the proposed algorithms, e.g., the regret analysis, which is important for multi-armed bandit problems.\n2.\tThe combinatorial bandit part in the proposed algorithmic framework seems a straightforward application of existing algorithms, i.e., epsilon-greedy, Thompson Sampling and BayesUCB, which reduces the novelty of algorithm design.\n3.\tIs the experiment open-source?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work addresses the problem of long-distance navigation for battery electric vehicles, where one or more charging sessions are required to reach the intended destination. The authors propose a combinatorial semi-bandit framework for exploring the road network to learn the parameters of the queue time and charging power distributions. They first present a method for transforming the road network graph into a graph of feasible paths. Then, they develop a Bayesian approach to model the stochastic edge weights, utilizing conjugate priors for the one-parameter exponential and two-parameter gamma distributions. Finally, they use combinatorial versions of Thompson Sampling, BayesUCB and epsilon-greedy to solve the problem. They provide experimental results on real-world road network datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the review on weaknesses above.", "broader_impact_concerns": "I do not have ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kVnYMnIKmU", "reviewer": "Reviewer_TZzB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- routing problem with energy constraints is becoming a relevant problem with the deployment of electric transportation.\n- the paper is well written and clearly presented.\n- Several variants of learning algorithms are presented. \n\nWeaknesses:\n1. What is meant by \"queuing delay\" is not clear. In particular, the justification of this queueing delay by an M/M/1 model seems very far-fetched.\n2. (linked to the previous point): congestion is not modeled.\n3. The problem is a minor variation of a combinatorial bandit problem where the energy constraint is added.\n4. Is it not clear if the studied problem corresponds to a realistic model for two reasons:\n   - in practice, one would probably have prior knowledge of delays and/or charging times, which make the learning problem less relevant\n   - the case when the delays or charging time are unknown would probably be when there is congestion, in which case the problem would have time-varying parameters (that are not considered here).\n5. The novelty is somehow limited as it is a variation of the classical online routing problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an adaptation of a classical online routing problem to incorporate charging delays. As for the classical routing problem, the problem is viewed as a combinatorial bandit problem where agent choose the set of routes. The paper contains mostly three contributions:\n1. The modelization of the problem\n2. How to adapt classical learning algorithm (UCB variants and Thompson sampling) to this problem\n3. An experimental validation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The main change requested concern my weakness 1. The model need not necessarily be changed by the discussion should be rewritten.", "broader_impact_concerns": "This work is mostly a theoretical work and I do not foresee any broader impact problems.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers are in favor of acceptance, although 1 more so (accept) than the others (2 leaning accept). I concur with the reviewers that, overall, the paper deserves acceptance. As several reviewers point out, the technical novelty is slightly on the weak side. At the same time, the application and experiments are quite impressive, which outweighs the negatives.
Decision: Accept (poster)