# Smart Procurement of Naturally Generated Energy (SPONGE) for Plug-in Hybrid
Electric Buses

Joe Naoum-Sawaya, Emanuele Crisostomi, Mingming Liu, Yingqi Gu, and Robert
Shorten J. N. Sawaya is with the Ivey Business School, University of Western
Ontario, 1255 Western Rd, London, Canada (e-mail: jnaoum-sawaya@ivey.ca).E.
Crisostomi is with the Department of Energy, Systems, Territory and
Constructions Engineering, University of Pisa, Italy (e-mail:
emanuele.crisostomi@dsea.unipi.it).Y. Gu and M. Liu and R. Shorten are with
the School of Electrical, Electronic and Communications Engineering,
University College Dublin, Ireland (e-mail<EMAIL_ADDRESS>mingming.liu@ucd.ie).R. Shorten is also with IBM Research, Dublin, Ireland
(e-mail: robshort@ie.ibm.com).

###### Abstract

We discuss a recently introduced ECO-driving concept known as SPONGE in the
context of Plug-in Hybrid Electric Buses (PHEB)’s.Examples are given to
illustrate the benefits of this approach to ECO-driving. Finally, distributed
algorithms to realise SPONGE are discussed, paying attention to the privacy
implications of the underlying optimisation problems.

###### Abstract

In this paper we present a new idea for ECO-driving for buses. It is an IoT
concept - that instead of connecting devices in space, connects devices in
time via forecasting engines. Basically, a bus uses knowledge of the available
energy at the next charging step, to optimise its performance beforehand. The
system can be implemented using available (free) forecasting engines, and
existing distributed optimisation tools. A sample implementation is described
using a Toyota plug-in Prius (as a proxy for a hybrid bus). Apart from the
forecasting and optimisation analytics, the only additional work needed was
the development of an interface unit to control EV mode of the vehicle, and
the development of a smart-phone app. Future work will investigate impacts of
our approach on the grid, integration of the ideas into the hybrid drive
cycle, and using driver behaviour as an input into the design of the utility
functions.

###### Index Terms:

Primary Topics: Number 7, Number 8; Secondary Topic Keywords: Routing,
Distributed Systems

Note to Practitioners:

Primary and Secondary Keywords

##  I Introduction

We discuss a recently introduced holistic ECO-driving concept known as SPONGE
in the context of Plug-in Hybrid Electric Buses (PHEB)’s. PHEB’s are
increasingly seen as an effective tool in combating air pollution in our
cities, and as a tool for reducing our cities reliance on fossil fuels
(thereby reducing greenhouse gas emissions) [1, 2]111See
https://chargedevs.com/newswire/ultramodern-plug-in-buses-go-into-service-in-
gothenburg/ for further examples.. Consequently, the design and operation of
such buses has been the subject of much research interest. Hitherto,
significant research effort has focused on improving the fuel economy while
guaranteeing that both the engine and the electric machine work in the high-
efficiency area; typically, by taking into account knowledge of both bus
routes and passenger loadings in a predictive manner. Selected examples of
work in this direction can be found in [3, 4, 5].

Our objective in this paper is to extend this line of inquiry further. Our
basic setting is to consider a bus operator that has access to a fixed amount
of renewable energy on a daily basis. For example, some operators may own
solar farms or have access to wind generation. It makes sense to use this free
energy before consuming electrical energy that is bought from the grid, and in
situations where there is an oversubscription for this free energy, the
operator then has a choice as to how this energy is distributed to each bus.
For example, some drivers may be more efficient than others. Thus, it makes
eminent economic sense, to distribute this free energy to reduce the impact of
less efficient drivers in optimising the hybrid engine cycle, while at the
same time ensuring that sufficient energy is consumed to make room for every
unit of free energy that arrives the next time the buses recharge.
Specifically, SPONGE for buses operates as follows.

  * A.

We introduce the forecast of generation of energy from renewable resources on
a day ahead basis as a further variable to influence the energy management
system for the bus operator.

  * B.

We use this forecast to prioritise the manner in which individual buses
dissipate electrical energy.

  * C.

We do this by prioritising the utilisation of energy from renewable sources
over other resources, and by taking account of the fact that some
drivers/routes are more energy efficient than others.

Prioritising energy from renewable sources in this manner introduces a number
of benefits for the bus operator and society.

  * •

The use of energy from renewable sources (e.g., wind turbines, dynamic water
power, or solar power) achieves environmental health benefits with respect to
the use of the “power grid average” electricity [6].

  * •

Financial benefits for the bus operator.

  * •

Depleting PHEBs’ batteries of a pre-specified quantity of energy allows better
grid-demand balancing. That is, the energy provider knows in advance how much
energy will be required by PHEBs, when connected for charging. This makes the
electrical load of PHEBs to be fully predictable and dispatchable, thus
mitigating the burden of the power grid to accommodate a not-known-in-advance
electrical load.

Note that the proposed charging problem closely resembles the widely discussed
practice of demand side management, where electricity customers shift their
electrical loads taking into account the expected availability of energy from
renewable sources (e.g., solar panels on the roofs of their houses). In fact,
in this paper we are considering the possibility that buses accommodate the
consumption of their batteries considering the amount of energy that will be
available from renewable sources when recharging.

This paper extends previous work of some of the authors in [7] for the case of
electric cars. While the basic idea of matching energy from renewable sources
with space in the battery of the EVs remains the same, the case of PHEBs
substantially differs from the case of Plug-in Hybrid Electric Vehicles
(PHEVs) in several ways: (i) the a-priori knowledge of bus routes can be
included in the formulation of the optimisation problem; (ii) we show that
maximisation of $CO_{2}$ savings can be formulated as an optimisation problem
as a function of the fraction of time that a PHEB spends in EV mode; (iii) the
optimisation procedure can now be computed in a batch fashion, thus shifting
the interest of optimisation algorithms from the time of convergence to other
aspects, such as privacy preservation and communication costs of the
algorithms. With this latter aspect in mind, our final contribution is to give
a brief comparison of two competitive optimisation algorithms.

##  II Sponge Problem Formulation

Let $\mathcal{N}=\left\\{1,2,...,N\right\\}$ denote the set of $N$ PHEBs
participating to the SPONGE programme. We shall make the following
assumptions:

  * •

We assume that after a number of trips along their (different) routes, the $N$
PHEBs stop for charging at the bus station. For instance, we can assume that
the PHEBs will not drive from 11pm to 6am, and they will be charged in this
time frame;

  * •

We also assume that a 24-hour ahead forecast of energy from the renewable
energy sources available to the operator will be available as well (e.g., a
forecast of how much energy will be generated by the wind plants connected
with the charging station at night time). We denote this amount of energy
available by $E_{\textrm{av}}$;

  * •

Early in the morning, before being dispatched along their routes, the buses
will compute how the energy $E_{\textrm{av}}$ should be optimally shared among
themselves during the day (i.e., in terms of energy consumption of their own
batteries);

  * •

In order to compute the optimal allocations of energy, we shall assume that
each PHEB is equipped with a device to transmit messages to the central
infrastructure via Vehicle-to-Infrastructure (V2I) technology;

  * •

The central infrastructure has the ability to broadcast messages to the whole
network of PHEBs using some Infrastructure-to-Vehicles (I2V) technology.

Note that in our set-up we shall not require vehicles to exchange information
among themselves, and thus, we shall not require PHEBs to be equipped with
Vehicle-to-Vehicle (V2V) communication devices. A schematic diagram of the
above SPONGE paradigm is illustrated in Fig. 1.

Figure 1: A schematic diagram of the SPONGE programme

When travelling along their routes, the buses will be able to choose when it
is more convenient to switch from electric mode to ICE mode (i.e., using the
Internal Combustion Engine) and back. In this context, we denote by $d_{i}$
the energy consumption by the $i^{\prime}$th bus along its trip. Then we are
interested in computing the solution of the following optimisation:

$\left\\{\begin{array}[]{l}\underset{d_{1},d_{2},\ldots,d_{N}}{\max}\quad\sum\limits_{i\in\mathcal{N}}f_{i}\left(d_{i}\right)\\\
\\\
{\text{s.t.}}~{}\sum\limits_{i\in\mathcal{N}}d_{i}=E_{\textrm{av}}\end{array}\right..$
(1)

In the optimisation problem (1), the terms $d_{i}$ can be interpreted as a
“budget” of energy that is allocated to the $i^{\prime}$th bus in order to
maximise a utility function of interest, such that the sum of the energy
budgets allocated to all the buses matches $E_{\textrm{av}}$ as in the SPONGE
spirit. Although in principle the utility function
$\sum\limits_{i\in\mathcal{N}}f_{i}\left(d_{i}\right)$ may be chosen in an
arbitrary fashion, to represent any utility, in this work we shall explore the
particular case where one is interested in the utility of $CO_{2}$ emissions
savings $f_{i}\left(d_{i}\right)$ as achieved by each bus. Clearly, each
$f_{i}\left(d_{i}\right)$ is an increasing function of $d_{i}$ as no $CO_{2}$
emissions are saved when the bus travels all the time in ICE mode, while no
pollution occurs when all the vehicles travel in electric mode all the time.
The utility functions of 15 PHEBs that we shall study are shown in Fig. 2 as a
function of the percentage of the use of the electrical engine for each bus.
These functions are constructed from real data and the next section will
explain how the utility functions are designed in detail. In addition, Section
III will describe an attractive distributed solution of the optimisation
problem (1).

Figure 2: Utility functions of 15 PHEBs in Dublin city. Note that some buses
pollute more than others (and thus, have a greater potential in terms of
$CO_{2}$ savings) depending on the characteristics of their routes (e.g.,
speed limits).

###  II-A Construction of the utility function

Electrical energy consumption: Under the assumption that a vehicle is
travelling at a constant speed $s$, the amount of electrical energy
consumption of vehicles can be modelled as a convex function of $s$, see [8,
9] for instance. The convex function depends in turn on, among other things,
the physical characteristics of the bus. In our work, we used the real energy
consumption data of a BYD electric bus [9] and noticed that it can be
accurately approximated with a quadratic function of the vehicle speed $s$ as

$e(s)=\alpha_{0}s^{2}+\alpha_{1}s+\alpha_{2}.$ (2)

where $\alpha_{0},\alpha_{1},\alpha_{2}$ are all constant parameters. Using a
conventional least square method to fit the real energy consumption we
obtained $\alpha_{0},\alpha_{1}$ and $\alpha_{2}$ equal to
$\frac{22}{28777},\frac{-213}{2599}$ and $\frac{2384}{783}$, respectively, and
the corresponding utility function is depicted in Fig. 3. In particular, note
that the energy is large when the speed is large, which is caused by the fact
that power consumption increases with the cube of the speed for aerodynamic
reasons, and that the energy is large again when the speed is very low, due to
the fact that travel times increase.

Figure 3: A typical energy cost function for PHEBs.

Saving of $\boldsymbol{CO_{2}}$: In an analogous manner to power consumption,
$CO_{2}$ emissions may also be computed as a function of the speed of the
vehicles, by adopting for instance the following well-known average-speed
model (from [10])

$\begin{gathered}h(s)=\text{k}\left(\frac{\text{a}+\text{b}s_{i}+\text{c}s^{2}+\text{d}s^{3}+\text{e}s^{4}+\text{f}s^{5}+\text{g}s^{6}}{s}\right),\end{gathered}$
(3)

where
$\text{a},\text{b},\text{c},\text{d},\text{e},\text{f},\text{g},\text{k}\in\mathbb{R}$
are used to specify different levels of emissions by different classes of
vehicles. In particular, in our work we used the cost function depicted in
Fig. 4, that corresponds to the vehicle code R203 in [10] (i.e., diesel buses
with up to 15 tonnes of gross vehicle mass).

Figure 4: $CO_{2}$ emission cost function for PHEBs.

Utility functions $\boldsymbol{f_{i}}$: As anticipated in Section II, the
overall utility function $f_{i}(d_{i})$ quantifies how much $CO_{2}$ has been
saved by the $i^{\prime}$th bus, provided that the bus is allowed to spend a
budget of $d_{i}$ units of energy when traveling along its route. In the
following, we shall assume that the whole path traveled by a bus during the
day can be split into a number of very small sections, corresponding to the
distance traveled by a bus in one second. For simplicity, we shall further
assume that speed limits do not change within sections, and that a bus will
travel at a speed equal to the speed limit within the section. Finally, we
shall denote by $\mathcal{R}_{i}$ the set of all the sections traveled by the
$i^{\prime}$th PHEB, and by $\gamma_{l}$ the fraction of the time that a PHEB
will travel in EV mode along the $l^{\prime}$th section of the route. Due to
the fact that all bus routes are fixed and known a priori, then the utility
functions can be computed off-line by optimally deploying the energy budget
$d_{i}$ along the routes as follows:

$\left\\{\begin{array}[]{l}f_{i}(d_{i})=\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\gamma_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\gamma_{l}=d_{i}\\\ \\\ 0\leq\gamma_{l}\leq
1,l\in\mathcal{R}_{i}\end{array}\right.$ (4)

where $L(l)$ denotes the length of the $l^{\prime}$th section of a trip.

###### Theorem 1

The utility functions $f_{i}(d_{i})$ are concave.

Proof : By definition (4)

$\left\\{\begin{array}[]{l}f_{i}(d_{i})=\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\gamma_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\gamma_{l}=d_{i}\\\ \\\ 0\leq\gamma_{l}\leq
1,l\in\mathcal{R}_{i}.\end{array}\right..$ (5)

Consider two variables $d_{i}^{1}\neq d_{i}^{2}$, we can show that

$\left\\{\begin{array}[]{l}f_{i}(d_{i}^{1})=\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\gamma_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\gamma_{l}=d_{i}^{1}\\\ \\\ 0\leq\gamma_{l}\leq
1,l\in\mathcal{R}_{i}.\end{array}\right.,$ (6)

Given a $0<\lambda<1$, it then follows that

$\left\\{\begin{array}[]{l}\lambda
f_{i}(d_{i}^{1})=\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\lambda\gamma_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\gamma_{l}=d_{i}^{1}\\\ \\\ 0\leq\gamma_{l}\leq
1,l\in\mathcal{R}_{i}\end{array}\right.,$ (7)

and

$\left\\{\begin{array}[]{l}\lambda
f_{i}(d_{i}^{1})=\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\bar{\gamma}_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\frac{\bar{\gamma}_{l}}{\lambda}=d_{i}^{1}\\\ \\\
0\leq\frac{\bar{\gamma}_{l}}{\lambda}\leq
1,l\in\mathcal{R}_{i}.\end{array}\right..$ (8)

Thus,

$\left\\{\begin{array}[]{l}\lambda
f_{i}(d_{i}^{1})=\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\bar{\gamma}_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\bar{\gamma}_{l}=\lambda d_{i}^{1}\\\ \\\
0\leq\bar{\gamma}_{l}\leq\lambda,l\in\mathcal{R}_{i}.\end{array}\right..$ (9)

Similarly, we can show that

$\left\\{\begin{array}[]{l}(1-\lambda)f_{i}(d_{i}^{2})=\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\hat{\gamma}_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\hat{\gamma}_{l}=(1-\lambda)d_{i}^{2}\\\ \\\
0\leq\hat{\gamma}_{l}\leq(1-\lambda),l\in\mathcal{R}_{i}\end{array}\right.,$
(10)

where adding (9) and (10) is equivalent to

$\left\\{\begin{array}[]{l}\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot(\bar{\gamma}_{l}+\hat{\gamma}_{l})\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\bar{\gamma}_{l}=\lambda d_{i}^{1}\\\ \\\
\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\hat{\gamma}_{l}=(1-\lambda)d_{i}^{2}\\\ \\\
0\leq\bar{\gamma}_{l}\leq\lambda,l\in\mathcal{R}_{i}\\\ \\\
0\leq\hat{\gamma}_{l}\leq(1-\lambda),l\in\mathcal{R}_{i}\end{array}\right.,$
(11)

which is less or equal to

$\left\\{\begin{array}[]{l}\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot(\bar{\gamma}_{l}+\hat{\gamma}_{l})\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot(\bar{\gamma}_{l}+\hat{\gamma}_{l})=\lambda
d_{i}^{1}+(1-\lambda)d_{i}^{2}\\\ \\\
0\leq\bar{\gamma}_{l}+\hat{\gamma}_{l}\leq\lambda+(1-\lambda),l\in\mathcal{R}_{i}.\end{array}\right..$
(12)

This implies that

$\left\\{\begin{array}[]{l}\underset{\gamma_{l}}{\max}\quad\sum\limits_{l\in\mathcal{R}_{i}}h\left(s_{\textrm{max}}(l)\right)\cdot\gamma_{l}\\\
\\\
{\text{s.t.}}~{}\sum\limits_{l\in\mathcal{R}_{i}}e(s_{\textrm{max}}(l))\cdot
L(l)\cdot\gamma_{l}=\lambda d_{i}^{1}+(1-\lambda)d_{i}^{2}\\\ \\\
0\leq\gamma_{l}\leq 1,l\in\mathcal{R}_{i}\end{array}\right.$ (13)

$=f_{i}(\lambda d^{1}_{i}+(1-\lambda)d^{2}_{i})$. Therefore $\lambda
f_{i}(d^{1}_{i})+(1-\lambda)f_{i}(d^{2}_{i})\leq f_{i}(\lambda
d^{1}_{i}+(1-\lambda)d^{2}_{i})$ and by definition the function $f_{i}$ is
concave. ${\bf Q.E.D}$.

Remark: Note that $\mathcal{R}_{i}$ is the set of all sections traveled by a
bus during a day (or in general, between two different runs of the
optimisation algorithm). Given that bus routes are typically cyclic, this
implies that the same stretch of a road might appear more times in
$\mathcal{R}_{i}$, and possibly with different values of optimal $\gamma_{l}$.

Remark: Roughly speaking, the utility functions describe the maximum $CO_{2}$
savings that can be achieved by a bus, given that the bus is allocated a
budget of $d_{i}$ units of energy that can be spent in travelling in electric
mode. The knowledge of the route is used to optimally decide when it is best
to drive in ICE mode and when in electric mode in order to maximise $CO_{2}$
savings without exceeding the energy budget. Built on such utility functions,
the next section will show how to optimally allocate the expected energy
$E_{av}$ into the single budgets.

##  III Algorithms and Optimal Solution

In principle, many different methods may be used to solve the optimisation
problem (1) that arises in our work (for instance ADMM-like algorithms [11]).
ADMM (Alternating Direction Method of Multipliers) is a popular optimisation
algorithm, that has been recently proposed as an evolution of other well-known
optimisation algorithms, like the dual ascent and the method of multipliers.
As an alternative to ADMM-like algorithms, our choice here is to adopt an
AIMD-like algorithm [12] to solve the problem in a distributed fashion. Such a
choice is motivated by many reasons:

  * •

Low-communication requirements: Although we have presented here a simple case
study with a small number of buses, the same programme can be easily
generalised to include hundreds of buses. Also, the batch optimisation
formulation might be solved in real-time to account for non fully-predictable
aspects (for example to respond to traffic peaks or weather forecast updates).
In this context, it is convenient to consider the communication cost of
solving the optimisation algorithm. AIMD based optimisation can be solved
using only intermittent binary feedback and can thus, unlike many other
distributed optimisation techniques, be solved without the need to broadcast
of the Lagrange multipliers in a pseudo-continuous manner.

  * •

Privacy-preservation requirements: In our application, the utility functions
$f_{i}(d)$ potentially reveal sensitive private information. For example, when
formulated in a slightly different manner, these functions may reveal how good
a particular driver is on a given route. This information is potentially very
useful for an employer and could potentially be used in a nefarious manner. In
addition, in unionised environments, revealing these functions to an employer
could also be of concern and consequently impede the adaptation of ideas like
SPONGE. Given this context, a natural question is whether the distributed
optimisation can be solved without revealing private information. As we shall
see, AIMD has some very nice privacy properties.

  * •

Agent actuation: AIMD requires very little actuation ability on the agent-
side. This is in contrast to ADMM where at each time step, agents must solve a
local optimisation problem.

  * •

Algorithm parameterisation: In AIMD the gain parameters of the network are
independent of network dimension; rather, they only depend on the largest
derivative over all utility functions. Thus, selecting a gain for the
algorithm is extremely simple in the case of AIMD.

As we shall further discuss in the following section, AIMD is thus a
convenient alternative to ADMM, when the previous aspects are relevant.

###  III-A AIMD Algorithm

Additive Increase Multiplicative Decrease (AIMD) algorithms were originally
applied for solving issues arising in network congestion in the Internet [13].
To date, this idea has been widely explored for the design of practical
algorithms for other applications as well, as for instance, network
applications see [14, 15, 16], and smart grid applications see [17, 18, 19].
More recently, an unsynchronised AIMD algorithm based on the nonhomogeneous
place-dependent Markov chains model was proposed in [12] to solve utility
optimisation problems. The pseudo-code of the proposed algorithm is given in
Algorithm 1.

Algorithm 1 Unsynchronised AIMD Algorithm

1:Initialisation: $k=1$, $d_{i}(k)=0$;

2:Broadcast the parameter $\Gamma$ to the entire networks;

3:while $k<k_{\textrm{max}}$ do

4: if $\sum_{i=1}^{N}d_{i}(k)<E_{\textrm{av}}$ then

5: $d_{i}(k+1)=d_{i}(k)+\alpha$

6: else if with probability
$p_{i}(k)=\Gamma\frac{1}{\overline{d_{i}}(k)f_{i}^{\prime}(\overline{d_{i}}(k))}$
then

7: $d_{i}(k+1)=\beta d_{i}(k)$

8: else

9: $d_{i}(k+1)=d_{i}(k)+\alpha$

10: end if

11: $k=k+1$

12:end while

Note that the algorithm does not compute the optimal budgets $d_{i}$ in a
single step, but in an iterative fashion, as $d_{i}(k)$ represents the value
of the unknown energy to be allocated to the $i^{\prime}$th PHEB, computed at
time step $k$. For large values of $k$, $d_{i}(k)$ will eventually converge to
the optimal solution that maximises the environmental benefits (while still
satisfying the energy constraint). In Algorithm 1, $k_{\textrm{max}}$
represents the maximum number of iterations before the algorithm stops (e.g.,
after five minutes of iterations).

The basic idea of Algorithm 1 is that if the sum of the $d_{i}(k)$ of all
PHEBs is smaller than $E_{av}$, then each PHEV increases its target energy
consumption $d_{i}(k)$ at the next iteration $k+1$ by a quantity $\alpha$.
However, if the sum of the energy budgets of all PHEVs exceeds $E_{av}$ (this
situation is usually called as a congestion event), then each PHEB decreases
its energy consumption by a multiplicative factor $0<\beta<1$ with probability
$p_{i}(k)=\Gamma\frac{1}{\overline{d_{i}}(k)f_{i}^{\prime}(\overline{d_{i}}(k))}$,
where $\Gamma$ is a constant common broadcast parameter, and
$\overline{d_{i}}(k)$ is the time average of the sequence of $d_{i}(k)$ at
congestion events, up to the last iteration. It is proved in [12] that
$\overline{d_{i}}(k)$ approaches to the optimal solution of the problem when
Algorithm 1 converges and where the optimisation is carried out over the
$f_{i}(\bar{d}_{i})$.

Remark (AIMD): The philosophy underlying the AIMD algorithm is to adjust
$p_{i}(k)$ and $d_{i}(k)$ at every time step $k$ such that for large values of
$k$,
$f_{i}^{\prime}(\overline{d_{i}}(k))=f_{j}^{\prime}(\overline{d_{j}}(k)),~{}\forall
i\neq j\in\mathcal{N}$, or in other words the PHEBs achieve consensus on the
derivatives of their utility functions. This, with strict convexity of the
utility functions, is both necessary and sufficient for optimality when
feasibility is guaranteed. This property is known from elementary optimisation
theory. Algorithm 1 was originally designed in [12] to minimise a cost
function of interest, here we slightly adapt it to maximise $CO_{2}$ savings.
Accordingly, given that each utility function $f_{i}$ in our case is strictly
concave, and that the $p_{i}$ are strictly non-increasing in our problem, then
we can adapt the algorithm in [12] so that consensus is achieved on
$1/f_{i}^{\prime}$, and the convergence and optimality properties of the
algorithm are preserved.

Remark (Privacy): We now make some brief comments concerning the privacy
properties of AIMD based optimisation. Recall that we assume that the central
agent may receive the value $d_{i}$ from agent $i$, and performs the
aggregation $A=\sum_{i=1}^{N}d_{i}$. We also assume that there are no
incentives for an agent to cooperate with the central agent to help deduce the
$f_{i}^{\prime}$; that is, all agents, other than the central agent, are
honest. Given this basic setting, one may discern the following four basic
levels of privacy.

  * (i)

Absolute utility privacy (AUP) : Here, the central agent cannot deduce
$f_{i}(d)$ based on knowledge available to it. This is a basic level of
privacy.

  * (ii)

Relative utility privacy (RUP) : Here the central agent cannot deduce whether
$f_{i}(d)>f_{j}(d)$. This again, is a basic level of privacy.

  * (iii)

Absolute derivative privacy (ADP) : Here, the central agent cannot deduce
$f^{\prime}_{i}(d)$ based on knowledge available to it. This information is
important since it allows the central agents to estimate the price elasticity
of individual agents.

  * (iv)

Relative derivative privacy (RDP) : Here the central agent cannot deduce
whether $f^{\prime}_{i}(d)>f^{\prime}_{j}(d)$.

Privacy preservation is beyond the scope of this paper. However, we note
briefly that the stochastic AIMD algorithm allows us to give guarantees
regarding some of these privacy categories. First since the optimisation is
based on $f^{\prime}_{i}(d_{i})$, the AIMD algorithm can be considered _AUP_
\- and _ADP_ -private. Deducing any $f^{\prime}_{i}(d_{i})$ would require
estimation of the $p_{i}(k)$ in Algorithm 1. Clearly, this is difficult (but
not impossible) except at optimal points. However, since our algorithm only
requires an implicit consensus among all derivatives, one may replace in the
formula for $p_{i}(k)$ (i.e., line 6 of Algorithm 1), $f^{\prime}_{i}(d_{i})$
with $g(f^{\prime}_{i}(d_{i}))$, where $g$ is chosen so that the convergence
conditions in [12] are satisfied. Clearly, without knowledge of the function
$g$, the central agent cannot deduce $f^{\prime}_{i}(d_{i})$ even if the
probabilities $p_{i}$’s are correctly estimated when the algorithm converges.

##  IV SUMO Simulations

###  IV-A Simulation Set-up

In this section, we evaluate the performance of the proposed AIMD algorithm in
a realistic traffic scenario, where vehicular flows are simulated using the
popular mobility simulator SUMO [20]. In doing so, we shall also compare the
results obtained using AIMD with those obtained with the ADMM algorithm.
Finally, we shall also shortly discuss the impact of inaccurate predictions
made by weather forecasting tools (e.g., from solar PV panels). All the
simulations are performed over the road network of Dublin, Ireland, depicted
in Fig. 5, imported from OpenStreetMap [21].

Figure 5: Road network of Dublin City, Ireland, imported from OpenStreetMap,
used in our simulations.

###  IV-B Simulation Results

We assume that 15 PHEBs participate in a SPONGE programme in Dublin city,
Ireland. We further assume that weather forecasting tools predict an
availability of 250 kWh in the next charging period. Ten minutes before
starting their routes, the buses and the CA solve the optimisation problem
using the described AIMD algorithm, and optimally allocate the 250 kWh of
available energy to 15 different bus trips. Fig. 6 compares the overall energy
that would be required for each of the 15 trips when travelling the full route
in EV mode (blue bars) with the optimal allocated budgets (red bars). Fig. 7
shows that the AIMD algorithm converges to the optimal solution that can be
easily computed by solving (1) using a standard nonlinear optimisation solver.
Fig. 8 reveals that the necessary condition for optimality (KKT) has been
achieved when AIMD converges (i.e., the derivatives of the utility functions
converge to the same value). Comparatively, Fig. 9 demonstrates that ADMM
converges to the same solution as AIMD. We note that although ADMM requires
less iterations to converge (around 3,500 iterations) compared to AIMD (around
20,000 iterations), ADMM requires more data to be transmitted to the agents.
For instance, we assume that at each iteration ADMM needs to broadcast a
packet (with multipliers) to all buses in 32 bits, therefore the total data
required for algorithm convergence is $32\times 3500=14$kB. On the other hand,
AIMD needs to transmit one bit for all buses only on congestion events so the
maximum data that is transmitted is less than $4$kB. This shows that AIMD is
competitive from the perspective of communication overhead when compared to
the ADMM algorithm.

Figs. 10-12 illustrate the sections of the road where ICE and EV modes are
used for buses 1 and 2 in a single journey for three different scenarios of
total available energy $E_{av}$: 250kWh, 100kWh, and 50kWh. Clearly, in
scenarios where the available energy is lower, the green sections
corresponding to EV mode are shorter than the scenarios where the available
energy is larger. When $E_{av}=250$kWh the total savings of $CO_{2}$ emissions
for the 15 bus routes is 186.6kg, while the total savings is 83.37kg and
44.30kg for the cases where $E_{av}=100$kWh and $E_{av}=50$kWh, respectively.

Figure 6: Comparison of the required energy and the optimal allocated energy
for 15 bus trips Figure 7: Evolution of AIMD Figure 8: Evolution of
$f_{i}^{\prime}(\overline{d_{i}}(k))$s converges to consensus Figure 9:
Evolution of the distributed ADMM Figure 10: Electrical energy distribution of
two bus routes when $E_{av}=250$kWh. Green lines indicate PHEBs driving in EV
mode and red lines indicate PHEBs in ICE mode Figure 11: Electrical energy
distribution of two bus routes when $E_{av}=100$kWh Figure 12: Electrical
energy distribution of two bus routes when $E_{av}=50$kWh

##  V Comments on the practical implementation of SPONGE

To conclude the paper we now briefly comment on testing and implementation of
the SPONGE algorithm.

A. Large-Scale Traffic Simulator As we have mentioned, all simulations are
based on the SUMO simulation environment. SUMO [20] is an open source,
microscopic road traffic simulation package primarily being developed at the
Institute of Transportation Systems at the German Aerospace Centre (DLR). SUMO
is designed to handle large road networks, and comes with a “remote control”
interface, TraCI (short for Traffic Control Interface) [22], that allows one
to adapt the simulation and to control singular vehicles on the fly.

B. Test Vehicle : While we have not yet implemented SPONGE in a real bus, the
algorithm has been implemented in a real test vehicle. Our test vehicle is a
2015 Toyota Prius VVTi 1.8 5DR CVT Plugin Hybrid vehicle and is pictured in
Fig. 13. The engine management system of the Prius allows the vehicle to be
powered by the ICE alone, the battery, or using a combination of both, and it
is this degree of freedom that we exploit to implement SPONGE. For the purpose
of this programme, we have made some important modifications to the basic
vehicle to make it behave as a context-aware vehicle. First, we automate the
switching of the vehicle from ICE to EV mode by adapting the ÒEVmode buttonÓ
hardware in the vehicle. For this purpose, a dedicated Bluetooth-controlled
mechanical interface was constructed to override the manual EV button based on
signals from a smartphone. The switching is based on GPS location, external
context information, and onboard signals such as speed and battery level.
Second, special-purpose hardware was constructed to permit communication
between a smartphone and the controller area network (CAN) bus. The Prius
provides a CAN access on the vehicle diagnosis On Board Diagnosis II (OBDII)
interface. Our hardware module acts as a gateway between this CAN interface
and the smartphone. The module is directly connected to CAN and to the
smartphone via Bluetooth. Communication to other vehicles, to GPS, and to a
cloud server is also realized using a smartphone device. To control the
driving mode, the software connects via Bluetooth to a mechanical switch to
toggle driving mode between the EV mode and non-EV driving modes. In our
application we use a Samsung Galaxy S III mini (model no. GT-I8190N) running
the Android Jelly Bean operating system (version 4.1.2) and the OBD2 interface
device that we used was the Kiwi Bluetooth OBD-II Adaptor by PLX
Devices.222PLX Devices Inc., 440 Oakmead Parkway, Sunnyvale, CA 94085, USA.
Phone: +1 (408) 7457591. Website: http://www.plxdevices.com.

Figure 13: Field-test vehicle: 2015 Toyota Prius.

C. Weather forecasting : An important component in any real practical
implementation of the SPONGE programme is the ability to have a reasonably
accurate, and cheap, prediction of the expected energy that will be available
for charging $E_{\textrm{av}}$. To obtain a feeling for fidelity of such
tools, we evaluated the accuracy of a free online forecasting tool over a 3
month period. The tool that we evaluated is provided by the Technical
University of Crete and is described in [23], where the energy generated by a
solar plant can be predicted (anywhere in the world) by simply providing the
technical parameters of the plant. We collected real data on-site from PV
panels mounted on the flat roof of the building in University College Dublin,
Ireland. We recorded a total of 100 days and the predicted and the actual
recorded energy are shown in Fig. 14. As also shown in Fig. 15 the predictions
are relatively accurate with 80% of the predictions within 3% of Normalised
Mean Absolute Error (NMAE) and the maximum NMAE is 7%. Thus, our data suggests
that accurate predictions can be performed even for small powers, and even
when a free online tool is employed. As for wind power forecasts, we note that
a recent study in Germany reported that “typical wind-forecast errors for
representative wind power forecasts for a single wind project are $10\%\
-15\%$ root mean square error of installed wind capacity but can drop down to
$6\%\ -8\%$ for day-ahead wind forecasts for a single control area and to
$5\%\ -7\%$ for day-ahead wind forecasts for all of
Germany”333http://www.nrel.gov/electricity/transmission/resource_forecasting.html.
The accuracy may further be increased if other (commercial) tools are
employed. From the previous discussion it appears reasonable to claim that on
average the prediction error is below $10\%$, and this is consistent with
other recent studies as well, see for instance [24] and [25].

Figure 14: Comparison between the real and the predicted energy generated from
PV panels in UCD Figure 15: Histogram of the percentage of NMAE

Comment : While the effect of uncertainty is beyond the scope of this paper,
we note briefly that, it is simple to accommodate for forecasting errors by
buying extra energy, if required, from the outer grid, or by appropriately
using other storage devices, if available. However, interactions with the grid
are not always convenient, either in terms of price, or in terms of
environmental friendliness of the average power mix from the grid (see [26]).
An alternative to this is to formulate an uncertainty description as part of
the optimisation, and this will be part of future work.

##  VI Conclusion

In this paper, we introduce an optimal energy allocation scheme for the SPONGE
system in the context of PHEBs. We describe a distributed AIMD algorithm for
solving the optimisation problem. The main features of the proposed AIMD
approach are the low-communication requirements and the privacy-preserving
properties. The proposed approach is demonstrated on a case study with 15 bus
trips with varying energy profiles. The results demonstrate significant
environmental benefits in terms of $CO_{2}$ emissions that can be achieved
with optimal use of free renewable energies.

## Acknowledgment

The authors gratefully acknowledge funding for this research provided by
Science Foundation Ireland under grant 11/PI/1177. The work of E. Crisostomi
was supported in part by the University of Pisa under Project PRA 2016
“Sviluppo di strumenti di analisi e gestione per l’approvvigionamento e la
distribuzione dell’energia.”

## References

  * [1] D. Lowell, “Comparison of modern CNG, Diesel and Diesel hybrid-electric transit buses: Efficiency & environmental performance,” _Report - M.J. Bradley & Associates, LLC_, 2013.
  * [2] R. D. Jong, M. Ahman, R. Jacobs, and E. Dumitrescu, “Hybrid electric vehicle an overview of current technology and it’s application in developing and transitional countries,” _UNEP. Kenya_ , 2009.
  * [3] F. Tianheng, Y. Lin, G. Qing, H. Yanqing, Y. Ting, and Y. Bin, “A supervisory control strategy for plug-in hybrid electric vehicles based on energy demand prediction and route preview,” _IEEE Transactions on Vehicular Technology_ , vol. 64, no. 5, pp. 1691–1700, 2015.
  * [4] L. Li, C. Yang, Y. Zhang, L. Zhang, and J. Song, “Correctional DP-based energy management strategy of plug-in hybrid electric bus for city-bus route,” _IEEE Transactions on Vehicular Technology_ , vol. 64, no. 7, pp. 2792–2803, 2015.
  * [5] L. Li, B. Yan, C. Yang, Y. Zhang, Z. Chen, and G. Jiang, “Application oriented stochastic energy management for plug-in hybrid electric bus with AMT,” _IEEE Transactions on Vehicular Technology_ , vol. accepted for publication, 2016.
  * [6] C. Tessum, J. Hill, and J. Marshall, “Life cycle air quality impacts of conventional and alternative light-duty transportation in the United States,” _PNAS_ , vol. 111, no. 52, pp. 18 490–18 495, 2014.
  * [7] Y. Gu, F. Häusler, W. Griggs, E. Crisostomi, and R. Shorten, “Smart procurement of naturally generated energy (SPONGE) for PHEVs,” _International Journal of Control_ , vol. accepted for publication, 2016.
  * [8] R. Van Haaren, “Assessment of electric cars’ range requirements and usage patterns based on driving behavior recorded in the national household travel survey of 2009,” in _A Study conducted as part of the Solar Journey USA project_ , 2011.
  * [9] http://insideevs.com/byd-electric-bus-test-results-in-canada/.
  * [10] P. Boulter, T. Barlow, and I. McCrae, “Emission factors 2009: Report 3-exhaust emission factors for road vehicles in the United Kingdom,” _TRL Report PPR356. TRL Limited, Wokingham_ , 2009.
  * [11] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” _Foundations and Trends® in Machine Learning_ , vol. 3, no. 1, pp. 1–122, 2011.
  * [12] F. Wirth, S. Stuedli, J. Y. Yu, M. Corless, and R. Shorten, “Nonhomogeneous place-dependent markov chains, unsynchronised AIMD, and network utility maximization,” _arXiv preprint arXiv:1404.5064_ , 2014.
  * [13] R. Rejaie, M. Handley, and D. Estrin, “Rap: An end-to-end rate-based congestion control mechanism for realtime streams in the internet,” in _INFOCOM’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE_ , vol. 3. IEEE, 1999, pp. 1337–1345.
  * [14] M. Corless and R. Shorten, “An ergodic AIMD algorithm with application to high-speed networks,” _International Journal of Control_ , vol. 85, no. 6, pp. 746–764, 2012.
  * [15] Ł. Budzisz, R. Stanojević, R. Shorten, and F. Baker, “A strategy for fair coexistence of loss and delay-based congestion control algorithms,” _Communications Letters, IEEE_ , vol. 13, no. 7, pp. 555–557, 2009.
  * [16] R. Shorten, D. J. Leith, J. Foy, and R. Kilduff, “Analysis and design of AIMD congestion control algorithms in communication networks,” _Automatica_ , vol. 41, no. 4, pp. 725–730, 2005.
  * [17] M. Liu and S. McLoone, “Investigation of AIMD based charging strategies for EVs connected to a low-voltage distribution network,” in _Intelligent Computing for Sustainable Energy and Environment_. Springer, 2013, pp. 433–441.
  * [18] E. Crisostomi, M. Liu, M. Raugi, and R. Shorten, “Plug-and-play distributed algorithms for optimized power generation in a microgrid,” _Smart Grid, IEEE Transactions on_ , vol. 5, no. 4, pp. 2145–2154, 2014.
  * [19] S. Stüdli, E. Crisostomi, R. Middleton, and R. Shorten, “Optimal real-time distributed V2G and G2V management of electric vehicles,” _International Journal of Control_ , vol. 87, no. 6, pp. 1153–1162, 2014\.
  * [20] D. Krajzewicz, M. Bonert, and P. Wagner, “The open source traffic simulation package sumo,” _RoboCup 2006 Infrastructure Simulation Competition_ , vol. 1, pp. 1–5, 2006.
  * [21] M. Haklay and P. Weber, “Openstreetmap: User-generated street maps,” _Pervasive Computing, IEEE_ , vol. 7, no. 4, pp. 12–18, 2008.
  * [22] A. Wegener, M. Piórkowski, M. Raya, H. Hellbrück, S. Fischer, and J.-P. Hubaux, “TraCI: an interface for coupling road traffic and network simulators,” in _11th Communications and Networking Simulation Symposium, Ottawa, Canada_ , 2008, pp. 155–163.
  * [23] http://www.intelligence.tuc.gr/renes/.
  * [24] B.-M. Hodge, D. Lew, M. Milligan, H. Holttinen, S. Sillanpää, E. Gómez Lázaro, R. Scharff, L. Söder, X. Larsén, G. Giebel, D. Flynn, and J. Dobschinski, “Wind Power Forecasting Error Distributions: An International Comparison,” in _11th Annual International Workshop on Large-Scale Integration of Wind Power into Power Systems as well as on Transmission Networks for Offshore Wind Power Plants, Lisbon, Portugal_ , 2012\.
  * [25] J. Zhang, B.-M. Hodge, A. Florita, S. Lu, H. Hamannk, and V. Banunarayanan, “Metrics for Evaluating the Accuracy of Solar Power Forecasting,” in _3rd International Workshop on Integration of Solar Power into Power Systems, London, UK_ , 2013.
  * [26] S. Stüdli, W. Griggs, E. Crisostomi, and R. Shorten, “On optimality criteria for reverse charging of electric vehicles,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 15, no. 1, pp. 451–456, 2014.

|  Joe Naoum-Sawaya is currently an Assistant Professor in Management Science
at Ivey Business School. He received a B.E. in Computer Engineering from the
American University of Beirut and a M.A.Sc. and Ph.D. in Operations Research
from the University of Waterloo. His research interests include large scale
optimization methods for practical problems arising in the industry.
---|---
|  Emanuele Crisostomi received the B.S. degree in computer science
engineering, the M.S. degree in automatic control, and the Ph.D. degree in
automatics, robotics, and bioengineering, from the University of Pisa, Italy,
in 2002, 2005, and 2009, respectively. He is currently an Assistant Professor
of electrical engineering with the Department of Energy, Systems, Territory
and Constructions Engineering, University of Pisa. His research interests
include control and optimization of large-scale systems, with applications to
smart grids and green mobility networks.
---|---
|  Mingming Liu received his double B.E. degrees in Electronic Engineering
with first class honours from National University of Ireland Maynooth and
China Changzhou University in 2011. He has obtained his Ph.D. degree from the
Hamilton Institute, Maynooth University. He is currently a post-doctoral
researcher in University College Dublin, working with Prof. R. Shorten. His
current research interests are nonlinear system dynamics, distributed control
techniques, modelling and optimisation in the context of smart grid and smart
transportation systems.
---|---
|  Yingqi Gu received her B.E. degree in Electronic Engineering (first class
honours) from Maynooth University in 2013. She obtained her M.Sc degree in
Signal Processing and Communications at School of Engineering, University of
Edinburgh in 2014. From February 2015, she commenced her Ph.D. degree in the
University College Dublin with Prof. Robert Shorten. Her current research
interests are modelling, simulation and optimisation of intelligent
transportation systems.
---|---
|  Robert Shorten Professor Shorten is currently Professor of Control
Engineering and Decision Science at University College Dublin, and holds a
position at IBM Research. Prof. Shorten’s research spans a number of areas. He
has been active in computer networking, automotive research, collaborative
mobility (including smart transportation and electric vehicles), as well as
basic control theory and linear algebra. His main field of theoretical
research has been the study of hybrid dynamical systems.
---|---