This article has been accepted for inclusion in a future issue of this journal.

Content is final as presented, with the exception of pagination.

IEEE SYSTEMS JOURNAL 1

A Review of Charge Scheduling of

Electric Vehicles in Smart Grid
Joy Chandra Mukherjee and Arobinda Gupta

Abstract—Electric vehicles (EVs) are being introduced by dif- Two types of interactions are possible between an EV and
ferent manufacturers as an environment-friendly alternative to the power grid, namely, grid to vehicle (G2V) and vehicle to
vehicles with internal combustion engines, with several benefits. grid (V2G). In G2V, an EV’s battery can be charged from the
The number of EVs is expected to grow rapidly in the coming grid using stored electricity originating from external power
years. However, uncoordinated charging of these vehicles can put a
severe stress on the power grid. The problem of charge scheduling sources, i.e., the power flow is always unidirectional. In V2G,
of EVs is an important and challenging problem and has seen the power flow is bidirectional, i.e., from the grid to an EV
significant research activity in the last few years. This review while charging and from an EV to the grid while discharging.
covers the recent works done in the area of scheduling algorithms V2G-enabled EVs earn incentives while discharging power to
for charging EVs in smart grid. The works are first classified into the grid and make payments while charging batteries from the
two broad classes of unidirectional versus bidirectional charging, grid. Thus, V2G-enabled EVs can facilitate the supply/demand
and then, each class is further classified based on whether the
balance by discharging during peak hours (peak shaving) and
scheduling is centralized or distributed and whether any mobility
aspects are considered or not. It then reviews the key results in charging during off-peak hours (valley filling).
this field following the classification proposed. Some interesting The impact of EVs on the power grid has been studied in dif-
research challenges that can be addressed are also identified. ferent works [2], [6]. One solution to mitigate the impact of EVs
on the grid is to schedule their charging/discharging profiles.
Index Terms—Charging, electric vehicle (EV), grid to vehicle
(G2V), scheduling, vehicle to grid (V2G). This can be done by aggregating different sets of EVs for charg-
ing or discharging with different start times and durations such
that grid constraints are maintained. However, the aggregation
I. I NTRODUCTION of EVs differs from the aggregation of more traditional power
resources [7]. In particular, the temporal availability of EVs
E LECTRIC VEHICLES (EVs) have received considerable
attention in recent times as an eco-friendly and cost-
effective alternative over conventional vehicles driven by in-
along with their location information is an important parameter
to consider while aggregating EVs for possible grid congestion
ternal combustion engines (ICEs). They have lower operating planning and management. Thus, determining the appropriate
costs with respect to ICE vehicles and can be also charged with charge and discharge times of EVs that do not violate grid
locally produced renewable energy sources (RESs) [1]. How- constraints while maintaining acceptable degrees of user satis-
ever, there exists several challenges to large-scale adoption of faction is a challenging problem. The area has seen significant
EVs. Although their operating costs are less, EVs are still more research activity in the last few years, and in this paper, we
expensive to buy than ICE vehicles. In addition, access to charg- aim to review the work done in charge scheduling of EVs from
ing stations is limited, and large capital investment is required its origin until early 2013.
for developing a public charging infrastructure [1]. In addition, The rest of this paper is organized as follows. Section II de-
EVs consume comparatively high power from the grid during scribes the basic background in smart grids and EVs needed for
charging. Therefore, uncoordinated charging of a large number this survey. Section III provides a classification of the existing
of EVs can have an adverse impact on the grid operation (power works in charge scheduling of EVs. Sections IV and V briefly
outages, unacceptable voltage fluctuations) [2]. To handle the review the charge scheduling algorithms with unidirectional
peak demand of EVs, one possible solution can be to ramp up and bidirectional power flow models, respectively. Section VI
the power generation; however, this will lead to significant in- discusses handling uncertainty in some of the parameters.
frastructure cost. As an alternative cost-effective solution, smart Section VII identifies some open issues and research chal-
grid allows EVs to coordinate their charging operations, which lenges. Finally, Section VIII concludes this paper.
can improve frequency regulation [3], smooth out intermittent
power generation from RESs, and make the electric power II. BACKGROUND
usage efficient [4], [5].
An electric power system is primarily composed of three
operational sectors: generation, transmission, and distribution.
The generation phase is connected to the transmission phase,
Manuscript received July 15, 2013; revised November 6, 2013, March 13,
2014, and June 10, 2014; accepted August 28, 2014.
which carries electricity to the distribution phase through differ-
The authors are with the Department of Computer Science and Engineering, ent substations and transmission lines. The distribution phase
Indian Institute of Technology Kharagpur, Kharagpur-721 302, India (e-mail: dispatches the electricity to the end users through distribution
joy.cs@cse.iitkgp.ernet.in; agupta@cse.iitkgp.ernet.in). feeders and transformers. An independent system operator
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org. (ISO) coordinates, controls, and monitors the operation of
Digital Object Identifier 10.1109/JSYST.2014.2356559 the transmission phase. However, the introduction of various

1932-8184 © 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

2 IEEE SYSTEMS JOURNAL

distributed generators over the years has made the problem of are typical ratings, and the actual energy consumption of an EV
controlling the power flow more complex. A smart grid inte- changes with several factors, such as vehicle model, external
grates a communication infrastructure for fast and secure data elements, driving behaviors, vehicle maintenance, and lithium-
transmission, using smart sensors and actuators at lower layers ion battery age.
for data collection and control and intelligent decision making EVs are plugged into a charging station to charge or discharge
at higher layers using information technologies for various their batteries through charger outlets. Note that an EV can act
smart energy applications. Three different conceptual models as a load to the distribution grid (charging), a mobile energy
of smart grid are used in the literature: Internet model, active storage (ES) device, and a supplier of electricity to the grid
networks, and microgrids [8]. The Internet model will use in- (discharging). Unlike other conventional generating units, vehi-
formation and communication technology to provide real-time cle batteries do not have any startup cost or shutdown cost [3]
interconnection between nodes, enabling nodes to effectively while discharging power to the grid. Due to lower load, night
respond to and adapt in real time to fluctuations in parameters hours are generally preferred for charging EV batteries (valley
such as supply/demand and price. The active network model filling). The driving profile of an EV is such that it typically
ensures connectivity between the supply and demand points. It travels for 2–3 h a day on an average and is parked for the
also enables users to update their energy consumption profiles rest of the time [18]. The possibility of higher plugged-in time
based on real-time power market information and demand-side with respect to the actual charging time gives flexi-timing that
management, allowing for better balance between supply and can facilitate providing ancillary services such as frequency
demand [8], [9]. The microgrid model considers a smart grid regulation, while charging the vehicle by a certain time (smart
as a system of integrated intelligent microgrids. A microgrid charging [18]).
is a centralized electrical system that locally generates and EVs can be charged overnight at home using AC Level 1
distributes power to local customers, possibly at privileged (typically 120 V) or AC Level 2 (typically 240 V) charging
tariffs. Microgrids are connected to the smart grid, allowing equipment [19]. Typically, AC Level 1 and AC Level 2 charging
for potential power exchange between the grids for better grid can add around 2–5 and 10–20 mi of range per hour of
reliability [8], [10]. charging time, respectively [19]. EV charging schedule can be
Some of the notable benefits of smart grids include re- coordinated with the operation of other electrical home appli-
liable and optimized power generation, automated and ef- ances using a home area network. Although the majority of EVs
ficient operation and maintenance, increased capacity of are expected to be charged at home, conveniently located public
existing power networks, improved disruption resiliency, pre- charging stations can complement this to increase the daily use-
dictive maintenance, self-healing feedback mechanism for im- ful range of EVs [20]. Public charging stations use AC Level 2
balance reduction, and deployment of renewable resources. or DC fast charging (also sometimes called DC Level 2) [19].
Demand response programs are expected to play a major role DC fast charging typically uses 480-V ac input and enables
in realizing many of the benefits of smart grids. Such programs rapid charging, adding around 60–80 mi of range to an EV in
allow the customer to obtain real-time information about the 20–30 min [19]. However, the charging time and the mileage
electrical energy availability and price, which enables them to added vary depending on the vehicle model, the battery type,
potentially shift some energy usage to off-peak hours to obtain and the power drawn.
better economic benefits. At the same time, this protects the grid Wireless power transfer techniques have been commercially
from overloading at peak hours and allows the ISO to better introduced as a convenient alternative to charging conductively.
manage the power system [9], [10]. An example of such a technology is an inductive power transfer
(IPT) system [21], [22], which consists of a transmitter coil and
A. EVs in Smart Grid a receiver coil that form a system of magnetically coupled in-
EVs carry lithium-ion (Li-ion) batteries that can be charged ductors. An alternating current in the transmitter coil generates
from a household electrical outlet or from a public charging sta- a magnetic field, which induces a voltage in the receiver coil,
tion. Plug-in EVs (PEVs) that are driven only by the chemical which is used to charge an EV battery. It operates at power level
energy stored in battery packs are known as battery EVs (BEVs) compatible to AC Level 2. No cables are needed, and charging
or all-EVs. In contrast, a plug-in hybrid EV (PHEV) can use can start automatically whenever the EV is parked over the sys-
either battery power or onboard fossil fuel (e.g., gasoline). tem, even for a few minutes. Other techniques for wireless
EVs are rated as miles per gallon equivalent [MPGE; the U.S. power transfer that have been explored include capacitive pow-
Environmental Protection Agency (EPA) estimates that 1 gal of er transfer [23], low-frequency permanent-magnet coupling
gasoline is equal to 33.7 kWh] [11]. The battery capacity of power transfer [24], resonant IPT [25], online power transfer
some typical commercially available BEVs (Nissan Leaf [12], system [26], and resonant antenna power transfer [27]. An
Ford Focus Electric [13], Mitsubishi i-MiEV [14], etc.) varies alternative to recharging, called battery swapping, is to quickly
between 16 and 24 kWh, with the EPA-estimated mileage rating exchange drained or nearly drained batteries with fully charged
varying between 110 and 126 MPGE. A typical EV using only batteries at designated exchange stations [28].
its battery power requires around 1 kWh for every 3–4 mi of Public charging stations currently installed worldwide use
driving, potentially making them one of the biggest energy con- both AC Level 2 and DC fast charging, commonly called slow
sumers in future. PHEVs are rated as MPGE/MPG [15]–[17]. and fast charging, respectively. Currently, USA has around
The EPA-estimated mileage rating for a typical PHEV (Toyota 21 400 outlets [29] available in around 7700 charging stations
Prius Plug-in [15], Ford Fusion Energi [16], Chevrolet Volt [30]. At the end of 2012, the approximate number of charging
[17], etc.) varies between 95 and 100 MPGE/35 and 50 MPG, outlets was 20 000 in Europe, 5000 in Japan, and 8000 in China
which is equivalent to around 2.8–3 mi/kWh. However, these [31]. Most of these are slow chargers using AC Level 2. Only
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

MUKHERJEE AND GUPTA: REVIEW OF CHARGE SCHEDULING OF ELECTRIC VEHICLES IN SMART GRID 3

that optimizes some grid, user, or aggregator-side parame-

ters (or a mix of them) subject to different grid, user, and
aggregator-side constraints. The parameters, constraints, and
objective functions considered span a very wide range, giving
rise to different forms of optimization problems, and no single
mathematical formulation exists for the problem in general.
There have been many works reported in the area of charge
scheduling for EVs in the last few years. While all of them
address the same basic problem, there is a wide variation in the
Fig. 1. System-level view of the charge scheduling process.
environment in which they operate, parameters and constraints
Japan had nearly 1400 fast charging outlets; in contrast, USA handled, and methodology employed for deriving the charge
had only around 300 fast charging outlets [31]. The higher schedule. Here, we attempt to classify the works based on
deployment of slow chargers in USA may possibly be due to different parameters.
more reliance on home charging and the prevalence of PHEVs
[31], which require less charge and can be charged typically in
A. Unidirectional Versus Bidirectional Power Flow
around 2–3 h even with slow chargers. In contrast, Japan is the
largest market for BEVs [31], which require more charging time Unidirectional power flow model assumes that power flows
due to larger battery capacity. Initial studies have also shown only from the grid to EVs (G2V) when the EVs charge. In the
that a large number of fast chargers, which are also more costly, bidirectional power flow model, power flow is possible in both
may not be needed [31]. This can be also seen in the future directions (V2G), but simultaneous charging and discharging of
targets set for charging infrastructure installation by two of the an EV battery is not allowed.
major EV users: 2 million slow chargers and 5000 fast chargers Without any substantial modification to the existing equip-
by 2020 by Japan and around 22 000 total chargers, including ment in EVs or without deploying any additional infrastructure
only around 350 fast chargers, by 2014 by USA [31]. Although in the charging stations, all legacy EVs can participate in the
several companies offer wireless EV charging solutions com- unidirectional power flow model [32], [33]. With the expected
mercially, they are still more costly to install. However, as surge of EV penetration with bidirectional capabilities in near
prices continue to fall, wireless charging may become more future, early experience with EVs with unidirectional capabil-
popular as a public charging option because of its convenience ities is helpful for the markets and aggregators and regulatory
and flexibility. authorities. However, the bidirectional model has the ability to
Majority of the EVs are expected to be connected to the Inter- provide more flexibility in charging/discharging over the unidi-
net through Wi-Fi, cellular network, or ZigBee communication rectional model [34]–[38]. In the bidirectional power flow mod-
network [18]. The Internet-enabled communication enables el, EV owners have the option of earning incentives from the
EVs to be clubbed into different groups of varying sizes by utility while discharging at peak hours to mitigate the negative
aggregators so that each group can be treated as a dispatchable impacts on the grid by restraining themselves from charging.
load to the grid. The actual charging decision of each group Despite its limitations, the unidirectional power flow model
of EVs is either centrally controlled by the aggregator, or EVs with its lower infrastructure cost is a first logical step toward
may collaborate with the aggregator in a decentralized manner implementing more complex bidirectional power flow model.
to decide their charging schedule. When a driver plugs the Most of the works have assumed the unidirectional power flow
vehicle into a charging point at a parking spot, a sign-on ses- model [1], [3], [5], [39]–[57]. The bidirectional power flow
sion is initiated by the aggregator. The vehicle communicates model has been assumed in [34], [35], [37], [38], and [58]–[64].
several charging parameters such as location, maximum battery
capacity, current state of charge (SOC), desired SOC, maximum B. Centralized Versus Decentralized Charging Control
and minimum recharge power drawn, and deadline information
within which the battery must be charged up to the desired In centralized charging control, the optimization of EV
SOC through a secured channel to the aggregator [18]. The charge scheduling is done centrally at the aggregator after col-
aggregator, based on several grid constraints, user constraints, lecting information about power requirement of the EVs. The
and mobility parameters, determines and communicates the EVs can only communicate their electrical parameters such as
charge schedule to the individual EV to avoid grid overload and maximum battery capacity, SOC, and charge rate to the aggre-
balance supply/demand potential of the grid [9]. gator. Based on the aggregated power requirement, each aggre-
Fig. 1 shows a system-level diagram for the charge schedul- gator makes a contract with the ISO. On receiving the contracts
ing process for both unidirectional (only charging) and bidirec- from different aggregators, an energy management system at
tional (both charging and discharging) cases. The aggregator is the ISO decides the appropriate power share for each aggregator
placed in between the ISO and the EVs. within their contracted boundary considering the other loads,
power generation capacity from different generators, and grid
III. C LASSIFICATION OF C HARGE constraints. Then, each aggregator executes an optimization
routine to schedule the EV charging in such a way that the
S CHEDULING A LGORITHMS
EVs anticipated energy requirements are met. In contrast, in
The EV charge scheduling problem takes as input a set of decentralized charging control, each EV is equipped with some
EVs and different grid, user, and aggregator-side parameters computing capability, and the decision to charge or not is taken
and outputs a charging schedule (starting and ending times of by each EV in collaboration with the aggregator. Each EV
charging of each EV in the set). It is an optimization problem communicates their energy requirements to the aggregator and
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

4 IEEE SYSTEMS JOURNAL

uses part of this information collected at the aggregator to E. Providing Ancillary Services
decide on an optimal schedule.
In a V2G scenario, an EV cannot only act as an energy
The centralized charging control method is able to calculate
supplier to the grid, it can also provide certain ancillary services
the optimal schedule as all the information is available to it.
to the grid. Some examples of such services are frequency
However, this benefit comes at the cost of sharing all the
regulation and spinning reserves.
private user state information of the EVs. The implementation
Regulation or frequency control or automatic generation
of centralized charging algorithm for large number of EVs is
control is needed to monitor and control the frequency and
also computationally intractable in general. The advantage of
voltage of the grid by balancing the power generation profile
using decentralized control is its scalability, where penetration
with the potential load [32], [65]. Regulation service is super-
of a large number of EVs is allowed in the scheduling process.
vised by the ISO. The ISO dispatches signals to the generators,
However, lack of complete information at any EV makes the
and the generators respond either by increasing regulation up
charge schedule suboptimal.
or decreasing regulation down their output to give the nec-
Majority of the works on charge scheduling use centralized
essary regulation service. Compared with spinning reserves,
charging [1], [3], [5], [34], [37]–[44], [46]–[48], [50], [51],
regulation service is invoked more frequently, requires prompt
[55], [59], [63]. Decentralized charging has been explored in
response within a minute or so, and is required to continue its
[35], [45], [49], [52]–[54], [56]–[58], [60]–[62], and [64].
operation for shorter duration typically on the order of minutes
at a time [65].
C. Static Versus Mobility-Aware Charging In case of power shortages, spinning reserves are notified
Static charging refers to the charging scenario where the by the ISO to discharge power back to the grid in a short
mobility of the EVs is ignored; the vehicles are treated as while (within 10 min) [65]. Spinning reserves run at low speed
stationary loads with no temporal properties related to the with proper synchronization to the grid and earn incentives
mobility of the EVs. In contrast, mobility-aware charging takes depending on the current market price of electricity and the
into consideration different mobility aspects such as the arrival/ duration for which they are up and ready for delivering power.
departure time of an EV at/from a charging station, trip history Individual EVs can supply ancillary services to the grid by
of EVs, and unplanned departure of EVs. varying their charge/discharge rates around a preferred oper-
Considering mobility aspects makes the problem more real- ating point (POP) during charging/discharging [18], [41]. The
istic by considering the spatiotemporal behavior of an EV. For POP is a power output level for a generator, whereas it is a
example, charging requests can be known a priori based on power draw level for a load. In a G2V scenario, regulation up
expected arrival times at charging stations; similarly, unplanned and down can be performed by the EVs either through decreas-
departures of EVs and their effect on grid load can be studied. ing or increasing the power drawn from the grid, respectively.
However, the increased flexibility requires a more complex Similarly, spinning reserves are supplied by the EVs to the grid
problem formulation. Static charging, on the other hand, keeps by decreasing the power drawn from the grid. In a V2G sce-
the problem formulation simple, and some authors consider it nario, regulation and spinning reserve can be also provided by
to investigate the impact of other parameters on the grid. controlling the battery discharge rate. The aggregator controls
Both static and mobility-aware charging have received the charge/discharge rate of each EV to provide the regulation
considerable attention from researchers in the recent years. service and acts as spinning reserve.
Static charging has been assumed in [1], [3], [37], [39], [40], Some of the existing works on charge scheduling also con-
[43], [44], [47], [49], [52], [53], [57]–[62]. In contrast, the sider EVs providing such ancillary services to the grid [1], [3],
works in [5], [34], [35], [38], [41], [42], [45] [46], [48], [50], [34], [37], [41], [42], [58], [62], [63].
[51], [54]–[56], [63], and [64] consider at least some mobility
aspects of the EVs. F. Objectives of Charge Schedule Optimization
The charge scheduling problem is an optimization prob-
D. Integration of RESs
lem, and different objective functions have been used in the
The greenhouse gas emissions from transportation and en- problem formulations depending on the goals of scheduling.
ergy sectors are one of the biggest threats to the environment. Some works have tried to optimize grid-side benefits such as
In the supply side, RESs such as wind power and solar power minimizing financial cost of power supply [54], minimizing
are potential solutions for emission reduction from the energy grid operation cost, including cost of wind and hydro power
sector. However, climatic variations make the power genera- and availability cost for providing spinning reserves [38], min-
tion from RESs highly stochastic. In the demand side, next- imizing distribution system load variance [56], minimizing
generation EVs from the transportation sector can reduce CO2 loss in distribution system [40], and maximizing the profits of
emissions [37]. EVs with V2G capability can be integrated with thermal and wind plants while minimizing energy trading risks
RESs to reduce emissions. Thus, charge scheduling algorithms [42]. Some other works have focused on optimizing EV-side
that can handle the integration of such RESs are important. benefits such as minimizing charging cost [35], [37], [39], [45],
However, considering such RESs makes the problem more minimizing both CO2 emission and charging cost [37], [39],
complex because of the uncertainty surrounding the supply of maximizing the average SOC of EVs [48], and maximizing user
power from such sources. convenience [49]. However, another class of works has focused
Only a few works in the literature have considered the on optimizing aggregator-side benefits such as maximizing
integration of RESs explicitly in their problem formulations [1], aggregator profits [63] and reducing the imbalances arising out
[37], [38], [42], [48], [54], [55]. of the energy purchased by the aggregator from the day-ahead
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

MUKHERJEE AND GUPTA: REVIEW OF CHARGE SCHEDULING OF ELECTRIC VEHICLES IN SMART GRID 5

TABLE I the classification hierarchy, we mention these properties while

O PTIMIZATION T ECHNIQUES U SED
discussing each work wherever applicable. Fig. 2 shows the
classification hierarchy we use in the rest of this paper.

IV. C HARGE S CHEDULING W ITH U NIDIRECTIONAL

P OWER F LOW M ODEL
Here, we review the works that have assumed the unidirec-
tional power flow model. The algorithms are subdivided into
four subclasses: 1) static centralized scheduling; 2) mobility-
aware centralized scheduling; 3) static decentralized schedul-
ing; and 4) mobility-aware decentralized scheduling. In each
subclass, the works are considered in chronological order from
the least to the most recent.

A. Static Centralized Scheduling

This subclass of scheduling uses centralized control and does
market and the actual energy consumed [60]. Several works not consider any mobility parameters of EVs.
have also tried to jointly optimize both grid-side and EV-side Erol-Kantarci and Mouftah [39] proposed a charging al-
benefits [46], [51], [51], [64]. gorithm based on prediction of the energy prices during the
charging period where the charging stations are informed about
real-time pricing information through wireless communication.
G. Methods for Charge Schedule Optimization
The algorithm finds an appropriate time of charging (TOC) with
The exact formulation of the charge scheduling optimization low cost. During the charging process, the k-nearest neighbor
problem depends on the constraints handled and the objective classification algorithm is applied to predict the price signals
functions to be optimized. Different works have formulated of the grid. If the predicted price is greater than a threshold,
the problem differently and have explored a wide variety of charging is delayed until it determines a suitable TOC for the
optimization techniques to solve them. Table I summarizes vehicle. It is shown that the cost of electricity consumption of
the optimization tools used in the works reported in this vehicles is considerably reduced by this.
survey. Han et al. [3] developed an optimal aggregator to provide
Table II summarizes the classifications discussed so far. The frequency regulation services toward the grid by determining
rows indicate references to the works we have covered in this the charge schedule for EVs. Since a vehicle is an energy
survey, and the columns indicate the class each work belongs to. consumer and at the same time a regulation provider, the market
A  indicates that it falls in the class specified in the column prices and incentives for both of them are taken into account.
heading (e.g., bidirectional or decentralized); a × indicates that The aggregator decides the charging rate, charging sequence,
it does not. Note that, for all classifications proposed, there are and charging duration for each vehicle while maximizing the
only two classes possible; thus, a × automatically implies that revenue. A dynamic-programming-based approach is proposed
the work falls in the other class (e.g., unidirectional or central- to find an optimal charge schedule for each vehicle.
ized). It is seen that while most of the works fall under cen- Sortomme and El-Sharkawi [1] presented another charge
tralized static charging with unidirectional power flow model, scheduling algorithm while providing frequency regulation to
several works exist otherwise also. Again, most of the works the grid by varying the charge rate of each EV around a POP
have not considered integrating renewable resources or provid- [18], which is scheduled with the system. The POP is the aver-
ing ancillary services. age power drawn around which the EV charge rate is de-
In the next two sections, we briefly review the charge termined. The aggregator controls the charging of each EV
scheduling algorithms listed in Table II. However, since each according to its capacity by decreasing or increasing the load
work can fall in different classes based on the classification to achieve regulation up or regulation down. In this paper,
property chosen, a hierarchy of the important classes is first two POP selection algorithms, namely, heuristic smart charging
created. A primary characteristic of any algorithm is whether it POP selection algorithm and optimal POP selection algorithm,
supports unidirectional or bidirectional power flow, and hence, are proposed. Under the first category, three suboptimal smart
all algorithms are first classified based on this property. How- charging POP selection algorithms are described: load based,
ever, since a large number of works are present for each of these price based, and maximum regulation participation based. Af-
two classes, we further classify the works reported under these ter determining the initial POP using one of the three smart
two classes based on the type of control used (centralized or charging algorithms, the final POP and regulation up and down
decentralized) and whether mobility aspects are considered or capacity of each EV for the aggregator are defined. In addition,
not. Classifications based on integrating renewable resources three optimal algorithms analogous to the three smart charging
or providing ancillary services are not considered separately techniques are developed that minimize the charging cost while
as only a small number of works address these issues. Op- maximizing the profits of the aggregator through charging and
timization methods and objective functions used are also not providing regulation.
considered separately in the hierarchy as they do not provide a The impact of PHEVs on distribution grid performance such
binary classification. However, although we exclude them from as overloading, efficiency, power quality, and voltage regulation
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

6 IEEE SYSTEMS JOURNAL

TABLE II
C LASSIFICATION OF C HARGING O PTIMIZATION

Vasirani and Ossowski [43] proposed a power allocation

policy for PEVs based on the lottery scheduling algorithm for
balancing fairness and selfishness. The charging infrastructure
is a local distribution grid having a substation with several
charging spots where PEVs can be plugged in for charging their
batteries. The substation runs a randomized resource allocation
mechanism that allocates the available power to the vehicles
with higher preference given to the vehicles that are paying
higher price for the electricity. The algorithm also ensures fair-
ness by guaranteeing a nonzero percentage of the total allocated
power to all the PEVs.
Richardson et al. [47] have proposed a local and a cen-
tralized charging strategy for EVs in low-voltage distribution
Fig. 2. Classification scheme followed for EV charge scheduling algorithms. grid and discussed the pros and cons of each strategy. The
model assumes that each house has an EV charger unit with
is studied by Sortomme et al. [40], and coordinated charging automated metering infrastructure facility enabling customers
of PHEVs is proposed as a possible solution. The objective to know about the time-of-day electricity prices. A local control
function is formulated based on load factor and variance, which technique is described that an EV uses to maximize its own
maximizes profits of the aggregator, minimizes system losses, charging rate based on local network conditions and its battery
and improves voltage regulation. Three optimal charge schedul- SOC while maintaining local grid constraints within acceptable
ing algorithms are proposed based on the relationship among limits. For the centralized control method, each connection
load factor, load variance, and feeder losses to solve the coordi- voltage, the thermal load of each household, the low-voltage
nated PHEV charging problem. transformer load, and the battery SOCs of EVs are sent to
Wu et al. [44] proposed centralized charge scheduling and a central controller, which respects several grid constraints to
load dispatch algorithms that aggregators can use to minimize determine dispatch signals at each time step for the individual
their energy cost. The algorithms use the charging demand pro- EV charger units accordingly. The results indicate that the
file forecast for the coming day, determine the charging sched- local charging allows a larger penetration of EV with minimal
ule for each PEV, and dispatch the energy purchased from the communication infrastructure, whereas the centralized method
market to the individual PEVs. The impact of a combined PEV gives a better scheduling plan with exact knowledge of network
load over the distribution grid is also studied. parameters.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

MUKHERJEE AND GUPTA: REVIEW OF CHARGE SCHEDULING OF ELECTRIC VEHICLES IN SMART GRID 7

B. Mobility-Aware Centralized Scheduling i.e., EVs are reasonably charged up to a certain limit before
their scheduled departure.
This subclass of scheduling also uses centralized control but
Sortomme and El-Sharkawi [41] explored the problem of
takes some mobility aspects of the EVs into consideration while
maximizing the profit of the aggregator that bids for ancillary
forming a charge schedule.
services (regulation and spinning reserves), while facilitating
Deilami et al. [46] proposed a real-time smart load man-
the charging of vehicle batteries. The proposed spinning reserve
agement algorithm using maximum sensitivities selection [66]
algorithm and the regulation algorithm modulate the charging
optimization that schedules the charging of PEVs in residential
of the EVs around the POP. An optimal bidding strategy is
areas to minimize grid overload and increase grid reliability.
formulated, which selects the POP and the capacities of each
Mobility issues such as random arrival and departure of PEVs
are taken into account in formulating the problem. Time- ancillary service to be sold. Mobility aspects considered include
varying energy prices over the day and preferred charging time EV driving statistics for the whole day, which is used to derive
zone priorities specified by PEV owners are also taken into the expected availability times for EVs and travel distances,
consideration. The charging of PEVs starts as soon as possible which, in turn, are used to select the daily charging profile.
within the priority-charging time zones with the goal of mini- The formulation also accounts for the probability of unexpected
mizing energy purchasing cost plus the cost due to grid energy departure during a contract period with associated penalty and
losses while respecting grid constraints such as system losses, the compensation given to the other EVs for maintaining the
voltage fluctuations, generation constraints, and energy demand schedule. The decision variables that the aggregator can set and
limits. bid into the market are the EVs’ POPs, capacity to increase/
Al-Awami and Sortomme [42] investigated how a load- decrease the charge rate for regulation down/up, and the capac-
serving entity (LSE) that controls thermal and wind plants ity to decrease charge rate for spinning reserves.
can handle a load with a significant number of EVs using Sundstrom and Binding [5] proposed a framework involving
energy trading. Mobility aspects considered include different charging service providers (CSPs), retailers, and distributed
trip times of EVs, EV’s presence to perform V2G, and reduction system operators (DSOs) that influence the charge schedules. A
in SOC as a result of driving. The problem of energy trading centralized algorithm for charge scheduling of EVs is proposed
is formulated as a mixed-integer stochastic linear program that that considers grid constraints in terms of voltage and power
maximizes the LSE’s profits while minimizing trading risks due and meets user-specified constraints. The CSP solves the charg-
to uncertain energy prices, intermittent energy availability, and ing schedule optimization problem based on forecasted EV en-
variable energy demand of EVs. The suppliers and consumers ergy schedule, vehicle locations, and reference load curve from
submit day-ahead energy supply and demand bidding offers retailer; then, the DSO validates the feasibility of loads and gen-
for each hour in the energy market. The market operator, on eration based on the output available from the earlier optimiza-
combining these bidding offers, determines the market clearing tion and forecasted data for inflexible conventional load and
prices (MCPs) for each hour and allocates the estimated energy generation. If it is feasible, the CSP is notified that the proposed
to each participant. For each hour, each energy supplier gets schedules can be implemented. Otherwise, the power imbal-
incentive by an amount equal to the product of MCP and the en- ances are calculated for the flexible loads by the DSO and used
ergy volume. In addition, an energy supplier may be penalized, as input to the next iteration of the optimization problem along
resulting from the imbalance between the cleared energy vol- with the earlier inputs until the power imbalances are resolved.
ume and the actual energy produced. When the LSE generates Xu and Pan [55] formulated the scheduling problem as
below a threshold, it can either ramp up the production from the maximizing the time-averaged expected social welfare, which
thermal units, ramp down the power consumption by the vehi- is a function of the total customer utility, the electricity cost as-
cles, pay the imbalance penalty, or any combination of the three sociated with PHEV charging, and the penalty for not meeting
strategies. The opposite holds true when the LSE overgenerates. PHEVs’ charging requests. This problem essentially boils down
The decision variables considered are optimal bid of a thermal to a stochastic deadline scheduling problem with preemption
unit and a wind plant, thermal power output, scheduled car where penalty for unsatisfied charging request is taken into
charging level, scheduled capacity increase or decrease from account. The deadline for a vehicle is essentially the departure
the POP, and actual power draw of the EVs. time from the charging spot. The decision-making problem is
Su and Chow [48] have proposed an optimal charging algo- formulated as an infinite-horizon dynamic programming prob-
rithm for a large number of PHEVs (in thousands) at a mu- lem that considers the stochastic arrival process of the PHEVs
nicipal parking spot. Typical parking spot environments (e.g., that evolves like a Markov chain, the uncertainty in renewable
arrival/plug-in time, initial SOC, expected charging time, and generation, and the inexact forecast of grid loads.
user preference) are simulated based on statistical analysis of Lee et al. [50] integrated vehicular networks with smart grid
available transportation data. Mobility of the vehicles has been and designed a charge scheduler for EVs based on heuristic-
taken into account by considering both different arrival times based approaches and genetic algorithms, which minimizes the
and unexpected departure of vehicles. Specifically, the authors load at a charging station. Each request consists of vehicle
have investigated the use of the estimation of distribution type, estimated arrival time, desired service completion time
algorithm [67] for power allocation to PHEVs in real time. (deadline), and current battery charge. On receiving the request,
The objective of the algorithm is to maximize the average SOC the power consumption profile of the vehicle is retrieved from
for all vehicles at the next time step, taking into account the the repository of vehicular information. Then, the charging
maximum battery capacity, remaining battery capacity, energy station verifies whether it can satisfy the new request along with
price, charging time, and current SOC. The proposed algorithm the other requests already submitted to the scheduler. The result
ensures some fairness in the SOC distribution at each time step, is communicated back to the vehicle. On receiving the result,
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

8 IEEE SYSTEMS JOURNAL

the driver may accept the schedule, initiate a renegotiation algorithm is developed for that. The authors proved that this
session, or choose another charging station. problem is convex with respect to the total electricity demand,
Kim et al. [51] developed a constraint-based charge sched- and the solution to the scheduling problem fills the demand
uler in a similar line like Lee et al. [50], where they adopted valley optimally.
classic backtracking algorithm with pruning to speed up the
performance of the scheduler at a parking place. D. Mobility-Aware Decentralized Scheduling

C. Static Decentralized Scheduling This subclass of scheduling also uses decentralized control
but takes some mobility aspects of EVs into consideration.
This subclass of scheduling uses decentralized control and Li et al. [56] proposed a decentralized PEV charging algo-
does not consider any mobility parameters of EVs. rithm to minimize the load variance of the distribution grid in
Ma et al. [52] proposed a decentralized charge scheduling order to flatten the total load profile. With no future knowledge
algorithm for a large number of PEVs using the Nash cer- of the system behavior, the PEV charging processes are con-
tainty equivalence methodology [68]. Initially, the grid operator trolled by the algorithm based only on the current power system
broadcasts the expected non-PEV base demand among the PEV conditions. Some of the parameters considered in their problem
agents, and each PEV agent proposes a charging plan based on formulation include charging power and charging efficiency of
this initial forecast to minimize its charging cost. In the second PEVs, charging cost, number of PEVs, energy queue length of
step, the grid operator receives all the charging plans from PEVs each PEV at each time slot, and total net base load. To address
proposed in the earlier iteration and updates the combined PEV mobility, an indicator function is used that tells whether a PEV
demand corresponding to the proposed charging strategies. This is plugged into the charge outlet or it is moving. The decision
updated aggregate PEV demand is rebroadcasted among all the output is a binary one for each of the vehicle, either it will
PEVs. In the third step, each of the PEVs proposes a charging charge at its maximum rate or not charge at all in a time slot.
plan with respect to a common aggregate PEV demand broad- Cao et al. [45] proposed a decentralized EV charging algo-
cast by the grid operator to reduce its charging cost. Steps 2 rithm in response to time-of-use (TOU) price in a regulated
and 3 are repeated until the optimal plans proposed by the PEVs market that remains constant for a long time. On plugging an
converge. EV charger into the grid, the user can set the expected charging
Gan et al. [57] studied a decentralized charge scheduling completion time, SOC, and the maximum charging power.
algorithm for EVs to satisfy the electricity demand valley The charger with embedded TOU price module formulates an
overnight. The objective is to minimize the charge rate of the optimized charging scheme to minimize the charging cost. By
EVs within the targeted deadline set by individual EVs. This using the relation between the acceptable charging power of
work differs from Ma et al. [52] in the following way. In each EV battery and the SOC, a heuristic algorithm is presented
iteration, the choice of the EVs’ charge profile is governed by to reduce the charging cost. The charging cost and the energy
the price signal broadcast from the grid operator, and the grid demand in different times are considered for studying single-
operator updates the price profile accordingly for a predefined and multi-EV cases. To address mobility, the diversity in arrival
number of iterations. time of EVs is considered in the multi-EV case.
The work of Wen et al. [49] uses a charging selection concept Hutterer et al. [54] proposed a multiagent policy optimization
for PEVs to maximize user convenience levels while satisfying where each EV (agent) acts in response to dynamic conditions
demand constraints. In this paper, the charging time, SOC, and in its environment according to a given strategy. Evolutionary
allowable price characterize the user convenience. The convex computation has been used for optimizing EVs’ charging be-
relaxation optimization [69] tool is used to calculate close- havior such that EVs’ energy demand is satisfied and secure
to-optimal solutions for the problem. The simulation results power grid operation is guaranteed using renewable power. The
are compared against the results of the uncoordinated PEV driving profiles of EVs (locations, time of arrival, and stay time
charging, and it has been observed that the user convenience at each location) and uncertainties in intermittent supply are
levels are slightly reduced, but the negative impact of charging considered. Initially, distribution grid inputs, traffic patterns,
a large number of PEVs is significantly mitigated. A decen- and probabilistic supply models are aggregated for evaluating
tralized charging selection algorithm is also developed where a candidate solution. Using this solution, the resulting charging
the EVs exchange their power demand without disclosing their rate is computed for each EV agent over all time steps. Con-
private information with the aggregator several times and finally sidering all constraints and the charging rates computed in the
come to a decision whether to charge or not. For a real- earlier iteration, a fitness value is computed that reflects the
time implementation of the proposed approach, a low-speed amount of constraint violation. If the fitness value is higher
communication framework is also presented in this paper. than the threshold, the optimization algorithm continues until
Chen et al. [53] studied a time-dependent optimal power flow a certain stopping criterion is reached. The results show that the
[70] charging problem that optimizes the operation of the power policy-based strategy schedules nearly the amount of energy to
grid and the charging activity of EVs. Two types of load are each EV agent that it needs.
considered: price-inelastic load (load must be provided with the
requested power) and price-elastic load (the availability of the V. C HARGE S CHEDULING W ITH B IDIRECTIONAL
requested power depends on the current cost of energy and time
P OWER F LOW M ODEL
limit within which energy must be provided). The objective
is to reduce the charging cost and the total power generation Here, we review the works that have assumed the bidirec-
cost. They also consider the uncertainty arising out of the tional power flow model. As before, the algorithms are sub-
future price-inelastic load, and a near-optimal distributed online divided into four subclasses: 1) static centralized scheduling;
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

MUKHERJEE AND GUPTA: REVIEW OF CHARGE SCHEDULING OF ELECTRIC VEHICLES IN SMART GRID 9

2) mobility-aware centralized scheduling; 3) static decentral- power constraints, and power system outages are considered as
ized scheduling; and 4) mobility-aware decentralized schedul- variables. The solution finds out the hourly unit commitment,
ing. In each subclass, the works are considered in chronological calculates the dispatch from different generators, and decides
order from the least to the most recent. the PEVs’ charge/discharge schedules.
Jin et al. [63] introduced ES from an electricity market
A. Static Centralized Scheduling perspective where the aggregator of EVs participates in energy
trading in the day-ahead and real-time markets. For real-time
This subclass of scheduling uses centralized control and does charge scheduling, a communication framework for exchanging
not consider any mobility parameters of EVs. messages among the aggregator, the power grid, and EVs
Shrestha and Chew [59] formulated an optimization problem is also proposed. The problem is formulated using a mixed-
for EV charging to reduce the charging cost of EVs for a given integer linear programming (MILP)-based technique. However,
EV charging characteristic. The problem formulation considers solving an MILP may take exponentially long time. There-
possible charging period, remaining battery capacity, and sys- fore, a polynomial-time heuristic scheduling algorithm is pro-
tem load at each charging period. The decision variables are the posed based on linear programming rounding. The aggregator
percentage of vehicles that are charged in each charging period receives charging requests (i.e., starting time, finishing time,
and the total cost of charging during that period. Quadratic pro- initial SOC, and desired SOC) from EVs, energy availability in-
gramming technique is used to solve the optimization problem, formation from the ES, and grid constraints (grid capacity, pric-
and it is shown that the evening and night hours are preferable ing, and regulation requirements) and executes the heuristic al-
for charging/discharging of EVs, which reduce the grid stress gorithm to determine the charge/discharge rate of the ES along
while maximizing the EVs’ benefits. with the charge rates of EVs.
Saber and Venayagamoorthy [37] used particle swarm opti-
mization [71] for charge scheduling that considers the uncer-
tainties of power generation from RESs and constraints put by C. Static Decentralized Scheduling
different non-EV loads and EVs in a smart grid. Statistical data
have been used to generate several valid scenarios for uncertain- This subclass of scheduling uses decentralized control and
ties arising out of solar and wind power. The objective function does not consider any mobility parameters of EVs.
aims at minimizing the carbon emissions and reducing power The interactions of EVs with aggregators in a V2G market
generation costs. The vehicle load, spinning reserve limit, gen- for frequency regulation are studied by Wu et al. [58] using a
eration limit, SOC, battery efficiency, parking lot limitations, game-theoretic model. The frequency regulation provided by
and charging/discharging inverter efficiency are considered as an aggregator is directly proportional to the number of EVs
system constraints in the problem formulation. under its control, and it requires that the difference between
the total discharge amount by the EVs’ batteries and the total
charging done for the EVs’ batteries for any aggregator should
B. Mobility-Aware Centralized Scheduling
match the total charging or discharging level requested to it by
This subclass of scheduling also uses centralized control but the ISO. However, lack of EVs’ cooperation or less number
takes some mobility aspects of the EVs into consideration while of EVs sometimes causes the imbalance between charging and
forming a charge schedule. discharging in some of the time slots. To overcome this prob-
Sortomme and El-Sharkawi [34] developed a V2G algo- lem, the authors introduced a backup battery bank (BBB) with
rithm to optimize energy and ancillary services (regulation and each aggregator for achieving the frequency regulation target.
spinning reserves) scheduling. This algorithm maximizes the The design objective for an aggregator is to minimize the use
profit of the aggregator while providing system flexibility and of costly BBB while achieving the overall frequency regulation
peak load shaving to the grid and low costs of EV charging for the grid. In practice, EVs are not under direct control of
to the customer. The formulation also considers unplanned EV an aggregator. Therefore, a decentralized control mechanism
departures during the contract periods and compensates accord- is proposed that does the resource management efficiently by
ingly. Simulations using a set of 10 000 EVs in the Electric adopting a smart pricing policy as part of the game. It is shown
Reliability Council of Texas system [72] using different battery that the distributed behaviors of self-interested EVs can achieve
replacement costs demonstrate that the algorithm can provide the same optimal performance in frequency regulation as that of
significant benefits. the centrally controlled system.
Khodayar et al. [38] introduced the stochastic security- Vandael et al. [60] proposed a multiagent system (MAS)-
constrained unit commitment model for studying the integra- based solution for demand-side management of PHEVs. An
tion of stochastic energy demand from a group of PEVs with optimal scheduler is designed using quadratic-programming-
stochastic energy supply from renewable wind energy sources. based technique that acts as a reference solution. However,
The objective is to minimize the expected grid operation cost the lack of complete information and the poor scalability with
subject to system and generator constraints while considering number of EVs make the solution infeasible in practice. Two
the random behavior of the PEVs with different spatiotemporal different MAS-based coordination strategies are developed that
constraints. A PEV fleet is characterized by its initial and use less data than a central scheduler: 1) the energy limiter only
final locations, arrival and departure times at intermediate stops uses load predictions, and 2) the power limiter does not use any
along its route, locations of charging stations, and driving forecast data. The system constantly adapts to new information
patterns. The problem is formulated as a stochastic optimization through coordination between the agents. It is found that the
problem where the vehicle fleet size with different energy MAS-based solution gives more adaptable and scalable solution
requirements, the errors of forecasted loads, the wind and hydro that differs only 5% from the optimal solution.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

10 IEEE SYSTEMS JOURNAL

Fan [61] assumed that the vehicle owners have the informa- VI. U NCERTAINTY M ODELING
tion of the current price that is proportional to the overall system
The operation of power generation and distribution systems
load. Based on this information, the vehicle owners try to adapt
in general and EV charging in particular is dependent on several
their demands to maximize their own utility. Motivated by the
parameters with inherent uncertainty in them, such as power
concept of congestion pricing in Internet Protocol networks,
demand, power generation capacity and pricing, and failure or
a simple adaptation mechanism is proposed based on price
forced outage of lines. Modeling such uncertainties and use of
feedback, which is shown to be very effective in achieving
proper forecasting techniques are important. To tackle these
demand response. User preference is modeled as a willingness
uncertainties, several uncertainty modeling tools have been
to pay parameter that affects the price and the charging rate.
used such as information gap decision theory [73]–[75], proba-
Based on this distributed algorithm, the author then proposed a
bilistic approach (Monte Carlo simulation [38], point estimate
novel charging method, where PHEVs can adapt their charging
method [76], scenario-based decision making [76]), possibilis-
rates according to their preferences.
tic approach [77], [78], robust optimization [79], and interval
Ota et al. [62] proposed an autonomous distributed V2G con-
analysis [80].
trol scheme. Controllable RESs, heat pumps, water heaters, and
In the power generation end, [1], [37], [38], and [42] took
battery ESs are integrated in the regional energy management
the impact of uncertainties in renewable power generation into
system of the distribution grid. An EV acts as a distributed
account while formulating the EV charge scheduling problem.
responsive reserve and supplies power back to the grid based
Sortomme and El-Sharkawi [1] used hourly wind schedules
on the supply–demand imbalance to counteract the frequency
based on a 30-min persistence forecast by adding random
deviation while plugged into the charger outlet at a charging
error to the average wind power generation. Uncertainties of
station. Therefore, V2G power control is done with the droop
wind availabilities are handled deterministically by Awami and
characteristics against the frequency deviation. If the frequency
Sortomme [42]. The uncertainties of wind and solar energy
deviation drops below a minimum threshold limit, the vehicle
sources are considered as different probability distributions in
discharges at its maximum rate instantly to the grid; otherwise,
Saber and Venayagamoorthy [37]. Khodayar et al. [38] used
vehicle battery is charged from the grid.
the Monte Carlo simulation method to handle power system
outages modeled with probability distributions. In other works
D. Mobility-Aware Decentralized Scheduling
not related to EV charging, Mohammmadi-Ivatloo et al. [75]
This subclass of scheduling also uses decentralized control handled generation-side uncertainties such as forced outage
but takes some mobility aspects of EVs into consideration. of generating units by information gap decision theory to
He et al. [35] gave a centralized and a decentralized solution determine the operation schedule of a generation company.
for charge scheduling of a large number of EVs with random Soroudi et al. [77] considered uncertainties in the price
arrival times. In the formulation, maximum battery capacity, of electricity in pool market and the demands of each in-
initial battery charge, charging interval, EV’s arrival and de- vestor and applied information gap decision theory, which
parture times, charging power, system load, and energy pricing helps the distribution network operators in selecting the re-
are taken into consideration. As an output, the charging power sources such as pool market, distributed generations, and bi-
and whether an EV is charged or remains idle in an interval is lateral contracts for meeting the customer demand. Venkatesh
calculated using convex optimization technique. However, the et al. [78] used possibilistic approaches to handle wind en-
assumption of knowing future load and arrival times of EVs ergy generators while determining the thermal power units’
information a priori is unrealistic. To develop a more realistic optimal day-ahead unit commitment schedule. Wang et al.
solution, the authors aimed to minimize the total cost of the [80] employed interval analysis to characterize intermit-
EVs in the current ongoing EV set in the local group. The tent wind power generation. In order to model the wind
electricity price is assumed to be constant across locations at power generation and load demand uncertainties for the en-
a time instant. A group is constructed from the EVs in one ergy and reserve scheduling, a two-stage stochastic program-
location or multiple nearby locations. Each group is controlled ming framework is implemented by Zakariazadeh et al. [81].
by a local controller (LC). The charging stations at the local site Uncertainties in load forecast in EV charge scheduling are
are connected to the central controller through communication handled in [1], [39], and [42]. Erol-Kantarci and Mouftah [39]
channel established by the LC. On receiving the forecasted used short-term forecasting techniques by employing the
loads for the day from the central controller and collecting the similar-day approach, which searches a historical database to
EV information from each charging station in real time, LC runs find a day with similar weather properties. Sortomme and
a local scheduling optimization algorithm and then instructs El-Sharkawi [1] generated load schedules by adding an error
each local EV to charge or discharge its battery with the optimal to the actual average load per hour. Load uncertainties were
charging powers. handled in deterministic manner by Awami and Sortomme
Jin et al. [64] designed a decentralized online charge schedul- [42]. In the renewable and nonrenewable distributed generation
ing algorithm for large number of EVs, where the EVs can be planning, Soroudi et al. [82] used Monte Carlo simulation to
highly heterogeneous and may start their charging dynamically. deal with uncertainties in load, generated wind power, and
The algorithm uses a clustering-based strategy that classifies electricity price.
heterogeneous EVs into multiple groups, and a sliding-window- In other works on handling uncertainty, the price un-
based iterative approach is adopted to schedule the charging certainties for energy prices are considered by Awami and
demand for the EVs in each group in real time. After the Sortomme [42] in the problem formulation. Pantos [76] used
optimization, the EVs in a group will adjust their individual point estimation method to model the uncertainties in en-
charging rates based on their energy requirements. ergy pricing. Probability distributions are used to model
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

MUKHERJEE AND GUPTA: REVIEW OF CHARGE SCHEDULING OF ELECTRIC VEHICLES IN SMART GRID 11

uncertainties of time of arrival and time of departure of EVs for better schedule planning. In addition, while the current
in [37], [44], [48], and [54]. Hajimiragha et al. [79] studied charging model assumes that the EV will be connected to a
the technical and financial impact of integrating the power grid charging station, an alternate charging model of the future can
during off-peak hours for charging PHEVs. Wu et al. [44] be one where charged batteries can be also sold as a commod-
modeled timing errors in the departure of PEVs in Gaussian ity, and an EV can just replace its batteries from designated
error terms. charging stations with precharged batteries to save time. In such
mixed charging scenarios with competitive and dynamic pricing
VII. O PEN I SSUES AND R ESEARCH D IRECTIONS among vendors, on-time delivery of information and the effect
of dynamic user choices on the charge scheduling problem are
An analysis of the works surveyed indicates that most of interesting problems to investigate.
them address unidirectional power flow and are static and
centralized. It is expected that the future grid will have a very C. Bidirectional Power Flow
large number of EVs of different types integrated in it. Making
centralized decisions for charging this large number of EVs will Bidirectional power flow compounds the problems stated
be computationally intractable and impractical [52]. Similarly, earlier by adding a greater degree of uncertainty to the schedul-
ignoring the mobility of the EVs will be totally unrealistic in ing process. In addition to the algorithmic challenges of dealing
terms of load planning and delivery [35]. At the same time, with the uncertainty, studying the effect of frequent discharging
the future grid will enjoy the benefits of bidirectional power on EV batteries and integrating this effect in the optimization
transfer to and from the EVs. The charge scheduling algorithms problem solved are interesting problems.
of the future are therefore expected to be bidirectional, de-
centralized, and mobility aware. We next discuss some of the D. Security Issues
research challenges arising out of these issues.
Inherent to all the issues discussed above is the fundamental
issue of providing security and privacy. Users need to be
A. Decentralized Charging guaranteed of privacy of their data such as charging location and
It has been already noted that the limited capacity of a single profiles. This is of more importance in decentralized scheduling
EV restrains itself from participating in energy markets, and and scheduling using interaggregator collaboration. The charg-
hence, for a totally decentralized solution, it will be necessary ing model also opens up the issue of EVs sending malicious and
for a group of EVs to pull together [64]. Forming and maintain- wrong information to affect the grid load. While some works
ing such groups of the right size and composition dynamically exist in the area of vehicular communication in handling such
in a decentralized manner is a challenging task. A more practi- privacy and misbehavior detection issues, their effect on charge
cal approach seems to be a service-oriented framework where scheduling of EVs and ways to mitigate them have not been
multiple aggregators vie for business of the EVs. EVs can sub- adequately studied.
scribe to services of aggregators (similar to telecom operators),
and aggregators can own/contract charging stations at which the VIII. C ONCLUSION
subscribed EVs can charge. It opens up interesting issues of In this paper, we have attempted to review the existing works
dynamic and decentralized interaggregator collaboration to use on charge scheduling of EVs, an area that has seen tremen-
each other’s resources to provide the necessary service to their dous research activity in the last few years. Several possible
subscribers while maximizing their own profits. Investigating ways of classifying the works based on different parameters
such interaggregator collaboration mechanisms is an interesting and operating environment have been discussed, and based on
research challenge. this, a classification hierarchy is proposed. The classification
first considers the two broad classes of unidirectional versus
B. Mobility Issues bidirectional charging and then further classifies them based
on whether the scheduling decision is made centrally at the
Most people follow a certain driving pattern most of the days,
aggregator or distributively at the EVs and whether mobility
and hence, learning from trip histories or routes can be a very
aspects of the EVs are considered or not. With the expected
useful tool that can be used for efficient charge scheduling.
surge in the number of EVs on the roads in the coming years,
If a person has reasonable stopping times at multiple places
coordinating their charging schedules is definitely going to
with charging stations during a day (including at home), the
become more important and complex. This survey is a step to
aggregator has the flexibility of scheduling the charging of the
identify the current state of the art in the area and some of the
EV at one or more of multiple locations based on different
interesting research challenges.
parameters and constraints and informing the customer of the
same. In such a scenario, the aggregator needs to only know
R EFERENCES
the charge demand profile of the EV and can estimate the
arrival/departure time at each location. [1] E. Sortomme and M. A. El-Sharkawi, “Optimal charging strategies for
unidirectional vehicle-to-grid,” IEEE Trans. Smart Grid, vol. 2, no. 1,
Integrating the charge scheduling problem more closely with pp. 131–138, Mar. 2011.
existing works on mobility and communication management [2] K. Clement-Nyns, E. Haesen, and J. Driesen, “The impact of charging
of vehicles can also open up interesting issues. These include plug-in hybrid electric vehicles on a residential distribution grid,” IEEE
Trans. Power Syst., vol. 25, no. 1, pp. 371–380, Feb. 2010.
integration with current traffic information to estimate arrival [3] S. Han, S. Han, and K. Sezaki, “Development of an optimal vehicle-to-
times more accurately and the use of vehicular networks for on- grid aggregator for frequency regulation,” IEEE Trans. Smart Grid, vol. 1,
time delivery of information between an EV and an aggregator no. 1, pp. 65–72, Jun. 2010.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

12 IEEE SYSTEMS JOURNAL

[4] A. G. Boulanger, A. Chu, S. Maxx, and D. Waltz, “Vehicle electrifi- [37] A. Saber and G. Venayagamoorthy, “Resource scheduling under uncer-
cation: Status and issues,” Proc. IEEE, vol. 99, no. 6, pp. 1116–1138, tainty in a smart grid with renewables and plug-in vehicles,” IEEE Syst.
Jun. 2011. J., vol. 6, no. 1, pp. 103–109, Mar. 2012.
[5] O. Sundstrom and C. Binding, “Flexible charging optimization for electric [38] M. E. Khodayar, L. Wu, and M. Shahidehpour, “Hourly coordina-
vehicles considering distribution grid constraints,” IEEE Trans. Smart tion of electric vehicle operation and volatile wind power generation
Grid, vol. 3, no. 1, pp. 26–37, Mar. 2012. in SCUC,” IEEE Trans. Smart Grid, vol. 3, no. 3, pp. 1271–1279,
[6] Q. Gong, S. Midlam-Mohler, V. Marano, and G. Rizzoni, “Study of PEV Sep. 2012.
charging on residential distribution transformer life,” IEEE Trans. Smart [39] M. Erol-Kantarci and H. T. Mouftah, “Prediction-based charging of
Grid, vol. 3, no. 1, pp. 404–412, Mar. 2012. PHEVs from the smart grid with dynamic pricing,” in Proc. IEEE 35th
[7] B. Jansen, C. Binding, O. Sundstrom, and D. Gantenbein, “Architecture Conf. LCN, 2010, pp. 1032–1039.
and communication of an electric vehicle virtual power plant,” in Proc. [40] E. Sortomme, M. M. Hindi, S. D. J. MacPherson, and S. S. Venkata,
1st IEEE Int. Conf. SmartGridComm, 2010, pp. 149–154. “Coordinated charging of plug-in hybrid electric vehicles to minimize
[8] P. Siano, C. Cecati, H. Yu, and J. Kolbusz, “Real time operation of distribution system losses,” IEEE Trans. Smart Grid, vol. 2, no. 1,
smart grids via FCN networks and optimal power flow,” IEEE Trans. Ind. pp. 198–205, Mar. 2011.
Informat., vol. 8, no. 4, pp. 944–952, Nov. 2012. [41] E. Sortomme and M. El-Sharkawi, “Optimal combined bidding of vehicle-
[9] P. Siano, “Demand response and smart grids—A survey,” Renew. Sustain. to-grid ancillary services,” IEEE Trans. Smart Grid, vol. 3, no. 1, pp. 70–
Energy Rev., vol. 30, no. C, pp. 461–478, Feb. 2014. 79, Mar. 2012.
[10] C. Cecati, C. Citro, A. Piccolo, and P. Siano, “Smart operation of wind [42] A. T. Al-Awami and E. Sortomme, “Coordinating vehicle-to-grid services
turbines and diesel generators according to economic criteria,” IEEE with energy trading,” IEEE Trans. Smart Grid, vol. 3, no. 1, pp. 453–462,
Trans. Ind. Electron., vol. 58, no. 10, pp. 4514–4525, Oct. 2011. Mar. 2012.
[11] [Online]. Available: http://www.carstuffshow.com//blog/how-to-convert- [43] M. Vasirani and S. Ossowski, “Lottery-based resource allocation for plug-
gasoline-energy-to-kilowatt-hours-kwh/ in electric vehicle charging,” in Proc. 11th Int. Conf. Auton. Agents
[12] [Online]. Available: http://www.nissanusa.com/electric-cars/leaf/ Multiagent Syst., 2012, pp. 1173–1174.
charging-range/ [44] D. Wu, D. Aliprantis, and L. Ying, “Load scheduling and dispatch for
[13] [Online]. Available: http://www.ford.com/cars/focus/trim/electric/ aggregators of plug-in electric vehicles,” IEEE Trans. Smart Grid, vol. 3,
[14] [Online]. Available: http://www.mitsubishicars.com/upcoming-vehicles no. 1, pp. 368–376, Mar. 2012.
[15] [Online]. Available: http://www.toyota.com/prius-plug-in/ [45] Y. Cao et al., “An optimized EV charging model considering TOU price
[16] [Online]. Available: http://www.afdc.energy.gov/vehicles/search/light/ and SOC curve,” IEEE Trans. Smart Grid, vol. 3, no. 1, pp. 388–393,
autos?fuel_type_code=PHEV Mar. 2012.
[17] [Online]. Available: http://www.chevrolet.com/volt-electric-car.html [46] S. Deilami, A. S. Masoum, P. S. Moses, and M. A. S. Masoum, “Real-
[18] A. Brooks, E. Lu, D. Reicher, C. Spirakis, and B. Weihl, “Demand dis- time coordination of plug-in electric vehicle charging in smart grids to
patch,” IEEE Power Energy Mag., vol. 8, no. 3, pp. 20–29, May/Jun. 2010. minimize power losses and improve voltage profile,” IEEE Trans. Smart
[19] [Online]. Available: http://www.afdc.energy.gov/fuels/electricity_ Grid, vol. 2, no. 3, pp. 456–467, Sep. 2011.
infrastructure.html [47] P. Richardson, D. Flynn, and A. Keane, “Local versus centralized charging
[20] [Online]. Available: http://www.afdc.energy.gov/fuels/electricity_ strategies for electric vehicles in low voltage distribution systems,” IEEE
stations.html Trans. Smart Grid, vol. 3, no. 2, pp. 1020–1028, Jun. 2012.
[21] F. Musavi, M. Edington, and W. Eberle, “Wireless power transfer: A sur- [48] W. Su and M.-Y. Chow, “Performance evaluation of an EDA-based large-
vey of EV battery charging technologies,” in Proc. IEEE Energy Convers. scale plug-in hybrid electric vehicle charging algorithm,” IEEE Trans.
Congr. Expo., 2012, pp. 1804–1810. Smart Grid, vol. 3, no. 1, pp. 308–315, Mar. 2012.
[22] Sae Electric Vehicle Inductively Coupled Charging, Sae J1173_201406, [49] C.-K. Wen, J.-C. Chen, J.-H. Teng, and P. Ting, “Decentralized plug-in
Jun. 5, 2014. electric vehicle charging selection algorithm in power systems,” IEEE
[23] M. Kline, I. Izyumin, B. Boser, and S. Sanders, “Capacitive power trans- Trans. Smart Grid, vol. 3, no. 4, pp. 1779–1789, 2012.
fer for contactless charging,” in Proc. 26th IEEE APEC Expo., 2011, [50] J. Lee, H.-J. Kim, G.-L. Park, and H. Jeon, “Genetic algorithm-
pp. 1398–1404. based charging task scheduler for electric vehicles in smart trans-
[24] W. Li, “High efficiency wireless power transmission at low frequency portation,” in Proc. 4th Asian Conf. Intell. Inf. Database Syst., 2012,
using permanent magnet coupling,” M.S thesis, Univ. British Columbia, pp. 208–217.
Vancouver, BC, Canada, 2007. [51] H.-J. Kim, J. Lee, and G.-L. Park, “Constraint-based charging scheduler
[25] A. Kurs et al., “Wireless power transfer via strongly coupled magnetic design for electric vehicles,” in Proc. 3rd Asian Conf. Intell. Inf. Database
resonances,” Science, vol. 317, no. 1, pp. 83–86, Jul. 2007. Syst., 2012, pp. 266–275.
[26] L. Farkas, “High power wireless resonant energy transfer system,” U.S. [52] Z. Ma, D. Callaway, and I. Hiskens, “Decentralized charging control
Patent 20 080 265 684 A1, Oct. 30, 2008. for large populations of plug-in electric vehicles: Application of the
[27] T. Imura, H. Okabe, and Y. Hori, “Basic experimental study on helical Nash certainty equivalence principle,” in Proc. IEEE Int. CCA, 2010,
antennas of wireless power transfer for electric vehicles by using magnetic pp. 191–195.
resonant couplings,” in Proc. IEEE Veh. Power Propulsion Conf., 2009, [53] N. Chen, C. W. Tan, and T. Q. S. Quek, “Optimal charging of electric
pp. 936–940. vehicles in smart grid: Characterization and valley-filling algorithms,” in
[28] [Online]. Available: http://www.teslamotors.com/batteryswap Proc. IEEE 3rd Int. Conf. Smart Grid Commun., 2012, pp. 13–18, vol. abs/
[29] [Online]. Available: http://www.afdc.energy.gov/fuels/stations_counts. 1208.4743.
html [54] S. Hutterer, M. Affenzeller, and F. Auinger, “Evolutionary optimization
[30] [Online]. Available: http://www.afdc.energy.gov/fuels/electricity_ of multi-agent control strategies for electric vehicle charging,” in Proc.
locations.html GECCO, 2012, pp. 3–10, (Companion).
[31] [Online]. Available: http://www.iea.org/publications/globalevoutlook_ [55] Y. Xu and F. Pan, “Scheduling for charging plug-in hybrid electric vehi-
2013.pdf cles,” in Proc. IEEE 51st CDC, 2012, pp. 2495–2501.
[32] W. Kempton and J. Tomic, “Vehicle-to-grid power implementation: From [56] Q. Li, T. Cui, R. Negi, F. Franchetti, and M. D. Ilic, “On-line decentralized
stabilizing the grid to supporting large-scale renewable energy,” J. Power charging of plug-in electric vehicles in power systems,” in Proc. Optim.
Sources, vol. 144, no. 1, pp. 280–294, Jun. 2005. Control, 2011, pp. 1–12, CoRR.
[33] J. Tomic and W. Kempton, “Using fleets of electric-drive vehicles [57] L. Gan, U. Topcu, and S. H. Low, “Optimal decentralized protocol
for grid support,” J. Power Sources, vol. 168, no. 2, pp. 459–468, for electric vehicle charging,” in Proc. 50th IEEE CDC-ECE, 2011,
Jun. 2007. pp. 5798–5804.
[34] E. Sortomme and M. A. El-Sharkawi, “Optimal scheduling of vehicle-to- [58] C. Wu, H. Mohsenian-Rad, and J. Huang, “Vehicle-to-aggregator in-
grid energy and ancillary services,” IEEE Trans. Smart Grid, vol. 3, no. 1, teraction game,” IEEE Trans. Smart Grid, vol. 3, no. 1, pp. 434–442,
pp. 351–359, Mar. 2012. Mar. 2012.
[35] Y. He, B. Venkatesh, and L. Guan, “Optimal scheduling for charging and [59] G. Shrestha and B. C. Chew, “Study on the optimization of charge-
discharging of electric vehicles,” IEEE Trans. Smart Grid, vol. 3, no. 3, discharge cycle of electric vehicle batteries in the context of Singapore,”
pp. 1095–1105, Sep. 2012. in Proc. AUPEC, 2007, pp. 1–7.
[36] A. Y. Saber and G. K. Venayagamoorthy, “Intelligent unit commitment [60] S. Vandael, N. Boucké, T. Holvoet, K. D. Craemer, and G. Deconinck,
with vehicle-to-grid—A cost-emission optimization,” J. Power Sources, “Decentralized demand side management of plug-in hybrid vehicles in a
vol. 195, no. 3, pp. 898–911, Feb. 2010. smart grid,” in Proc. AAMAS, 2011, pp. 803–810.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

MUKHERJEE AND GUPTA: REVIEW OF CHARGE SCHEDULING OF ELECTRIC VEHICLES IN SMART GRID 13

[61] Z. Fan, “A distributed demand response algorithm and its application to [78] B. Venkatesh, P. Yu, H. Gooi, and D. Choling, “Fuzzy MILP unit commit-
PHEV charging in smart grids,” IEEE Trans. Smart Grid, vol. 3, no. 3, ment incorporating wind generators,” IEEE Trans. Power Syst., vol. 23,
pp. 1280–1290, Sep. 2012. no. 4, pp. 1738–1746, Nov. 2008.
[62] Y. Ota et al., “Autonomous distributed V2G (vehicle-to-grid) satisfying [79] A. Hajimiragha, C. Canizares, M. Fowler, S. Moazeni, and A. Elkamel, “A
scheduled charging,” IEEE Trans. Smart Grid, vol. 3, no. 1, pp. 559–564, robust optimization approach for planning the transition to plug-in hybrid
Mar. 2012. electric vehicles,” IEEE Trans. Power Syst., vol. 26, no. 4, pp. 2264–2274,
[63] C. Jin, J. Tang, and P. Ghosh, “Optimizing electric vehicle charging with Nov. 2011.
energy storage in the electricity market,” IEEE Trans. Smart Grid, vol. 4, [80] Y. Wang, Q. Xia, and C. Kang, “Unit commitment with volatile node in-
no. 1, pp. 311–320, Mar. 2013. jections by using interval optimization,” IEEE Trans. Power Syst., vol. 26,
[64] R. Jin, B. Wang, P. Zhang, and P. B. Luh, “Decentralised online charging no. 3, pp. 1705–1713, Aug. 2011.
scheduling for large populations of electric vehicles: A cyber-physical [81] A. Zakariazadeh, S. Jadid, and P. Siano, “Economic-environmental energy
system approach,” Int. J. Parallel, Emergent Distrib. Syst., vol. 28, no. 1, and reserve scheduling of smart distribution systems: A multiobjective
pp. 29–45, Feb. 2013. mathematical programming approach,” Energy Convers. Manag., vol. 78,
[65] W. Kempton and J. Tomic, “Vehicle-to-grid power fundamentals: Cal- pp. 151–164, Feb. 2014.
culating capacity and net revenue,” J. Power Sources, vol. 144, no. 1, [82] A. Soroudi, R. Caire, N. Hadjsaid, and M. Ehsan, “Probabilistic dynamic
pp. 268–279, Jun. 2005. multi-objective model for renewable and non-renewable distributed gen-
[66] M. A. S. Masoum, M. Ladjevardi, E. F. Fuchs, and W. Grady, “Application eration planning,” IET Generation, Transmiss. Distrib., vol. 5, no. 11,
of local variations and maximum sensitivities selections for optimal place- pp. 1173–1182, Nov. 2011.
ment of shunt capacitor banks under nonsinusoidal operating conditions,”
Int. J. Electr. Power Energy Syst., vol. 26, no. 10, pp. 761–769, Dec. 2004.
[67] P. Larranaga and J. A. Lozano, Estimation of Distribution Algorithm: A
New Tool for Evolutionary Computation. Boston, MA, USA: Kluwer,
2002. Joy Chandra Mukherjee received the B.Tech. de-
[68] M. Huang, P. Caines, and R. Malhamé, “Individual and mass behavior in gree in computer science and engineering from
large population stochastic wireless power control problems: Centralized the University of Kalyani, Kalyani, India, in 2004
and Nash equilibrium solutions,” in Proc. 42th IEEE Int. Conf. Decision and the M.Tech. degree in computer science and
Control, 2003, pp. 98–103. engineering from the Indian Institute of Technol-
[69] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: ogy Kharagpur, Kharagpur, India, in 2011. He is
Cambridge Univ. Press, 2004. currently working toward the Ph.D. degree in the
[70] J. Lavaei and S. Low, “Zero duality gap in optimal power flow problem,” Department of Computer Science and Engineering,
IEEE Trans. Power Syst., vol. 27, no. 1, pp. 92–107, Feb. 2012. Indian Institute of Technology Kharagpur.
[71] Y. Valle, G. K. Venayagamoorthy, S. Mohagheghi, J. Hernandez, and From 2004 to 2007, he worked in the area of de-
R. G. Harley, “Particle swarm optimization: Basic concepts, variants and sign and implementation of large information tech-
applications in power systems,” IEEE Trans. Evol. Comput., vol. 12, no. 2, nology systems with Cognizant Technology Solutions and Tata Consultancy
pp. 171–195, Apr. 2008. Services. His research interests include smart grid, mobile computing, and
[72] Electric Reliability Council of Texas, Market Information, Aug. 2010. distributed algorithms.
[Online]. Available: http://www.ercot.com/mktinfo/
[73] A. Soroudi and M. Ehsan, “IGDT based robust decision making tool for
DNOs in load procurement under severe uncertainty,” IEEE Trans. Smart
Grid, vol. 4, no. 2, pp. 886–895, Jun. 2013. Arobinda Gupta received the Ph.D. degree in com-
[74] A. Soroudi and T. Amraee, “Decision making under uncertainty in energy puter science from The University of Iowa, Iowa, IA,
systems: State of the art,” Renew. Sustain. Energy Rev., vol. 28, no. 0, USA, in 1997.
pp. 376–384, Dec. 2013. From 1997 to 1999, he was with the Windows
[75] B. Mohammadi-Ivatloo, H. Zareipour, N. Amjady, and M. Ehsan, 2000 Distributed Infrastructure Group, Microsoft
“Application of information-gap decision theory to risk-constrained Corporation, Redmond, WA, USA, where he was in-
self-scheduling of gencos,” IEEE Trans. Power Syst., vol. 28, no. 2, volved in the design and development of large-scale
pp. 1093–1102, May 2013. distributed systems. Since October 1999, he has been
[76] M. Pantos, “Exploitation of electric-drive vehicles in electricity markets,” a Faculty with the Indian Institute of Technology
IEEE Trans. Power Syst., vol. 27, no. 2, pp. 682–694, May 2012. Kharagpur, Kharagpur, India, where he is currently
[77] A. Soroudi, M. Ehsan, R. Caire, and N. Hadjsaid, “Possibilistic evaluation a Professor in the Department of Computer Science
of distributed generations impacts on distribution networks,” IEEE Trans. and Engineering. His current research interests include distributed systems,
Power Syst., vol. 26, no. 4, pp. 2293–2301, Nov. 2011. mobile computing, and wireless ad hoc and sensor networks.