Dissertation Doctor of Philosophy Yih-Fang Huang Electrical Engineering

# ENGINEERING AND ECONOMIC ANALYSIS FOR ELECTRIC VEHICLE CHARGING
INFRASTRUCTURE — PLACEMENT, PRICING, AND MARKET DESIGN

Chao Luo

(2017)

###### Abstract

The objective of this dissertation is to study the interplay between large-
scale electric vehicle (EV) charging and the power system. In particular, we
address three important issues pertaining to EV charging and integration into
the power system: (1) charging station placement, (2) pricing policy and
energy management strategy, and (3) electricity trading market and
distribution network design to facilitate integrating EV and renewable energy
source (RES) into the power system.

Regarding the charging station placement problem, we propose a multi-stage
consumer behavior based placement strategy with incremental EV penetration
rates and model the EV charging industry as an oligopoly where the entire
market is dominated by a few charging service providers (oligopolists). A
nested logit model is employed to characterize the charging preference of the
EV owners. The optimal placement policy for each service provider is obtained
by solving a Bayesian game. We also developed a simulation toolkit called “The
EV Virtual City” based on Repast. We observe that service providers prefer
clustering instead of separation in the EV charging market.

As for the problem of pricing and energy management of EV charging stations,
we provide guidelines for charging service providers to determine charging
price and manage electricity reserve to balance the competing objectives of
improving profitability, enhancing customer satisfaction, and reducing impact
on the power system. In the presence of renewable energy integration and
energy storage system, EV charging service providers must deal with a number
of uncertainties, e.g., charging demand volatility, inherent intermittency of
renewable energy generation, and wholesale electricity price fluctuation. We
propose a new metric to assess the impact on power system without needing to
solve complete power flow equations. Two algorithms — stochastic dynamic
programming (SDP) algorithm and greedy algorithm (benchmark algorithm) — are
applied to derive the pricing and electricity procurement strategy. We find
that the charging service provider is able to reshape spatial-temporal
charging demands to reduce the impact on power grid via pricing signals.

The last technical contribution of this dissertation is on the design of a
novel electricity trading market and distribution network, which provides a
platform to support seamless RES integration, grid to vehicle (G2V), vehicle
to grid (V2G), vehicle to vehicle (V2V), and distributed generation (DG) and
storage. We apply a sharing economy model to the electricity sector to
stimulate different entities to exchange and monetize their underutilized
electricity. We propose an online advertisement-based peer-to-peer (P2P)
electricity trading mechanism. A fitness-score (FS)-based supply-demand
matching algorithm is developed by considering consumer surplus, electricity
network congestion, and economic dispatch. We compare the FS matching
algorithm with the first-come-first-serve (FCFS) algorithm. The simulation
results show that the FS matching algorithm outperforms the FCFS algorithm in
terms of network congestion management, electricity delivery delay
probability, energy efficiency, and consumer surplus.

Chao Luo

###### Contents

  1. 1 INTRODUCTION
    1. 1.1 Overview
    2. 1.2 EV Ecosystem
      1. 1.2.1 Power Plant
      2. 1.2.2 ISO/RTO
      3. 1.2.3 Reseller
      4. 1.2.4 EV Charging Infrastructure
      5. 1.2.5 Electricity Transmission Network
      6. 1.2.6 Electricity Distribution Network
    3. 1.3 Emerging EV Market
      1. 1.3.1 Hybrid Electric Vehicle (HEV)
      2. 1.3.2 Plug-in Hybrid Electric Vehicle (PHEV)
      3. 1.3.3 Battery Electric Vehicle/All Electric Vehicle (BEV/AEV)
    4. 1.4 Benefits of EVs
      1. 1.4.1 Economic Growth
      2. 1.4.2 Environmental Sustainability
      3. 1.4.3 Energy Security
    5. 1.5 State of the Art of EV Technology
      1. 1.5.1 Powertrain
      2. 1.5.2 Battery
    6. 1.6 Challenges of Large-Scale EV Integration
      1. 1.6.1 Large-Scale EV Charging Scheduling
      2. 1.6.2 Limited Battery Capacity and Long Charging Time
      3. 1.6.3 Insufficient EV Public Charging Infrastructure
      4. 1.6.4 Charging Station Operation and Management
      5. 1.6.5 Liberal Electricity Trading Market and Distribution Network
    7. 1.7 Dissertation Organization
  2. 2 INTERPLAY BETWEEN EV CHARGING AND THE POWER SYSTEM
    1. 2.1 Overview
    2. 2.2 EV Charging System
      1. 2.2.1 EV Charging Standard
      2. 2.2.2 Electric Vehicle Supply Equipment
      3. 2.2.3 EV Charging Coupler and Plug Receptacle
    3. 2.3 EV Charging, Power System, and Electricity Market
      1. 2.3.1 Power System and Control
      2. 2.3.2 ISO/RTO and Electricity Market
      3. 2.3.3 Interplay between EV Charging and Power System
  3. 3 PLACEMENT OF EV CHARGING STATIONS — BALANCING THE BENEFITS AMONG MULTIPLE ENTITIES
    1. 3.1 Overview
    2. 3.2 Motivation and Related Work
    3. 3.3 Preliminaries on Oligopoly and Consumer Behavior Analytics
      1. 3.3.1 Oligopoly Market
      2. 3.3.2 Consumer Behavior Analytics
    4. 3.4 Problem Formulation
      1. 3.4.1 Profit of EV Charging
      2. 3.4.2 Impact of EV Charging on Power Grid
      3. 3.4.3 Quality-of-Service Metrics
      4. 3.4.4 Multi-Stage Charging Station Planning Scheme
      5. 3.4.5 Emerging Problems
    5. 3.5 EV Charging Demand Estimation
    6. 3.6 Impact of EV Integration on Power Grid
    7. 3.7 Spatial Competition and Optimal Placement through a Bayesian Game
    8. 3.8 Simulation Platform Development and Case Study
    9. 3.9 Conclusion
  4. 4 STOCHASTIC DYNAMIC PRICING FOR EV CHARGING STATIONS WITH RENEWABLES INTEGRATION AND ENERGY STORAGE
    1. 4.1 Overview
    2. 4.2 Motivation and Related Work
    3. 4.3 Preliminary on Dynamic Programming
      1. 4.3.1 Basic Model
      2. 4.3.2 Principle of Optimality
    4. 4.4 Problem Formulation
      1. 4.4.1 Profit of Charging Service Provider
      2. 4.4.2 Customer Satisfaction
      3. 4.4.3 Impact on Power Grid
      4. 4.4.4 Multi-Objective Optimization Framework
    5. 4.5 Charging Demand Estimation
    6. 4.6 Impact on Power Grid from EV Charging
    7. 4.7 Stochastic Dynamic Programming for Pricing and Electricity Procurement
      1. 4.7.1 A Safeguard of Profit
      2. 4.7.2 Renewable Energy and Real Time Wholesale Price
      3. 4.7.3 Stochastic Dynamic Programming
    8. 4.8 Simulations and Discussions
      1. 4.8.1 SDP Algorithm versus Greedy Algorithm
      2. 4.8.2 Aggressive or Conservative Electricity Procurement Strategy
      3. 4.8.3 Charging Price with Safeguard of Profit
      4. 4.8.4 Pareto Optima and Knee Points
      5. 4.8.5 Interplays between Profit, Customer Satisfaction, and Impact on Power Grid
      6. 4.8.6 Spatial Charging Demand versus Impact on Power Grid
    9. 4.9 Conclusion
  5. 5 THE DESIGN OF A LIBERAL ELECTRICITY TRADING MARKET AND DISTRIBUTION NETWORK — A SHARING ECONOMY PERSPECTIVE
    1. 5.1 Overview
    2. 5.2 Motivation and Related Work
      1. 5.2.1 Related Work
      2. 5.2.2 Main Contributions
    3. 5.3 Problem Formulation
      1. 5.3.1 Supply and Demand Matcher
      2. 5.3.2 Electricity Flow Optimizer
      3. 5.3.3 Demand and Surge Price Prediction Module
      4. 5.3.4 Payment Settlement Module
    4. 5.4 Simulations and Discussions
      1. 5.4.1 Network Congestion Probability
      2. 5.4.2 Electricity Delivery Delay Probability
      3. 5.4.3 Network Throughput
      4. 5.4.4 Power Loss
      5. 5.4.5 Consumer Surplus
    5. 5.5 Conclusion
  6. 6 MAIN CONTRIBUTIONS AND FUTURE WORK
    1. 6.1 Main Contributions
      1. 6.1.1 Optimal EV Charging Station Placement
      2. 6.1.2 Dynamic Pricing and Electricity Management Policy of EV Charging Station
      3. 6.1.3 Electricity Trading Market and Distribution Network Redesign
    2. 6.2 Future Work
  7. A DISCRETE CHOICE MODEL FORMULA
    1. A.1 Derivation of Eq. (3.10)
  8. B MOBILE APPLICATION DEVELOPMENT — EV CHARGING BUTLER

###### List of Figures

  1. 1.1 Energy Flow and Cash Flow in EV Ecosystem
  2. 1.2 PHEV Sales
  3. 1.3 EV Market Share
  4. 1.4 Comparison EV with ICE in Global Warming Emission
  5. 1.5 Powertrain: Series HEV and PHEV
  6. 1.6 Powertrain: Parallel HEV and PHEV
  7. 1.7 Powertrain: Series-Parallel HEV and PHEV
  8. 1.8 Powertrain: BEV
  9. 2.1 Basic Elements of a Power System
  10. 2.2 Supplier Surplus
  11. 2.3 Customer Surplus
  12. 2.4 Social Surplus
  13. 2.5 Vehicle to Grid Mechanism
  14. 3.1 The Architecture of The EV Virtual City 1.0
  15. 3.2 Roads and Buildings of San Pedro District
  16. 3.3 The Statistics of Travel Patterns
  17. 3.4 IEEE 118-Bus Power System Test Case
  18. 3.5 A Snapshot of EVs Movement
  19. 3.6 Stage 1 Placement
  20. 3.7 Stage 2 Placement
  21. 3.8 Stage 3 Placement
  22. 3.9 Stage 4 Placement
  23. 3.10 Superimposing All Stages
  24. 3.11 Charging Station verses EV Penetration Rate
  25. 4.1 The EV Charging Market
  26. 4.2 Sample Customer Satisfaction Functions ($E=200$)
  27. 4.3 Dynamic Pricing and Energy Management Algorithm
  28. 4.4 Typical Daily Solar Radiation
  29. 4.5 SDP Profit Increase Percentage
  30. 4.6 Electricity Procurement with Different Storage Cost
  31. 4.7 Charging Prices with Different $W_{\textrm{min}}$
  32. 4.8 Pareto Front
  33. 4.9 Pareto Front with Knee Points
  34. 4.10 Profit vs Customer Satisfaction
  35. 4.11 Profit vs Impact on Power Grid
  36. 4.12 Customer Satisfaction vs Impact on Power Grid
  37. 4.13 Charging Demand Redistribution with Different Impacts
  38. 5.1 Market and Network Architecture
  39. 5.2 Electricity Network Congestion Comparison
  40. 5.3 Electricity Delivery Delay Comparison
  41. 5.4 Electricity Network Throughput Comparison
  42. 5.5 Power Loss Comparison
  43. 5.6 Consumer Surplus Comparison
  44. B.1 Facebook Login Activity
  45. B.2 Main Activity
  46. B.3 Profile Settings
  47. B.4 Charging Preference Settings
  48. B.5 Recommendation List
  49. B.6 Charging Station Information

###### List of Tables

  1. 2.1 CHARGE METHOD ELECTRICAL RATINGS (NORTH AMERICA)
  2. 4.1 SIMULATION PARAMETERS
  3. 5.1 DEMANDAD EXAMPLE
  4. 5.2 SUPPLYAD EXAMPLE
  5. 5.3 SIMULATION PARAMETERS

I would like to thank my advisor Dr. Yih-Fang Huang, whose expertise,
understanding, generous guidance and support made it possible for me to work
on a research topic that is of great interest to me. I am grateful for his
insightful and constructive suggestions on my research. After five-year
intensive PhD study with him, I have gained not only the abilities of critical
thinking and rigorous mathematical analysis, but also presentation and
communication skills, which will be invaluable treasures in my life.

I would like to thank Dr. Vijay Gupta, Dr. Ken Sauer, Dr. Hai Lin, and Dr.
Peter Bauer for being my PhD defense committee members. I really appreciate
their time and efforts to review my dissertation and provide meaningful
comments on how to improve it.

I would like to thank my parents and my sister for their continued love, help,
support and encouragement. I thank them for always being there and going
through the happiness and sorrow with me.

I would like to thank all my friends, colleagues, my roommate and many
visiting scholars for their genuine friendship and support. I would always
remember the crazy cheers and cadences in the football stadium, delicious
cuisine, interesting parties, funny Halloweens, etc.

I would also like to thank University of Notre Dame for providing such a
beautiful and divine campus for me. Wherever I go, and whatever happens in my
life I know I always have a home at Notre Dame to renew my heart and refresh
my spirit.

Ltotal number of candidate locations Ntotal number of EVs

$\psi_{j,k}^{n}$

charging demand

$s_{j,k}$

placement indicator

$F_{j,k}$

charging station setup cost

$R_{k}$

total revenue

$c_{j,k}$

locational marginal price

$\Pi_{k}$

total profit

$U_{k}$

overall utility

$w$

coefficient of EV charging penalty

$\Upsilon_{k}$

average service probability

$\Xi_{k}$

average service coverage

$t_{k}$

average charging time

$p_{k}$

retail charging price

$i_{n}$

income of the $n$th EV owner

$d_{j,k}^{n}$

deviating distance

$z_{j,k}^{n}$

indicator of destination

$d_{th}$

distance threshold

$r_{j,k}$

indicator of restaurant

$g_{j,k}$

indicator of shopcenter

$m_{j,k}$

indicator of supermarket

$\mathbf{P}_{\textrm{g}}^{\textrm{base}}$

active power vector without EV

$\mathbf{P}_{\textrm{g}}^{\textrm{EV}}$

active power vector with EV

$\mathbf{Q}_{\textrm{g}}^{\textrm{base}}$

reactive power vector without EV

$\mathbf{Q}_{\textrm{g}}^{\textrm{EV}}$

reactive power vector with EV

$v_{i}$

voltage at bus $i$

$\phi_{ik}$

voltage angle between bus $i$, $k$

$\alpha$

coefficient of $t_{k}$

$\beta$

coefficient of $p_{k}/i_{n}$

$\mu_{k}$

coefficient of $d_{j,k}$

$\eta_{k}$

coefficient of $z_{j,k}$

$\gamma_{k}$

coefficient of $r_{j,k}$

$\lambda_{k}$

coefficient of $g_{j,k}$

$\delta_{k}$

coefficient of $m_{j,k}$

$K$

Number of planning horizons

$s_{j}$

The $j$-th EV charging station

$p_{kj}$

Charging price of the $j$-th charging station at the $k$-th horizon

$c_{k}$

Real-time wholesale price at the $k$-th horizon

$E$

Electricity storage capacity

$I_{k}$

Remaining electricity at the beginning of $k$-th horizon

$W_{k}$

Profit of the $k$-th horizon

$W_{\textrm{min}}$

Threshold of minimum profit

$G_{k}$

Customer satisfaction at the $k$-th horizon

$F_{k}$

Impact at the $k$-th horizon

$o_{k}$

Electricity purchase at the $k$-th horizon

$u_{k}$

Renewable energy at the $k$-th horizon

$\eta_{s}$

Unit storage cost (in$/MWh)

$\eta_{c}$

Charging efficiency

$\eta_{d}$

Discharging efficiency

$\phi_{k}$

Total charging demand at $k$-th horizon

$\gamma_{i,j}$

Price elasticity coefficient

$P_{i}$

Active power of $i$-th bus

$Q_{i}$

Reactive power of $i$-th bus

$G_{ik}$

Conductance of $ik$-th element in admittance matrix

$B_{ik}$

Susceptance of $ik$-th element in admittance matrix

$S_{i}^{\textrm{Ac}}$

Active power sensitivity of $i$-th bus

$S_{i}^{\textrm{Re}}$

Reactive power sensitivity of $i$-th bus

$Q$

Requested electricity quantity

$\theta$

Power factor

$\theta^{\textrm{min}}$

Minimum power factor

$\theta^{\textrm{max}}$

Maximum power factor

$T^{\textrm{min}}$

Minimum delivery starting time

$T^{\textrm{max}}$

Maximum delivery starting time

$p^{\textrm{bid}}$

Bid price

$p^{\textrm{offer}}$

Offer price

$R$

Delivery rate (MW)

$R^{\textrm{min}}$

Minimum delivery rate

$R^{\textrm{max}}$

Maximum delivery rate

$S(i,j)$

Fitness score

$D_{i,j}$

Predicted electricity delivery cost

$Z(i,j)$

Same zone indicator

$E(j)$

Renewable energy indicator

$\mathcal{K}^{h}$

Active supply-demand pair set

$\mathcal{J}^{h}_{k}$

Route set

$\beta_{k,j,l}^{h}$

Power flow on branch (in MW)

$Q^{h}_{k}$

Scheduled power delivery rate (in MW)

$r_{l}$

Resistance of distribution line

$F^{\textrm{base}}_{l}$

Base power flow on branch (in MW)

$F^{\textrm{now}}_{l}$

Aggregated power flow on branch (in MW)

$M(i,j)$

Payment of $i$-th DemandAd to $j$-th SupplyAd

$C_{l}$

Branch capacity

##  Chapter 1 INTRODUCTION

###  1.1 Overview

This chapter provides a brief introduction to the EV ecosystem, which includes
EV and EV charging infrastructure, EV market and manufacturers, the
relationship between EV charging and power systems, as well as challenges that
the EV industry may face.

Figure 1.1: Energy Flow and Cash Flow in EV Ecosystem

###  1.2 EV Ecosystem

A complete EV ecosystem is illustrated in Fig. 1.1. Main entities like power
plants, independent system operator (ISO) or regional transmission
organization (RTO), EV charging infrastructure are included in this figure.
The energy flow (blue line) and the cash flow (green line) show the
interaction among different entities.

####  1.2.1 Power Plant

A power plant generates electricity by burning fossil fuels like coal or
natural gas, or by using clean and renewable sources like nuclear energy,
solar, or wind. A power plant can either sell the electricity to specific
consumers through bilateral contracts (or futures), or sell the electricity in
a wholesale market through auctions.

####  1.2.2 ISO/RTO

In the United States, ISO/RTO is an organization that coordinates, controls,
and monitors the power grid. For instance, California ISO (CAISO), Southwest
Power Pool (SPP), Midcontinent ISO (MISO) and PJM Interconnection are
ISO/RTOs.

ISO/RTO determines the day-ahead clearing price and the ancillary service
price through an auction between power plants and buyers. ISO/RTO also
operates the electricity real-time market, where the electricity price is
cleared in real-time and the power plants must deliver the committed
electricity immediately.

####  1.2.3 Reseller

The resellers are buyers in the auction in the wholesale market. The load
serving entity (LSE) and electricity marketers are typical resellers in the
market.

####  1.2.4 EV Charging Infrastructure

EV owners can either install an EV charging station at home or go to a public
charging station. So, EV charging infrastructure can be done at either private
or public infrastructures.

####  1.2.5 Electricity Transmission Network

Electricity transmission is the long distance delivery of bulk electricity
from power plants to substations, in which electricity is transferred using
the transmission lines with high-voltage (i.e. 69 kV, 115 kV and 138 kV). The
transmission lines are interconnected to form the transmission network.

####  1.2.6 Electricity Distribution Network

The electricity distribution network delivers electricity from the local
substations to end users using a relatively low voltage (i.e. 120/240 V in
North America, and 220, 230, or 240 V in Europe).

###  1.3 Emerging EV Market

As consumers are becoming more aware of the environmental impact of the
greenhouse gas emissions as well as promotions and incentives from local
governments, the demand for EVs has been growing over the past several years.
From 2008 to June 2015, about 345,000 highway plug-in electric vehicles were
sold in the United States, making it the largest plug-in EV market in the
world [1, 2]. The market share of plug-in EV of new registered cars in the US
increased from 0.14% to 0.37% in 2012 and 0.62% in 2013 and 0.72% in 2014 [3].
According to Navigant Research [4], the global light duty EV market is
expected to grow from 2.7 million vehicle sales in 2014 to 6.4 million in
2023.

Figure 1.2: PHEV Sales

In general, EVs can be classified into three main categories: Hybrid Electric
Vehicle (HEV), Plug-in Electric Hybrid Vehicle (PHEV), and Battery Electric
Vehicle (BEV) or All-Electric Vehicle (AEV).

####  1.3.1 Hybrid Electric Vehicle (HEV)

HEVs are primarily powered by the internal combustion engine (ICE) which uses
gasoline. Each HEV also has an electric motor that uses the electricity stored
in the battery. The battery gets recharged from the regenerative braking and
the internal combustion engine. However, the battery cannot be plugged into
the power system to get recharged. The electric powertrain helps HEVs achieve
better fuel economy and lower emission than the conventional ICE vehicles.
Many automakers have released their HEV-version cars like Honda Civic Hybrid,
Ford Fusion Hybrid, BMW ActiveHybrid 3, etc.

####  1.3.2 Plug-in Hybrid Electric Vehicle (PHEV)

PHEVs are powered by both the internal combustion engine (ICE) and the
electric motor. The ICE eliminates the “range anxiety” since PHEVs can switch
to the ICE when the battery is depleted. The battery can be plugged into the
power grid to get recharged. Usually, PHEVs have a larger battery pack than
the HEVs, which increases the “all-electric range”. Some representatives of
PHEVs include Ford Fusion Energi, Chevrolet Volt, Cadillac ELR, etc.

####  1.3.3 Battery Electric Vehicle/All Electric Vehicle (BEV/AEV)

BEVs or AEVs are solely powered by an electric motor which uses the
electricity from a battery. The battery gets recharged by plugging the vehicle
into the power grid. BEVs do not rely on fossil fuels and they generate zero
emissions. The representatives of BEVs are Fiat 500e, Nissan Leaf, Tesla Model
S, etc.

Fig. 1.2 shows the trend of EV market share based on the EV sales data from
Electric Drive Transportation Association (EDTA). Note that the plug-in EVs
(including PHEV and BEV) has a steady increase in market share from 2011 to
2014.

In this dissertation, we focus our attention on BEVs since there are more
challenges and problems associated with this type of EV, as compared to the
hybrids. In the subsequent discussions, we use EVs to refer BEVs.

Figure 1.3: EV Market Share

###  1.4 Benefits of EVs

In this section, we highlight some of the most prominent benefits of EV.

####  1.4.1 Economic Growth

Both individual EV owners and automobile manufacturers will benefit from a
vibrant EV industry and the resulting growth in the entire supply chain. Many
studies have shown that electricity is a cheaper fuel than gasoline to propel
the vehicles [5, 6, 7, 8, 9, 10]. In particular, [11] showed that the
equivalent cost of electricity as a gallon of gasoline is less than one
dollar. In addition, Navigant Research predicted that the global demand for
lithium ion batteries for the light duty fleet will increase from $3.2 billion
in 2013 to $24.1 billion in 2023. The global revenue from the electric vehicle
supply equipment (EVSE) is estimated to reach $5.8 billion in annual revenue
by 2022.

####  1.4.2 Environmental Sustainability

Massive adoption of EVs offers an opportunity to improve the air quality
through increasing fuel efficiency, reducing or terminating greenhouse gas
emissions [5, 12, 13, 14, 15, 16]. Fig. 1.4 illustrates that driving on
electricity offers a huge environmental benefit [17]. The electricity in the
US is generated from a diverse portfolio of energy sources from natural gas to
nuclear power, from hydroelectric to coal, from biomass to wind and solar.
More importantly, the portion of renewable energy generation (e.g. wind,
solar, and hydrodic) has increased over these years, which is a more desirable
source to recharge EVs. A lot of efforts have been made to enhance the
efficiency of electricity generation and distribution using smart grid
technologies to make EV charging even more convenient.

Figure 1.4: Comparison EV with ICE in Global Warming Emission

####  1.4.3 Energy Security

Relying on a single globally traded fuel, i.e. petroleum, is a potential
threat to energy security. According to the US Energy Information
Administration (EIA), soaring oil price has a negative impact on the US
macroeconomic variables. The growing gasoline cost and the painful spikes in
prices often have adverse impacts on family budget. EVs provide a viable
solution to propel our transportation sector and alleviate dependence on oil.
The diverse sources for electricity generation make electricity price remain
relatively stable, which offers some protection for the EV owners against the
volatile gasoline price.

###  1.5 State of the Art of EV Technology

The continuing evolution of EV technologies empowers EVs to compete with the
ICE vehicles in the competitive automobile market. In particular, recent
advances in powertrain, battery, propulsion motor, power converter, charging,
and hybrid control technology make EVs a viable substitute for the
conventional ICE vehicles. In this section, a brief summary to the state-of-
the-art EV technologies will be given.

####  1.5.1 Powertrain

Generally, the EVs can be classified into three categories: HEV, PHEV, and BEV
(all-electric vehicle). Both PHEVs and BEVs can be recharged by connecting the
battery to the power system, so they are also called plug-in electric vehicles
(PEVs). HEVs and PHEVs can be further divided into series HEVs and PHEVs,
parallel HEVs and PHEVs, and series-parallel HEVs and PHEVs according to
different configurations of the ICE and the electric motor (EM) [18, 19, 20].
Since a BEV does not have ICE so the EM provides the entire power for the
vehicle.

Series HEV and PHEV: In series HEV and PHEV, the ICE mechanical output is
first converted to electricity through a generator. After a power convertor,
the generated electricity can be utilized to recharge the battery or to power
the EM to propel the wheels. Another function of EM is to harvest the
regenerative energy during braking. The decoupling between the engine and the
driving wheel offers the advantage for HEV and PHEV design to place the
generator set. However, series HEV and PHEV powertrain need three propulsion
components: the ICE, the generator, and the EM, resulting in a lower energy
efficiency.

Figure 1.5: Powertrain: Series HEV and PHEV

Parallel HEV and PHEV: In contrast to series HEV and PHEV, parallel HEV and
PHEV allow both ICE and EM to propel wheels in parallel. The ICE and EM are
both coupled to the drive shaft of the wheels via two clutches. Similar to the
series type, the EM can be used to harvest electricity during braking to
recharge the battery or absorb the extra power produced by ICE. Compared with
the series hybrid, the parallel HEV and PHEV need only two propulsion
components—ICE and EM. Since ICE and EM can propel the wheel simultaneously,
the parallel type can have a smaller ICE and EM than the series type to
achieve the same performance.

Figure 1.6: Powertrain: Parallel HEV and PHEV

Series-Parallel HEV and PHEV: Series-parallel HEV and PHEV combine the
advantages of both series hybrid type and parallel hybrid type. However, the
series-parallel type is more complicated and expensive than either the series
type or the parallel type. As the control and manufacturing technologies
mature, many automobile manufacturers prefer to adopt this type of design.

Figure 1.7: Powertrain: Series-Parallel HEV and PHEV

BEV: The BEVs do not have the ICE and battery is the sole energy source to
propel the vehicle. The propulsion system is relatively simple compared to HEV
and PHEV because there is no coupling between the ICE and EM. However, BEVs
have the “range anxiety” problem, since they are without the ICE as the backup
energy source.

Figure 1.8: Powertrain: BEV

####  1.5.2 Battery

Battery is the only energy source for BEVs and one of two major energy sources
for HEV and PHEV. It is always a challenging task for designers to find an
appropriate battery for EVs with the desirable characteristics, such as high
capacity, low cost, light weight, fast charging, safe operation, durability,
long lifetime, and resistance to severe weather conditions. The limited
battery capacity is one of the major concerns for potential EV consumers. The
long charging time is another hinderance that discourages consumers to
purchase EVs. Furthermore, the high cost of battery makes EVs more expensive
than the ICE vehicles, which again places EVs in an unfavorable situation in
the automobile market.

However, the EV battery research has made remarkable progresses in the past
decades [19, 21, 22]. Currently, various novel technologies are employed to
refine the battery manufacturing process and many superior battery prototypes
are under development in the labs [23]. In this subsection, we will briefly
discuss the development of EV batteries and present several battery types that
were used in the past or are used currently.

Lead-Acid Battery: The first battery used in transportation is the lead-acid
battery. The lead-acid battery technology is mature and inexpensive but it has
many disadvantages, such as low capacity, heavy, and environmental pollution.

Nickel-Based Battery: The lead-acid battery was soon replaced by the nickel-
based battery, i.e., nickel-cadmium (NiCd) and nickel-metal-hydride (NiMH).
The nickel-based battery has several advantages over the lead-acid battery,
such as high cycle count, good load performance, simple storage and
transportation, and good low-temperature performance. However, the nickel-
based battery has some serious disadvantages like relatively low energy
density, memory effect, toxic metal, and high self-discharge rate.

ZEBRA Battery: ZEBRA battery utilizes the molten sodium aluminumchloride
($\textrm{NaAlCl}_{4}$ ) as the electrolyte. The negative electrode is the
molten sodium and the positive electrode is the nickel in the discharged state
and nickel chloride in the charged state. The operation temperature for ZEBRA
battery is 245 $\textrm{C}^{\circ}$ (473 $\textrm{F}^{\circ}$). ZEBRA battery
has the advantages of high energy density (5 times higher than lead acid
battery), large cell, long life cycle, and low material cost. However, this
battery type suffers from high internal resistance and high operating
temperature, which requires delicate internal thermal management.

Lithium-Based Battery: The advent of lithium-based battery gives new life to
the EV industry. There are several battery types belonging to the lithium-
based battery family—lithium-ion (Li-ion), lithium-ion polymer (LiPo), and
lithium-iron phosphate ($\textrm{LiFePO}_{4}$). The lithium-based battery has
the advantages of high energy density, low self-discharge rate, low
maintenance, light, cheap, environmentally friendly, and fast charging. The
limitations of this battery is that the internal resistance is relatively
high. Thus high thermal runaway may lead to fire. It also requires
sophisticated battery management circuit. The current EVs that are equipped
with lithium-based battery include Nissan Leaf, Mitsubishi i-MiEV, Tesla Model
S and Chevrolet Volt.

Emerging Battery Technologies: Many other battery technologies are still in
the experimental stage, e.g., metal phase, which gives superior performance.
Those batteries are lithium-sulfur (Li-S), zinc-air (Zn-air) and lithium-air
(Li-air). Those batteries offer excellent performance and will extend the all
electric range and reduce the manufacturing cost of EVs.

###  1.6 Challenges of Large-Scale EV Integration

EVs exhibit many advantages over ICE vehicles, like higher fuel efficiency,
lower operating cost, and zero greenhouse gas emissions. Nevertheless, many
challenges remain as major obstacles for EV proliferation. In this section, we
briefly discuss some of those challenges.

####  1.6.1 Large-Scale EV Charging Scheduling

Uncontrolled large-scale EV charging will undoubtedly place a heavy burden on
the existing power system legacy. Researchers have done much to investigate
the problem of optimal scheduling of EV charging by using historical data [8,
24], static time of usage based costs [25, 26, 27], power load prediction
[28], particle swarm optimization [29], and non-cooperative games [30].

####  1.6.2 Limited Battery Capacity and Long Charging Time

The onboard battery capacity is the bottleneck to increase the range for all-
electric EVs. For instance, Nissan LEAF has a 24 kWh battery, which only
provides a driving range of 84 miles. Chevrolet Spark EV has a 19 kWh battery
with a driving range of 82 miles. Tesla Model S has a larger battery pack with
a capacity of 70kWh, offering a 230 miles range. Moreover, it often takes up
to several hours to fully charge the battery. Obviously, the long charging
time is a severe drawback for EV compared to the ICE vehicles, which can be
fully refuelled in only a few minutes.

####  1.6.3 Insufficient EV Public Charging Infrastructure

The scarcity of public charging stations is another major concern to potential
EV consumers. Currently, most EV charging is done at the residence. The EV
owners find it inconvenient to go to the commercial charging stations either
because there are not enough charging stations available or those charging
stations are not deployed in locations that can be accessed easily. In this
dissertation, we propose an EV charging station placement strategy, which
provides guidelines on determining how many charging stations we need and when
and where to deploy them.

####  1.6.4 Charging Station Operation and Management

The effective management of EV charging infrastructure is crucial to EV
ecosystem. Currently, there is no proper model available for charging station
operation in terms of charging price setting, and energy management strategy.
A proper model should take into account the profitability of charging
stations, consumer satisfaction, and power system stability.

####  1.6.5 Liberal Electricity Trading Market and Distribution Network

The current wholesale electricity market is not conductive for the interplay
between EVs and RESs. In addition, the current electricity distribution
network cannot naturally support intermittent renewable energy generation. We
need to redesign the electricity trading market and distribution network to
facilitate large-scale EV and RES integration.

In essence, this dissertation addresses some of those challenges that include
public charging infrastructure, charging station operation and management, and
electricity trading market and distribution network.

###  1.7 Dissertation Organization

This dissertation is organized as follows: Chapter 2 discusses the interaction
between EV charging and the power system. An optimal EV charging station
placement strategy is studied in Chapter 3. In Chapter 4, a dynamic pricing
and electricity management model is proposed for EV charging service
providers. In Chapter 5, we present the design of a novel electricity trading
market and distribution network for EVs and RESs. Conclusion and future work
are presented in Chapter 6.

##  Chapter 2 INTERPLAY BETWEEN EV CHARGING AND THE POWER SYSTEM

###  2.1 Overview

This chapter presents an overview on the EV charging system including existing
charging standards, electric vehicle supply equipment (EVSE), and onboard
charger. In addition, the mutual interaction between EV charging and the power
system will be discussed and some relevant technologies like vehicle to grid
(V2G) and grid-to-vehicle (G2V) will also be considered.

###  2.2 EV Charging System

An EV charging system includes a suite of software and hardware. Many
countries have released their own EV charging standards. Accordingly, EV
charging equipment manufacturers produce different charging connectors.

####  2.2.1 EV Charging Standard

Currently, there are several popular standards for EV charging. In North
America, the Society of Automotive Engineers (SAE) has released the standard
of electrical connectors for electric vehicles — SAE J1772, with a formal
title of “SAE Surface Vehicle Recommended Practice J1772 (SAE J1772), SAE
Electric Vehicle Conductive Charge Coupler”. In Japan, CHAdeMO Association,
formed by the Tokyo Electric Power Company, Nissan, Mitsubishi, Fuji Heavy
Industries, and Toyota, has released the CHAdeMO standards for DC fast
charging [31]. In Europe, German Association of the Automotive Industry (VDA)
has released the standard of VDE-AR-E 2623-2-2 [32].

SAE J1772 Standard: SAE J1772 [33] specifies three charging levels with
different voltages and currents.

Table 2.1: CHARGE METHOD ELECTRICAL RATINGS (NORTH AMERICA) Level |  Voltage(V) |  Current (A) |  Charging Time (hour)
---|---|---|---
Level 1 |  120 |  12 |  16-18
Level 2 |  208 to 240 |  32 |  3-8
Level 3 |  600 max |  400 max |  $<$0.5

Level 1 Charging: Level 1 Charging is operated at 120 volts with single phase
alternating current (AC). It may take 16-18 hours to charge an EV. Level 1
Charging usually takes place at home and all EVs come with the Level 1
Charging cord.

Level 2 Charging: Level 2 Charging is operated at the voltage ranging from 208
volts to 240 volts with single phase AC. It may take 3-8 hours to fully charge
the battery pack. Level 2 Charging is apt for overnight or long-length
charging and is the preferred charging method for both public and private
facilities. They are typically found in shopping malls, parking lots, and
commercial buildings. They can also be charged at residential homes.

Level 3 Charging : Level 3 Charging uses direct current (DC) with a maximum
voltage of 600 volts. It takes less than 30 minutes to charge most of battery
packs to 80% full. The time to full charge is not too much more than what it
takes to fill the gas tank at a gas station. However, the equipment can be
quite expensive.

CHAdeMO Standard: To regulate the DC fast charging, CHAdeMO Association
introduced the CHAdeMO standard. According to CHAdeMO standard, DC fast
charging should recharge the battery pack to at least 80% in half an hour
using the optimal DC charger of 50 kW. DC fast charging is performed through
an external dedicated EV charging equipment, usually located in public areas
(like parking lot, shopping mall, etc.) CHAdeMO standard has been the Japanese
national standard since 2012.

VDE-AR-E 2623-2-2 Standard: Originally proposed by Mennekes Elektrotechnik
GmbH & Co. KG in 2009 and later standardized by VDA in 2011, the VDE-AR-E
2623-2-2 EV charging connector has been widely used in Europe. VDA recommends
that accessories and interfaces between the power supply and the EVs that
permit ‘fuelling’ at 20, 32, 63 amps (single and three-phase current) and at
70 amps (single-phase current only) with a maximum operating voltage of 500
volts at 50-60 Hz. This range will cover the entire range of power supply
range worldwide.

Tesla Charging Standard: Tesla mobile charging unit comes with adapters
allowing for every type of power outlets, from ordinary 120 volt 12 amp (NEMA
5-20) and 240 volt 50 amp (NEMA 14-50) to SAE J1772 connectors and CHAdeMO
connectors. In addition, Tesla Motors is building up its own Supercharger
network which provides DC fast charging service for Tesla vehicles.

####  2.2.2 Electric Vehicle Supply Equipment

The electric vehicle supply equipment (EVSE) is a charging meter which draws
electricity from the power system and feeds it to the onboard battery pack
through a charging coupler. An EVSE can be installed either at home or in
public. A public charging station typically has multiple EVSEs. Currently,
there are several EVSE manufacturers, like ChargePoint, Blink, AeroVironment,
etc.

####  2.2.3 EV Charging Coupler and Plug Receptacle

An EV charging coupler is like a gas pump nozzle which connects the EVSE and
the EV plug receptacle. In the U.S., most EVSEs and EVs are equipped with a
standard charging coupler and receptacle based on the SAE J1772 standard. Any
vehicle with a standard plug receptacle is able to use any J1772-compliant AC
Level 1 or AC Level 2 EVSE.

As for DC fast Charging, CHAdeMO [31] is a widely used standard among EVs
manufactured by Japanese automakers, such as Nissan Leaf and Mitsubishi
vehicles. The Chevy Spark and the BMW i3 come with the SAE J1772 combined
charging system (CCS), which uses a single receptacle for AC Level 1, AC Level
2, and DC Level 3. Additionally, Tesla Motor operates its own supercharger
network, which is based on their own connector and currently only charges
Tesla vehicles.

###  2.3 EV Charging, Power System, and Electricity Market

This subsection discusses the interplay among EV charging, the power system,
and the electricity market.

####  2.3.1 Power System and Control

Although power system varies in size and structural components, they all share
the following basic characteristics:

  * •

Consist of three phase AC system operating at a constant voltage. Generation
and transmission facilities use three phase equipments. Industrial loads are
usually three phase; single phase residential and commercial loads are
distributed evenly across the phase to effectively balance the three phases.

  * •

The power generators are synchronized to produce electricity using various
kinds of energy sources, such as fossil fuels, solar, wind, nuclear, etc.

  * •

Transfer electricity to consumers across a wide area. This requires a complex
transmission and distribution system comprising of many subsystems operating
at different voltages.

Fig. 2.1 shows the basic elements of a power system [34]. Electricity is
generated by the generation station (GS) and delivered to the end users
through a complicated network of individual components, transmission lines,
substations, feeders, etc.

Figure 2.1: Basic Elements of a Power System

In general, the electricity transmission network consists of three subsystems:
transmission system, subtransmission system, and distribution system.

Transmission System: It interconnects all major power plants and main load
centers. It forms the backbone of the entire power system. It operates at the
highest voltage levels (typically, above 230 kV). The voltage generated by the
generators is usually in the range of 11 to 35 kV, which needs to be raised up
to the transmission level voltage, say, 230 kV. When the electricity is
delivered to the transmission substations, the voltage is stepped down to
match the subtransmission levels (typically, 69 to 138 kV).

Subtransmission System: It delivers the electricity in smaller quantities from
transmission substations to distribution substations. Large industrial
customers are typically supplied directly by the subtransmisison system. In
modern electric power system, there is not a clear delimitation between a
transmission system and a subtransmission system.

Distribution System: It is responsible for delivering electricity to the end
customers. Distribution voltages are typically in the rage of 4 to 34.5 kV.
Small industrial customers are supplied by the primary feeders at this voltage
level. The secondary distribution feeders supply residential or commercial
customers at 120/240 V voltage level.

The most important task of an electric power system is to deliver electricity
from the power generators to the end customers in a reliable and efficient
manner. Power quality is one of the major issues which must be concerned with.
Power quality can be described by a set of parameters, such as continuity of
service, voltage variation, transient voltage or current, and harmonics. The
power system has different levels of controllers that are intended for
frequency control, voltage control, and reliability control. Basically, there
are three groups of controllers in a power system: generating unit control,
system generation control, and transmission control.

Generating Unit Control: It mainly controls the input and output of a
generator, which consists of the prime mover controller and the excitation
controller. The prime mover controller is concerned with the speed regulation
and control of energy supply system variables such as boiler pressure,
temperature, and flow. The function of the excitation controller is to
regulate the output voltage and reactive power.

System Generation Control: It is responsible for coordinating the system
generation and the system load and losses so that the desired frequency and
power exchange with adjacent systems are maintained.

Transmission Control: It has a myriad of power and voltage control devices,
like static var compensators, synchronous condensers, capacitors and reactors,
transformers, and HVDC transmission controls.

####  2.3.2 ISO/RTO and Electricity Market

In a deregulated electricity market, ISO/RTO is a nonprofit organization which
is responsible for integrating a diverse mix of power resources into the power
grid and coordinating generation and consumption. As a fair power grid
operator, ISO/RTO has no financial interest in any market segment and
different resources have an equal access to the transmission network. There
are 9 ISO/RTOs in North America—California ISO (CAISO), Alberta Electric
System Operator (AESO), Independent Electricity System Operator (IESO),
Midcontinent ISO (MISO), Southwest Power Pool (SPP), Electric Reliability
Council of Texas (ERCOT), ISO New England, New York ISO, and PJM
Interconnection.

An ISO/RTO has a full model of the generation and transmission schedules to
manage and avoid real-time congestions. An ISO/RTO also provides an integrated
forward market (IFM) for trading and analyzing the electricity bids,
transmission, capacity, and reserves needed to maintain grid stability.
Additionally, the locational marginal price (LMP) is calculated by the ISO/RTO
based on the cost of electricity generation and delivery.

Compared to regulated electricity markets, the presence of ISO/RTO has a few
benefits:

Enhanced Reliability: Since ISO/RTO is in charge of a large geographic area,
and the market reliability can be improved through resource sharing, that
allows excessive electricity in a local area to be transmitted to neighboring
areas via an open market. The use of advanced technology and market-driven
incentives improves the performance of power plants. Power plants tend to have
lower outage rates in the unregulated market than in the monopoly market,
because power plants have the motivations to keep the generators on line,
especially during peak hours, to maximize their revenues.

Price Transparency: The LMP mechanism creates a highly transparent system that
calculates the prices based on the cost of electricity generation and
delivery. In a monopoly market, customers and investors face the “black box”
pertaining to the information of prices and the locational cost of
transmission, which inhibits investments in the grid.

Green Resources Integration: ISO/RTO offers a fair platform for diverse
electricity resources to compete with each other, bringing the cheapest
electricity to customers. This non-discriminatory access to power grid opens
doors for the low cost renewable energy.

Market Monitoring: ISO/RTO plays a significant role in monitoring the
electricity market. ISO/RTO calculates the LMP which truly reflects the supply
and demand relationship. In addition, ISO/RTO can identify ineffective market
rules and tariff provisions, identify potential anticompetitive market
behaviors by participants and offer comprehensive market analysis to help in
informed decisions.

Market Flexibility and Diversity: The organized markets offer various
electricity products and financial instruments which can be used to hedge
price risks. Because average real-time energy prices are correlated to short-
term forward bilateral prices, ISO and RTO markets foster forward contracting
to stabilize prices. There are usually numerous sellers and buyers in the
electricity wholesale market. Any entity can participate in the market if they
satisfy the basic requirements.

Demand Response: The ISO/RTO has access to power grid operation data,
electricity usage data, generation and demand data. Facilitated by these data,
the ISO/RTO can make informed decisions on pricing or set other rules to alter
customer’s usage behavior and shape the demand profile to optimize the grid.

As a core optimization algorithm used by ISO/RTO, Security Constrained Unit
Commitment (SCUC) algorithm aims to determine the unit commitment (UC) and
economic energy dispatch by taking into account the supply/demand bids, the
ancillary service requirement, the transmission congestion and power balance.
SCUC algorithm is used in the day-ahead market and the real-time market. SCUC
algorithm employs Mixed Integer Programming (MIP) to effectively solve the
optimization problem with various model requirements and constraints. The
objective of SCUC algorithm is to minimize the overall cost of energy
generation and ancillary services.

$\displaystyle\min\sum_{h=1}^{T}\sum_{i=1}^{N}$
$\displaystyle\biggl{[}SUC_{i}(1-U_{i,h-1})U_{i,h}+MLC_{i,h}U_{i,h}+\int_{P_{\textrm{min},i}}^{P_{i,h}}C_{i,h}\left(P_{i,h}\right)dP$
(2.1) $\displaystyle+C_{i,h}^{\textrm{RU}}\cdot
RU_{i,h}+C_{i,h}^{\textrm{RD}}\cdot RD_{i,h}+C_{i,h}^{\textrm{SP}}\cdot
SP_{i,h}+C_{i,h}^{\textrm{NS}}\cdot NS_{i,h}\biggl{]},$

where

$h$: Hour index

$T$: Total number of hours

$i$: Resource index

$N$: Total number of resources

$P_{i,h}$: Power output of resource $i$ in hour $h$

$RU_{i,h}$: Regulation up provided by resource $i$ in hour $h$

$RD_{i,h}$: Regulation down provided by resource $i$ in hour $h$

$SP_{i,h}$: Spinning reserve provided by resource $i$ in hour $h$

$NS_{i,h}$: Nonspinning reserve provided by resource $i$ in hour $h$

$C_{i,h}(P_{i,h})$: Cost ($/hour) as a piece-wise linear function of output
(MW) for resource $i$ in hour $h$

$C_{i,h}^{\textrm{RU}}$: Bid cost ($/MW) of regulation up (MW) for resource
$i$ in hour $h$

$C_{i,h}^{\textrm{RD}}$: Bid cost ($/MW) of regulation down (MW) for resource
$i$ in hour $h$

$C_{i,h}^{\textrm{SP}}$: Bid cost ($/MW)of spinning reserve (MW) for resource
$i$ in hour $h$

$C_{i,h}^{\textrm{NS}}$: Bid cost ($/MW) of non-spinning reserve (MW) for
resource $i$ in hour $h$

$SUC_{i}$: Start-Up Cost ($/start) for resource $i$

$MLC_{i,h}$: Minimum Load Cost ($/hour) for resource $i$ in hour $h$

$U_{i,h}$: Commitment status — 0 if resource $i$ is off-line, and 1 if
resource $i$ is online, in hour $h$

The constraints considered in SCUC encompass the power balance constraint, the
ancillary service constraint, the transmission network constraint, and the
inter-temporal constraint.

All ISO/RTOs have similar operation procedures to clear day-ahead market. In
this section, we use CAISO as an example to demonstrate how the day-ahead
wholesale market operates under the coordination of an ISO/RTO. Through three
progressive stages (market power mitigation, integrated forward market,
residual unit commitment), CAISO receives buy bids and sell offers, guarantees
that the supply meets the demand, clears the prices and settles the
transactions.

Market Power Mitigation (MPM): The ISO/RTO market aims to encourage
competitive and efficient electricity consumption by ensuring that power
generation offers are consistent with their marginal cost and the use of least
costly centralized dispatch. The scheme of MPM are designed to ensure that the
power generators are able to bid on their marginal costs, but not able to
exercise market power. Market power is the ability of a provider to profitably
raise the market price of a good or a service. End customers may suffer from
electricity price rises if the power generators can exercise their market
power to manipulate market prices.

Basically, there are two approaches to market power mitigation—“structural”
approach and “conduct and impact” approach [35]. CAISO adopts the structural
approach. For structural approach, generator offers are subject to mitigation
if certain conditions are met. CAISO uses a formula to determine whether a
given transmission constraint is structurally competitive or non-competitive.
If the three largest resources available are jointly necessary to meet a given
constraint relief demand, these three resources fail the test. Resources that
fail the test in CAISO are mitigated to their reference level offers, which
consist of a marginal cost estimate plus a ten percent adder. These rules are
able to force the power generators to offer their bids close the short-term
marginal cost to avoid being mitigated.

The internal monitor of CAISO will calculate the reference levels for
incremental electricity offers, which are marginal cost plus a 10% adder.
Reference level calculation is based on many factors that include fuel prices
and heat rates, a resource’s lowest previous offers, lowest previous prices at
a resource’s node, and opportunity cost.

Integrated Forward Market (IFM): In an IFM, ISO/RTO analyzes the energy and
ancillary services market to calculate the transmission capacity needed
(congestion management) and confirm the reserves to balance the supply and
demand according to supply and demand bids. It guarantees that the generation
plus imports equals to the load plus exports plus transmission losses. The
ISO/RTO employs the LMP mechanism to calculate the market prices based on
bids/offers submitted by buyers and sellers.

Locational Marginal Price (LMP): It is a mechanism to manage transmission
congestion using market-based prices. LMP differs from place to place if
transmission congestion occurs. Transmission congestion prevents the
electricity of low-cost generators from satisfying all the loads and clearing
the market. As a result, the low-cost generators have to ramp down to avoid
transmission congestion. In essence, LMP is the marginal cost of supplying, at
the least cost, the next increment of power demand at a specific location
(node) in the power system, taking into account both the supply (generation or
import) bids and the demand (load or export) offers and the physical
characteristics of the transmission system and other operation constraints
[36]. Sometimes LMP is also called the “node price”.

The calculation of LMP is based on basic economic theory and power operation
practice. The ISO/RTO determines the LMP at each node by maximizing the total
social surplus under the transmission constraints and power losses. The total
social surplus consists of the supplier surplus and the consumer surplus.

The supply curve in Fig. 2.2 represents the marginal cost of supply. The
y-axis $P(Q^{*})$ corresponds to the minimum price-per-unit that the supplier
hopes to be paid to produce the next increment $Q$ at the point of $Q^{*}$.
The area under the curve up to $Q^{*}$ is the total cost ($\$/h$) of producing
the quantity $Q^{*}$. In addition, the supply curve is monotone increasing. If
the total quantity of $Q^{*}$ is priced at $P(Q^{*})$, the green area shown in
Fig. 2.2 is the supplier surplus. The total revenue for selling $Q^{*}$
quantity is at least $P(Q^{*})\times Q^{*}$ since the price can be greater
than $P(Q^{*})$. Suppose the total revenue is $P(Q^{*})\times Q^{*}$, then the
supplier surplus (area of upper triangle) equals to total revenue minus the
total cost to supply (area of lower triangle).

The demand curve in Fig. 2.3 represents the marginal benefit of demand. The
y-aix $P(Q^{*})$ corresponds to the price-benefit-per unit the consumer is
willing to pay to consume the next increment of $Q$ at point $Q^{*}$. The area
under the curve up to $Q^{*}$ is the total benefits ($\$/h$) to consume
quantity $Q^{*}$. Also, the demand curve is monotone decreasing. If the total
quantity of $Q^{*}$ is priced at $P(Q^{*})$, the solid area shown is the
customer surplus and represents the extra benefit the consumer acquires to
consume the quantity $Q^{*}$. The total payment for $Q^{*}$ is $P(Q^{*})\times
Q^{*}$ or less. Suppose the total payment is $P(Q^{*})\times Q^{*}$, which is
the area of the bottom square. The consumer surplus (area of upper triangle) =
the total benefits (upper triangle + bottom square) minus total payment (the
bottom square).

The total social surplus is the sum of the supplier surplus and the consumer
surplus. As is shown in Fig. 2.4, the intersection of the demand curve and
supply curve gives us the marginal clearing price, and the total social
surplus is maximized under the condition that total supply equals total
demand.

Figure 2.2: Supplier Surplus

Figure 2.3: Customer Surplus

Figure 2.4: Social Surplus

The ISO/RTO follows the same economic theory to calculate LMP, except that the
transmission constraints, power grid operation practices, and transmission
losses make the calculation more sophisticated. In this case, the incremental
generator supply bids become the supply curve, and the decremental demand bids
become the demand curve. LMP calculation is much more complex than the simple
supply-demand curve relationship due to all transmission and other operation
constraints. The transmission constraints and losses prevent the lowest-cost
electricity from being delivered to all nodes, leading to LMP varying from
location to location.

Residual Unit Commitment (RUC): In the integrated forward market, the ISO/RTO
clears the prices and volumes by maximizing the total social surplus. If the
clearing volume does not meet the forecast demand, the ISO/RTO needs to
procure additional capacity from other markets to be available in real-time
using the residual unit commitment process. This process ensures that there
are enough capacity online to meet the forecast demand. All generators
committed to residual unit commitment must be available online and submit an
energy bit in the real-time market. The Resource Adequacy (RA) program
developed by CAISO guarantees that load serving entities have at least 115% of
the peak-hour demand available as capacity.

The real-time market opens when the results of the day-ahead market are
published, and closes 75 minutes prior the trading hour. The real-time market
consists of several processes: (1) the market power mitigation process; (2)
the hour-ahead scheduling process; (3) real-time unit commitment (RTUC); (4)
the fifteen-minute market; (5) the real-time dispatch (RTD).

Market Power Mitigation (MPM): Similar to MPM in day-ahead market, the real-
time market employs MPM to create a valid bid-pool for real-time market
optimization. MPM runs every 15 minutes and the determination of MPM is based
on the non-competitive congestion test.

Hour-Ahead Scheduling Process (HASP): HASP is a special run of the real-time
unit commitment process. HASP produces (1) advisory schedules for internal
pricing nodes and intertie resources that do not have hourly block
schedules/bids; (2) final schedules for intertie resources with hourly block
bids for energy and ancillary services. HSAP is run once every hour.

Real-Time Unit Commitment Process (RTUC): RTUC is a continuous process running
at an interval of 15 minutes. This process (1) produces bind and advisory
fifteen-minute market (FMM) awards; (2) issues start-up instructions for fast
start and short start resources; (3) issues shut-down instructions for
resources that are not used in the grid; (4) produces transition decisions for
multi-stage generation resources.

Fifteen Minute Market (FMM): FMM runs every 15 minutes. This process is
responsible for (1) determining financially binding FMM schedules and
corresponding LMPs for all Pricing Nodes, including all Scheduling Points; (2)
determining financially and operationally binding Ancillary Services Awards
and corresponding ASMPs procure required additional Ancillary Services and
calculating ASMP; (3) determining LAP LMPs.

Real-Time Dispatch (RTD): RTD uses a Security Constrained Economic Dispatch
(SCED) algorithm every 5 minutes throughout the trading hour to determine the
optimal dispatch instructions to balance supply and demand. RTD can operate in
three modes: RTED (real-time economic dispatch), RTCD (real-time contingency
dispatch) and RTMD (real-time manual dispatch).

####  2.3.3 Interplay between EV Charging and Power System

In this section, we consider the interaction between EV charging and the power
system. In particular, we discuss the impact of EV charging on the power
system. Additionally, we will investigate how EVs can be used as mobile energy
storage to inject electricity into power grid via the emerging V2G technology.

Grid-to-Vehicle (G2V): Challenge and Opportunity of Power Grid: The principal
task of the power grid is to deliver economical and reliable electricity to
end customers. Nevertheless, many studies have shown that simultaneous large-
scale EV charging can disrupt the normal operation of the existing power
system with respect to frequency variation, voltage imbalance, and severe
power loss [37, 38, 39]. In regards to power supply, [6, 13, 8, 12, 14, 40]
have shown that the existing power generators can support up to 30% to 40% PEV
penetration rate without increasing generation capacity if the EV charging is
optimally scheduled. Additionally, large-scale EV charging can also overload
the distribution network [41, 42, 43, 44, 45, 46, 47]. [48, 49] have
demonstrated that high EV charging demand causes temperature increase and the
AD-DC conversion of EV can lead to harmonic distortion, which will shorten the
life span of upstream components like transformers and cables.

Generally, voltage and frequency are considered as the major variables to
assess the power quality. The frequency of a generator is calculated using the
following formula.

$f=\frac{PN}{60},$ (2.2)

where $P$ is the number of stator pole pairs in the rotor, $N$ is the
rotational speed of the rotor in rpm (revolutions per minute).

To maintain a constant frequency, the consumption and generation of active
power should always be balanced. For instance, if the consumption exceeds the
generation at any time, then the extra power is supplied by the rotational
inertia of the generator by decreasing the speed, which results in the
downward drift of frequency [50].

Literature abounds in addressing EV charging scheduling. In [51, 52, 53, 54,
55], the authors have proposed different frameworks to coordinate EV charging
to ensure stable and economical operation of the power grid. To protect the
distribution network from overloading, various strategies have been proposed,
e.g., demand response [56], time of use meters, and resource scheduling
algorithms [41, 57, 58].

In addition, the EV charging service provider can benefit from the burgeoning
EV charging market. As the EV charging market rises, the EV charging stations
are expected to gradually take over the market from the conventional gas
stations. The charging service provider can make a good deal of profit by
providing charging service to EVs. According to Navigant Research, global
revenue from EVSE charging services will grow from $81.1 million in 2014 to
$2.9 billion by 2023.

Vehicle-to-Grid (V2G): Challenge and Opportunity of Power Grid: In addition to
drawing electricity from the power system, EVs can also inject electricity
into the system through a bidirectional power flow channel. Various studies
[59, 13, 60, 61, 62, 63, 64, 65] have shown that the battery packs on EVs can
be utilized as mobile energy storage, which inject electricity into the power
system to provide ancillary services, like frequency regulation, spinning
reserve, voltage control, reactive power compensation, etc. EV owners receive
payments from the power aggregators by selling electricity to the power
system, therefore, reducing the overall operation cost of EVs [66, 67, 68, 69,
70]. Studies [71, 72, 73, 37, 74] have explored how to employ EVs to mitigate
the power fluctuation arising from intermittent renewable energy generation.
[75] have conducted a survey on customers’ willingness to pay for V2G, and
their findings suggest that the V2G concept is more inclined to be accepted if
the power aggregators offer either pay-as-you-go service or advanced cash
payment. The V2G communication protocols were developed and tested in report
[76]. Additionally, the V2G concept has been implemented and validated using
hardware and software simulator in [74, 77, 78, 79, 80]. Centralized and
decentralized V2G mechanisms have been implemented at University of Delaware
[77]. A testbed of V2G for frequency regulation and energy storage in PJM
system has been developed in [78].

Figure 2.5: Vehicle to Grid Mechanism

Although the electricity from EV battery packs is more costly than that from
power plants (e.g., $ 0.30/kWh versus $ 0.05/kWh), it is still a compelling
alternative to provide ancillary services because the price of power in
ancillary consists of two parts—capacity price and energy price. If an EV is
committed to provide ancillary services, the payment includes a capital price
for being available to quickly respond to power grid signals, and an energy
price for the actual energy output. Basically, the V2G exhibits several
advantages over the power plants in providing ancillary services: (1) the
capital cost of generation or storage equipment for V2G is low, (2) V2G can
respond quickly, and (3) V2G has the ability to operate in the V2G mode
without serious maintenance penalties.

While V2G has the aforementioned advantages, it has two main limitations,
namely, battery degradation and DC/AC power conversion loss. Note that
frequent charging and discharging will reduce the battery’s life span.
Therefore, battery degradation cost is an important factor that cannot be
neglected in V2G. [59] presents a formula to assess battery degradation cost.

$c_{\textrm{d}}=\frac{c_{\textrm{bat}}}{L_{\textrm{ET}}}=\frac{E_{\textrm{s}}c_{\textrm{b}}+c_{1}t_{1}}{L_{\textrm{C}}E_{\textrm{s}}\textrm{DoD}},$
(2.3)

where $c_{\textrm{bat}}$ is the battery replacement cost in US dollars
(capital and labor costs), $L_{\textrm{ET}}$ is the the battery lifetime
energy throughput for a particular cycling regime in kWh, $E_{\textrm{s}}$ is
the battery capacity in kWh, $c_{\textrm{b}}$ is the cost of battery
replacement in in US$/kWh, $c_{1}$ is the cost of labor in US$/h, $t_{1}$ is
the labor time for battery replacement, $L_{\textrm{C}}$ is the battery
lifetime in cycles, and DoD is the maximum discharge rate of battery, usually
usually 80% for NiMH and 100% for Li-Ion batteries.

Additionally, there are several challenges to implement V2G, such as the
coordination between EVs and power grid, pricing, hardware, power quality
assurance, etc. In summary, while V2G may seem like a viable alternative
energy source for power generation, its realization may still be quite some
time away.

##  Chapter 3 PLACEMENT OF EV CHARGING STATIONS — BALANCING THE BENEFITS AMONG
MULTIPLE ENTITIES

###  3.1 Overview

In a study of placement of electric vehicle (EV) charging stations, this
section proposes a multi-stage placement policy with incremental EV
penetration rates. A nested logit model will be employed to analyze the
charging preference of the individual consumer (EV owner), and predict the
aggregated charging demand at the charging stations. The EV charging industry
is assumed to be an oligopoly where the entire market is dominated by several
charging service providers (oligopolists). We plan to use the Bayesian game to
model the strategic interactions among the service providers and derive the
optimal placement policy at the beginning of each planning stage. To derive
the optimal placement policy, we consider both the transportation network
graph and electric power network graph. In addition, we also propose to
develop a simulation software—EV Virtual City 1.0 using Java to investigate
the interactions among the consumers (EV owner), the transportation network
graph, the electric power network graph, and the charging stations.

###  3.2 Motivation and Related Work

The continued technological innovations in battery and electric drivetrain
have made electric vehicles (EVs) a viable solution for a sustainable
transportation system. Currently, most EV charging is done either at
residences, or for free at some public charging infrastructure provided by
municipalities, office buildings, etc. As the EV industry continues to grow,
many more commercial charging stations need to be strategically added and
placed. Development of effective management and regulation of EV charging
infrastructure needs to consider the benefits of multiple
constituencies–consumers, charging station owners, power grid operators, local
government, etc. In this section, we propose a placement policy aiming at
striking a balance among the profits of charging station owners, consumer
satisfaction, and power grid’s reliability.

Our work is motivated by the desire of those service providers to make a
forward-looking decision on charging station placement to obtain a good return
on the investment. We plan to use the most up-to-date information (i.e.,
travel pattern, traffic flow, road network, power grid, etc.) to make the
best-effort decisions on charging station placement, hoping that service
providers will have a good chance to profit over the next few years. In this
model, we do not consider some factors like uncertainties in fuel prices,
climate change, population migration etc., which are random and unpredictable
in a long period of time. Instead, we believe some revenue management
techniques (i.e., realtime pricing) may be applied to deal with the potential
effects of those factors in our future work.

We assume that the service providers aim to strike a balance between the
competing goals of maximizing the profits and minimizing the disturbance to
electric power network due to large-scale EV charging. Accordingly, we
construct a utility function that incorporates both the total profits and the
impacts of EV charging on the electric power grid. Each charging service
provider attempts to maximize their own expected utility function while
satisfying the Quality-of-Service (QoS) constraints through choosing the
optimal locations of charging station. Note that consumers usually have
different preferences (tastes) over certain products and services. The nested
logit model will be used to analyze and predict the charging preference of EV
owners. As the EV penetration rate increases, the existing charging stations
may no longer satisfy the QoS constraints and a new stage shall be initiated
to place more charging stations. At the beginning of each stage, the service
providers predict the charging demand of each charging station candidate using
the nested logit model. The optimal placement strategy is obtained through a
Bayesian game.

There is a growing literature addressing the issues relevant to EV charging
station placement. [81, 82, 83, 84] formulated charging station placement as
an optimization problem. However, they did not take into account the overall
consumer satisfaction and the impacts of EV charging on electric power network
in their works. Besides, their optimization models were formulated from the
perspective of a central urban planner rather than that of service providers
in a free competitive market. In [85], the authors presented a strategy to
deploy charging stations by analyzing the patterns of residential EV ownership
and driving activities. In their work, they deploy the new charging stations
either randomly with no weight or only based on the weights of population.
They did not consider the mobility of EVs and the overall consumer experience.
Bernardo et al. [86] proposed a discrete choice model (DCM) based framework to
study the optimal locations for fast charging stations. They treat each
charging station as a player in a noncooperative game. However, the underlying
assumption in their work is that each player has complete information about
other players, which is too restrictive and infeasible in a practical
competitive market. In this section, we propose a Bayesian game framework that
does not require the complete information of other players.

The main contributions of our work are summarized as follows:

  * •

A multi-stage charging station placement strategy with incremental EV
penetration rates is first formulated, which takes into account the
interactions among EVs, road network, and the electric power grid.

  * •

A nested logit model is then employed to characterize the overall consumer
satisfaction and predict the aggregated charging demand, which provides
insights into the preferences and decision-making processes of EV owners.

  * •

An oligopolistic market model of EV charging service providers is studied and
a Bayesian game framework is applied to analyze the strategic interactions
among service providers.

  * •

A simulation software has been developed to analyze the interplay among EV
owners, road network, power grid, urban infrastructure and charging stations.

###  3.3 Preliminaries on Oligopoly and Consumer Behavior Analytics

In this section, we will introduce basic knowledge on oligopoly and consumer
behavior analytics.

####  3.3.1 Oligopoly Market

An oligopoly [87, 88] is a market form which is dominated by a small number of
sellers (oligopolists). Oligopoly can reduce competition and lead to higher
prices for consumers through different forms of collusion. In contrast to
oligopoly, monopoly is a market form which is controlled by a single seller.
There are many oligopolistic market examples, such as the Pepsi and Coke in
the soft drink industry and the four wireless providers in US—Verizon, AT&T,
T-Mobile, and Sprint. The retail gasoline market is another example of an
oligopoly because a small number of firms control a large majority of the
gasoline market.

For this type of market, each oligopolist is aware of the actions of the other
oligopolists, and the decisions of one oligopolist can significantly affect or
be affected by others. According to game theory, strategic planning by
oligopolists needs to take into account the possible responses of the other
market participants.

Characteristics of Oligopoly: Oligopoly has several characteristics:

  * •

Profit maximizer: An oligopolist maximizes its profits.

  * •

Ability to set price: Oligopolies all have the market power to set the prices.

  * •

Entry and exit: The cost to enter the market can be high. The most important
barriers are government regulation, patents, key technologies, and strategic
actions from incumbent firms to impede the entry of nascent firms.

  * •

Product differentiation: The product in an oligopoly can be homogeneous (i.e.
steel, gasoline) or differentiated (i.e. wireless services, automobile).

  * •

Knowledge about each other: Oligopolists have perfect knowledge about their
own production and demand. However, usually the information about other
oligopolists are incomplete.

  * •

Strategic interaction: An oligopoly consists of a few giant companies. Each
oligopolist’s action can influence the price of the entire market. Therefore,
an oligopolist will take into account the possible actions of the other
oligopolists when determine its own actions.

Outcomes of Oligopoly: The competition among the oligopolists can result in
different outcomes depending on how they interact with other. In some markets,
the firms may employ very restrictive transaction practices (collusion, market
sharing etc.) to raise prices and restrict production in much the same way as
a monopoly. An example of such oligopoly market structure is the Organization
of the Petroleum Exporting Countries (OPEC), which can greatly impact on the
international price of oil. In some markets, there may exist a recognized
leader who sets the product price and the other market participants just
follow the price. This type of market is called price leadership. In other
markets, the competition among the oligopolists can be extremely fierce. They
compete with each other in prices and productions. This may ultimately lead to
perfect competition.

Mathematical Models of Oligopoly: Various models have been employed to analyze
oligopoly, among which Cournot-Nash model and Betrand model are the most
famous. There are several classic papers comparing and discussing the two
models [89, 90, 91, 92].

Cournot model describes a market where the firms compete on the quantities
instead of prices and each firm makes an output decision under the assumption
of the other firm’s output is fixed. The firms will adjust their output
quantities in response to the other firms’ actions. It may take a series of
actions and reactions before the firms finally reach the Cournot-Nash
Equilibrium, in which situation no firm will change their output quantities
given that they are aware the reactions of the other firms to any changes.

For example, we assume there are two firms in a market which produce
homogeneous product. Suppose the output of firm 1 is $q_{1}$ and the output of
firm 2 is $q_{2}$. Since the two firms produce homogeneous product, the price
should be the same when they reach the Nash Equilibrium. We suppose the
equilibrium price is a function of $q_{1}$ and $q_{2}$, i.e. $f(q_{1}+q_{2})$.
The cost of the two firms are denoted using $C_{1}(q_{1})$ and $C_{2}(q_{2})$,
respectively. The profit of each firm is the total revenue minus the cost.

$\Pi_{j}=f(q_{1}+q_{2})q_{j}-C_{j}(q_{j}).\;\;\;(j=1,2)$ (3.1)

The best response is to maximize $\Pi_{j}$ by finding the optimal $q_{j}$
given that $q_{i}$ is fixed ($i\neq j$). Take the first derivative of
$\Pi_{j}$ with respect to $q_{j}$ and set it to zero.

$\frac{\partial\Pi_{j}}{\partial q_{j}}=q_{j}\frac{\partial
f(q_{1}+q_{2})}{\partial q_{j}}+f(q_{1}+q_{2})-\frac{\partial
C_{j}(q_{j})}{\partial q_{j}}=0.$ (3.2)

The value of $q_{j}$ satisfying the equation above is the best responses. The
Nash Equilibria are the pairs of $q_{1}$ and $q_{2}$ are satisfying the set of
equations simultaneously.

In contrast to Cournot model, Bertrand model describes an market where the
firms compete with each other in terms of product prices rather than product
quantities. We assume there are at least two firms dominating the market, and
the firms will not cooperate with each other. They try to maximize their
profits by setting the optimal prices taking into account the possible pricing
policies of the other firms.

Different from Cournot model, we need to consider two cases—homogeneous
product case and heterogeneous product case in Bertrand model, which lead to
very interesting results.

Homogeneous Product Case: We assume firm 1 and firm 2 produce exactly same
product. For simplicity, we assume the two firms have identical constant
marginal cost function. Let $MC$ represent the marginal cost of producing one
unit of the product. The firms set prices at $p_{1}$ and $p_{2}$ with outputs
of $q_{1}$ and $q_{2}$, respectively. Since the product is exactly the same,
any firm with a lower price will grab all the consumers. Therefore, the prices
of the two firms will be the same when they reach equilibrium, i.e.
$p_{1}=p_{2}=p$, where $p$ is the single market price. Furthermore, we assume
the market demand is expressed by a function $q=q(p)$. Under the equilibrium,
firm 1 and firm 2 will split the market demand equally—each firm sells the
same amount of products, $q_{1}=q_{2}=q/2$.

Heterogeneous Product Case: We assume the products of firm 1 and firm 2 are
similar, but not exactly the same. In this case, the prices do not have to be
the same in equilibrium since a lower price does not mean the firm will lose
the market. In addition, we assume the demands of the two firms depend on the
two prices: $q_{1}=q_{1}(p_{1},p_{2})$ and $q_{2}=q_{2}(p_{1},p_{2})$. For the
demand function of firm $i$ $q_{i}$, the partial derivative with respect to
$p_{i}$ should be negative, indicating that the price rise will result in a
decrease in demand and the partial derivative with respect to $p_{j}$ should
be positive, indicating that the price rise of the other firm will result in
an increase in its own demand. The profits of the two firms are given by

$\Pi_{1}=p_{1}q_{1}(p_{1},p_{2})-C_{1}(q_{1}(p_{1},p_{2})),$ (3.3)

and

$\Pi_{2}=p_{2}q_{2}(p_{1},p_{2})-C_{2}(q_{2}(p_{1},p_{2})).$ (3.4)

We take the first derivative of $\Pi_{1}$ and $\Pi_{2}$ with respect to
$p_{1}$ and $p_{2}$, respectively. The best responses of $p_{1}$ and $p_{2}$
are obtained by letting the derivatives equal to zero and solve the set of
equations. This is also called the first-order conditions (FOC).

$\displaystyle\frac{\partial\Pi_{1}}{\partial
p_{1}}=q_{1}(p_{1},p_{2})+p_{1}\frac{\partial q_{1}(p_{1},p_{2})}{\partial
p_{1}}-\frac{\partial C_{1}(q_{1})}{\partial q_{1}}\frac{\partial
q_{1}(p_{1},p_{2})}{\partial p_{1}}=0,$ (3.5)
$\displaystyle\frac{\partial\Pi_{2}}{\partial
p_{2}}=q_{2}(p_{1},p_{2})+p_{2}\frac{\partial q_{2}(p_{1},p_{2})}{\partial
p_{2}}-\frac{\partial C_{2}(q_{2})}{\partial q_{2}}\frac{\partial
q_{2}(p_{1},p_{2})}{\partial p_{2}}=0.$

We can rewrite it into a more compact way as follows,

$\displaystyle\frac{\partial\Pi_{1}}{\partial p_{1}}=q_{1}+p_{1}\frac{\partial
q_{1}}{\partial p_{1}}-MC_{1}\frac{\partial q_{1}}{\partial p_{1}}=0,$ (3.6)
$\displaystyle\frac{\partial\Pi_{2}}{\partial p_{2}}=q_{2}+p_{2}\frac{\partial
q_{2}}{\partial p_{2}}-MC_{2}\frac{\partial q_{2}}{\partial p_{2}}=0.$

where $MC_{1}$ and $MC_{2}$ are the marginal cost of firm 1 and firm 2,
respectively.

####  3.3.2 Consumer Behavior Analytics

In consumer behavior analytics, discrete choice model (DCM) is employed to
characterize, explain, and predict how a consumer will choose a certain
product in the presence of a finite set of alternatives, for instance which
car to buy, where to go to college, and which mode of transportation (bus,
taxi, rail) to use to work [93, 94, 95, 96]. DCM is a powerful tool that we
can use to calculate the probability that a certain consumer will choose a
certain product among a finite set of alternatives. The basic idea of DCM is
that a consumer tries to maximize the total utility when making a decision in
the presence of multiple choice alternatives.

We assume that there are some factors that determine a consumer’s choice. Some
of them are observed by the researchers, but some are not. The observed
factors are labelled as $x$ and the unobserved factors are denoted as
$\epsilon$ (we can call it the random term). How these factors influence the
choice of a consumer is expressed using a function $y=h(x,\epsilon)$. The
function characterizes the behavioral process of decision making of a
consumer. Since $\epsilon$ is not observed, the choice of a consumer is not
deterministic and cannot be exactly predicted by researchers. We assume that
$\epsilon$ is a random variable with a probability density function (PDF)
$f(\epsilon)$. The probability that a consumer chooses a particular product
among a finite set of alternatives is just the probability that the unobserved
factor such that the behavioral process results in the that outcome, i.e.
$P(y|x)=\textrm{Prob}(\epsilon s.t.h(x,\epsilon)=y)$. The probability can be
calculated by integration as follows,

$\displaystyle P(y|x)$
$\displaystyle=\textrm{Prob}\left(I[h(x,\epsilon)=y]=1\right)$ (3.7)
$\displaystyle=\int I[h(x,\epsilon)=y]f(\epsilon)d\epsilon.$

where $I[h(x,\epsilon)=y]$ is an indicator function which takes value of 1
when the statement in the brackets is true and value of 0 otherwise.

Nested Logit Model: DCM consists of many models, which encompasses the simple
logit model, the nested logit model, the probit model, and the mixed logit
model. The logit model is the most simple model with the assumption that the
unobserved factors have iid extreme value distribution. Other complex models
are developed based on logit model. In contrast to logit, nested logit model
divides the set of alternatives into multiple small nests wherein alternatives
are correlated and the alternatives across different nests are independent.
Probit is derived under the assumption that the unobserved factors have a
joint normal distribution, while the mixed logit allows the unobserved factors
to have any distribution. In this subsection, we will primarily introduce the
nested logit model, which will be utilized to characterize the EV charging
demand in the following sections.

The nested logit model is appropriate for the situation where the set of
alternatives faced by a consumer can be partitioned into several subsets, or
nests. The nested logit model differs from the logit model in that it allows
correlations among the alternatives.

Suppose that a consumer is facing a set of alternatives. Let the alternatives
be partitioned into $K$ non-overlapping nests $B_{1},B_{2},\cdots,B_{K}$. The
utility that consumer $n$ obtains from alternative $j$ in nest $B_{k}$ is
denoted as $U_{nj}=V_{nj}+\epsilon_{nj}$, where $V_{nj}$ is observed utility
and $\epsilon_{nj}$ is the unobservable utility. The vector of unobservable
utilities $[\epsilon_{n1},\epsilon_{n2},\cdots,\epsilon_{nJ}]$ has the
generalized extreme value (GEV) distribution with the cumulative distribution
function (CDF) as follows,

$F(\epsilon_{n})=\exp\left(-\sum_{k=1}^{K}\left(\sum_{j\in
B_{k}}e^{-\epsilon_{nj}/\sigma_{k}}\right)^{\sigma_{k}}\right),$ (3.8)

where $\sigma_{k}$ is a measure of the degree of independence in the
unobservable utility within nest $B_{k}$. For any alternatives $j$ and $i$ in
nest $B_{k}$, the unobservable utility $\epsilon_{nj}$ and $\epsilon_{ni}$ are
correlated. For any alternatives in different nests, the unobservable
utilities are uncorrelated: $Cov(\epsilon_{nj},\epsilon_{nm})=0$, for $j\in
B_{k}$ and $m\in B_{l}$ and $k\neq l$.

The probability that consumer $n$ will choose alternative $j$ is obtained by
taking the expectation over the unobservable utilities as defined in Eq.
(3.9).

$\displaystyle P_{nj}$
$\displaystyle=\mathbf{Prob}\left(V_{nj}+\epsilon_{nj}>V_{ni}+\epsilon_{ni},\forall
i\neq j\right)$ (3.9)
$\displaystyle=\int_{-\infty}^{+\infty}F_{nj}(V_{nj}-V_{n1}+\epsilon_{nj},V_{nj}-V_{n2}+\epsilon_{nj},\cdots,V_{nj}-V_{nJ}+\epsilon_{nj})d\epsilon_{nj}$

where $F_{nj}$ is obtained by taking the derivative of $F(\epsilon_{n})$ with
respective to $\epsilon_{nj}$: $F_{nj}\frac{\partial
F(\epsilon_{n})}{\partial\epsilon_{nj}}$. Finally, the integration gives us
the probability in the following form.

$P_{nj}=\frac{e^{V_{nj}/\sigma_{k}}\left(\sum_{i\in
B_{k}}e^{V_{ni}/\sigma_{k}}\right)^{\sigma_{k}-1}}{\sum_{l=1}^{K}\left(\sum_{i\in
B_{l}}e^{V_{ni}/\sigma_{l}}\right)^{\sigma_{l}}}.$ (3.10)

See Appendix for more detailed derivation of Eq. (3.10).

###  3.4 Problem Formulation

I postulate the problem of EV charging with an oligopolistic market structure
that has multiple charging service providers (oligopolists). The service
providers aim to maximize their expected utility while satisfying the QoS
constraints by selecting optimal station placements.

Particularly, we consider the case of three service providers that offer three
EV charging services [33], namely, Level 1, Level 2, and Level 3 (see Table
2.1 for details). Level 1 and Level 2 are AC charging. Level 3 charging is DC
Fast charging. Let $\mathcal{O}=\\{1,2,3\\}$ denote the set of charging
service providers. Moreover, we assume that service provider 1 offers Level 1
charging, service provider 2 offers Level 2 charging, and service provider 3
offers Level 3 charging. The three charging levels represent three charging
services, which have different charging voltages and currents, charging times,
and charging experiences. In economics, they are imperfect substitutes to each
other. In our model, we are interested in investigating how the different
charging services compete with each other in choosing locations and prices.
Each service provider can run multiple charging stations. At each planning
stage, service providers select some charging stations from a given set of
candidates, denoted as $\mathcal{I}=\\{1,2,3\cdots,L\\}$. The set of EVs is
denoted as $\mathcal{E}=\\{1,2,3,\cdots,N\\}$.

####  3.4.1 Profit of EV Charging

We assume that service providers run the charging stations like chain stores ,
so charging stations affiliated with the same service provider have the same
retail charging price. The charging stations purchase the electricity from the
wholesale market at the locational marginal price (LMP). In a deregulated
electricity market (like PJM, NYISO, NEISO, MISO, ERCOT, California ISO in
USA, the New Zealand and Singapore markets), LMP is computed at every node
(bus) by the market coordinator. LMP primarily consists of three components:
system energy price, transmission congestion cost, and cost of marginal losses
[36]. Let $p_{k}$ represent the retail charging price of provider
$k\;(k=1,2,3)$, and $p_{-k}$ be the retail charging prices of the other two
service providers except $k$. Let $c_{j,k}$ be the LMP of the $j$th charging
station candidate of service provider $k$, and $\psi_{j,k}$ be the predicted
charging demand at the $j$th charging station candidate of service provider
$k$. The vector $S_{k}=[s_{1,k},s_{2,k},\cdots,s_{L,k}]^{\textrm{T}}$
represents the placement policy of service provider $k$, where
$s_{j,k}\in\\{0,1\\}$ is an indicator with $s_{j,k}=1$ implying that service
provider $k$ will place the $j$th charging station. Let $S_{-k}$ represent the
placement policies of the other two service providers, $\theta_{j,k}$ be the
placement cost of the $j$th charging station. The total profit of service
provider $k$ is

$\Pi_{k}=p_{k}\Psi_{k}^{\textrm{T}}S_{k}-\textrm{diag}[C_{k}]\Psi_{k}^{\textrm{T}}S_{k}-\Theta_{k}^{\textrm{T}}S_{k},$
(3.11)

and the total revenue of service provider $k$ is,

$R_{k}=p_{k}\Psi_{k}^{\textrm{T}}S_{k}-\textrm{diag}[C_{k}]\Psi_{k}^{\textrm{T}}S_{k},$
(3.12)

where
$\Psi_{k}=[\psi_{1,k},\psi_{2,k},\psi_{3,k},\cdots,\psi_{L,k}]^{\textrm{T}}$,
$C_{k}=[c_{1,k},c_{2,k},\cdots,c_{L,k}]^{\textrm{T}}$ and
$\Theta_{k}=$ $[\theta_{1,k},\theta_{2,k},\cdots,\theta_{L,k}]^{\textrm{T}}$.
The notation $\textrm{diag}[.]$ is an operator to create a diagonal matrix
using the underlying vector, and $[.]^{\textrm{T}}$ is the transpose
operation. In the equation above, the total sale is
$p_{k}\Psi_{k}^{\textrm{T}}S_{k}$, the cost of purchasing electricity is
$\textrm{diag}[C_{k}]\Psi_{k}^{\textrm{T}}S_{k}$, and the placement cost is
$\Theta_{k}^{\textrm{T}}S_{k}$.

####  3.4.2 Impact of EV Charging on Power Grid

It is conceivable that the simultaneous large-scale EV charging can disrupt
the normal operation of the power grid in terms of frequency variation,
voltage imbalance, voltage variation, power loss. In a conventional power
grid, the generators will cooperatively control the output of real power and
reactive power to maintain system stability, perform frequency regulation and
voltage regulation. The charging service providers must optimally place the
charging stations to mitigate the “disturbance” to the power grid.
Accordingly, the overall utility function of service provider can be defined
as:

$U_{k}=\Pi_{k}-wB_{k},$ (3.13)

where $\Pi_{k}$ is the total profits from EV charging. $B_{k}$ characterizes
the penalty arising from large-scale EV charging. The variable $w$ is a
weighting coefficient, reflecting the tolerance to the penalty. In the
following section, we will further discuss how to develop a proper metric to
evaluate the penalty $B_{k}$. We should note that the weighting factor $w$ in
Eq. (3.13) offers a mechanism for the charging service providers to strike a
balance between their own profit and the “stress” their charging add to the
power system. If $w=0$, the impact of EV charging on the grid is not
considered at all, and any non-zero value of $w$ implies some impact on the
grid—the larger $w$ is, the larger the impact it is. Generally, if the focus
is on the charging provider’s profit, a small $w$ is used. In practice, the
value of $w$ needs to be determined with the help of heuristic and empirical
data.

####  3.4.3 Quality-of-Service Metrics

We use two quality-of-service (QoS) metrics for the service provider: (1)
average service delay probability $\Upsilon_{k}$, (2) average service coverage
$\Xi_{k},\;(k=1,2,3)$.

$\Upsilon_{k}=\frac{1}{N}\sum_{i=1}^{N}\upsilon_{i,k},$ (3.14)

$\Xi_{k}=\frac{1}{N}\sum_{i=1}^{N}\xi_{i,k},$ (3.15)

where $\upsilon_{i,k}$ is the average service delay probability for the $i$th
EV owner getting the EV charged at service provider $k$. For the $i$th EV
owner, $\upsilon_{i,k}$ is defined as the ratio of the number of delayed
charging to the total number of charging attempts; $\xi_{i,k}$ is the average
number of accessible Level $k$ charging stations along the route from origin
to destination. Notice that $\upsilon_{i,k}$ and $\xi_{i,k}$ are two random
variables depending on the travel patterns of all EVs, the urban road network
and the charging stations. It is difficult to use a simple formula to compute
them. Instead, we employ Mento Carlo method to estimate those two values.

####  3.4.4 Multi-Stage Charging Station Planning Scheme

At each planning stage, the service providers aim at solving the following
fundamental problem to obtain the optimal placement policy subjected to the
QoS constraints.

$\displaystyle[S_{k}^{T}|S_{1}^{T-1},S_{2}^{T-1},S_{3}^{T-1}]=$ (3.16)
$\displaystyle\operatorname*{argmax}_{\begin{subarray}{c}{s_{1,k},\cdots,s_{L,k}}\\\
{s_{j,k}\in\\{0,1\\}}\end{subarray}}\left\\{\mathbb{E}_{S_{-k}}[U_{k}]|S_{1}^{T-1},S_{2}^{T-1},S_{3}^{T-1}\right\\},$

subject to

$\Upsilon_{k}\leq\Upsilon^{0},$ (3.17) $\Xi_{k}\leq\Xi^{0},$ (3.18)

where $\mathbb{E}_{S_{-k}}[.]$ denotes the expectation over $S_{-k}$, and
$S_{k}^{T}$ is the placement policy at stage $T$. The variables $\Upsilon^{0}$
and $\Xi^{0}$ are the predetermined QoS constraints.

####  3.4.5 Emerging Problems

To solve the optimization problem defined as Eq. (3.16), we are confronted
with three principal questions: (1) How to predict the aggregated charging
demand $\psi_{j,k}$ at each charging station candidate? (2) How to find an
appropriate metric to characterize the impacts of EV charging on the power
grid? (3) How to derive the optimal placement policy in an easier way? For the
first question, we propose to employ the nested logit model to estimate the
charging demand using a nested logit model. As for the second question, we
will discuss the how EV charging may impact the power grid, and propose a
metric to assess the impacts of EV charging. For the last question, notice
that the optimization problem formulated by Eq. (3.16) is intractable since
the optimal placement decision for every service provider also depends on the
decisions taken by other service providers. To this end, we employ a Bayesian
game model to characterize the strategic interaction and price competition
among the service providers.

###  3.5 EV Charging Demand Estimation

In our model, the aggregated charging demand at a charging station candidate
is defined as the sum of the product of the probability that EV owners choose
that charging station and the electricity required to charge the EVs. The
charging behaviors of EV owners may be influenced by many factors that include
the charging price, travel cost, amenities at or near the charging station,
the travel purpose, EV owner’s income, etc. We plan to the nested logit model
to characterize the attractiveness of a charging station.

The nested logit model is widely used in the analysis and prediction of a
consumer s choice from a finite set of choice alternatives. The main idea of
nested logit model is that a consumer is a utility maximizer. The consumer
will choose the very product which brings him/her the maximum utility.

In our problem, the utility that the $n$th EV owner can obtain from choosing
charging station $j\;(j=1,2,\cdots,L)$ of service provider $k\;(k=1,2,3)$ is
denoted as $U_{j,k}^{n}=\overline{U}_{j,k}^{n}+\epsilon_{j,k}^{n}$, where
$\overline{U}_{j,k}^{n}$ is the observable utility and $\epsilon_{j,k}^{n}$ is
the unobservable utility. The vector of unobservable utility
$\epsilon^{n}=[\epsilon_{1,1}^{n},\cdots,\epsilon_{L,1}^{n},\epsilon_{1,2}^{n},\cdots,\epsilon_{L,2}^{n},\epsilon_{1,3}^{n},\cdots,\epsilon_{L,3}^{n}]^{\textrm{T}}$
is assumed to have a generalized extreme value (GEV) distribution with
cumulative distribution function (CDF).

$F(\epsilon^{n})=\exp\left(-\sum_{k=1}^{3}\left(\sum_{l=1}^{L}e^{-\epsilon_{l,k}^{n}/\sigma_{k}}\right)^{\sigma_{k}}\right),$
(3.19)

where $\sigma_{k}$ is a measure of the degree of independence in the
unobservable utility among the charging stations owned by service provider
$k$. For nested logit model, $\epsilon_{j,k}$ is correlated within each
charging level, and uncorrelated across different charging levels.

For nested logit model, we can decompose the observable utility
$\overline{U}_{j,k}^{n}$ into two components—the utility of choosing service
provider $k$ and the utility of choosing a charging station $j$. In addition,
we assume home charging is the “outside good” in this market [95, 97]. Thus,
$\overline{U}_{j,k}^{n}$ for EV owner $n$ can be expressed as

$\overline{U}_{j,k}^{n}=\overline{W}_{k}^{n}+\overline{V}_{j,k}^{n},$ (3.20)

where $\overline{W}_{k}^{n}$ is the observable utility of choosing service
provider $k$ (choosing nest $k$), and $\overline{V}_{j,k}^{n}$ is the
observable utility of choosing charging station $j$ given that service
provider $k$ has been chosen; $\overline{W}_{k}^{n}$ and $\overline{V}_{j,k}$
are linear weighted combinations of attributes of the charging stations and
the EV owner.

Note that the retail charging price and the charging time are the two
important factors differentiating the three charging services. In addition, we
assume the income of EV owners will also play a role in choosing charging
services. In contrast to our previous work [98], we use a different formula to
calculate $\overline{W}_{k}^{n}$ here.

$\overline{W}_{k}^{n}=\alpha\frac{1}{t_{k}}+\beta\frac{p_{k}}{i_{n}},$ (3.21)

where $t_{k}$, $p_{k}$ and $i_{n}$ represent, respectively, the averaged
charging time, the retail charging price, and the income of the $n$th EV
owner; $\alpha,\beta$ are the corresponding weighting coefficients. This model
is similar to Ben-Akiva and Lerman’s utility model in their study of public
transportation mode [96]. The value of $\alpha$ is positive because shorter
charging time implies a better charging service experience, therefore, leading
to higher utility. The value of $\beta$ is negative because a higher retail
charging price always results in less utility. However, the retail charging
price is divided by the income, which reflects that the retail charging price
for the EV owners becomes less important as their income increases. As an
“outside good”, the utility of home charging is normalized, i.e.
$\overline{W}_{0}^{n}=0$.

Furthermore, we define $\overline{V}_{j,k}^{n}$ as follows,

$\displaystyle\overline{V}_{j,k}^{n}=$
$\displaystyle\mu_{k}d_{j,k}^{n}+\eta_{k}z_{j,k}^{n}+\gamma_{k}r_{j,k}+\lambda_{k}g_{j,k}+\delta_{k}m_{j,k},$
(3.22)

where $z_{j,k}^{n}$ is the destination indicator. If the $j$th charging
station is near the EV owner’s travel destination (within a threshold distance
$d_{th}$), $z_{j,k}^{n}=1$, otherwise, $z_{j,k}^{n}=0$. $d_{j,k}^{n}$ is the
deviating distance due to EV charging. We use Dijkstra’s shortest path
algorithm [99] to calculate a travel route for each EV owner from his/her
origin to destination. If an EV owner needs to go to charging station $j$
halfway, we define the deviating distance The variable $d_{j,k}^{n}$ as the
route length of this new route minus the route length of the original route.
Additionally, each candidate charging station has a vector of characteristics
$[r_{j,k},g_{j,k},m_{j,k}]^{\mathrm{T}}$, which characterizes the
attractiveness of this charging station in terms of those amenities. For
instance, if there exists a restaurant near location $j$, $r_{j,k}=1$,
otherwise $r_{j,k}=0$. Similarly, $g_{j,k}$ and $m_{j,k}$ are the indicators
for shopping center and supermarket, respectively. The corresponding weighting
coefficients are $\mu_{k},\eta_{k},\gamma_{k},\lambda_{k},\delta_{k}$.

The EV owner’s choice is not deterministic due to the random unobservable
utility. However, we can derive the probability that an EV owner will choose a
certain charging station by taking the expectation over the unobservable
utilities. Similar to Eq. (3.10), the probability that the $n$th EV owner will
choose the $j$th charging station of service provider $k$ is

$\Phi_{j,k}^{n}=\frac{e^{\overline{U}_{j,k}^{n}/\sigma_{k}}\left(\sum_{l=1}^{L}e^{\overline{U}_{l,k}^{n}/\sigma_{k}}\right)^{\sigma_{k}-1}}{\sum_{t=1}^{3}\left(\sum_{l=1}^{L}e^{\overline{U}_{l,t}^{n}/\sigma_{t}}\right)^{\sigma_{t}}}.$
(3.23)

All coefficients in the nested logit model can be estimated and calibrated
from preference survey data. The nested logit model enables us to compute the
probability that an EV owner will go to a certain charging station, even
though, an EV owner’s decision may not always comply with the calculated
probabilities. An individual EV owner may go to a fixed charging station at
his/her discretion. However, employing the nested logit model provides a
statistically meaningful prediction for the charging demand based on ensemble
averages.

Once the EV owners’ choice probability is computed, we can predict the
charging demand of a charging station. Let $q_{n}\;(n=1,2,\cdots,N)$ denote
the total electricity (measured in kWh) that the $n$th EV owner purchases from
the charging station, and $q_{n}$ is a random variable uniformly distributed
in the range $[Q_{a},Q_{b}]$, where $Q_{a}$ and $Q_{b}$ are, respectively, the
lower and upper limit of charging demand for all EVs. The total predicted
charging demand of charging station $j$ of service provider $k$ is

$\psi_{j,k}=\sum_{n=1}^{N}q_{n}\Phi_{j,k}^{n}.$ (3.24)

###  3.6 Impact of EV Integration on Power Grid

The main function of the power grid is to deliver electricity to users
reliably and economically. However, large-scale EV integration can potentially
disrupt the normal operation of power grid in terms of system stability,
severe power loss, frequency variation, voltage imbalance, etc. Generally, the
variations in voltage and frequency of electricity are considered as the major
factors to characterize the power quality.

Assume that the power system has $M$ generators and $D$ buses (substations),
and the power flow study approach [100] is applied to solve the voltage, real
power, and reactive power in the power system. Consider the node power
equations, which can be written as real and reactive power for each bus.

$0=-P_{i}+\sum_{k=1}^{N}|v_{i}||v_{k}|(G_{ik}\cos\phi_{ik}+B_{ik}\sin\phi_{ik}),$
(3.25)
$0=-Q_{i}+\sum_{k=1}^{N}|v_{i}||v_{k}|(G_{ik}\sin\phi_{ik}-B_{ik}\cos\phi_{ik}),$
(3.26)

where $P_{i}$ and $Q_{i}$ are, respectively, the injected real power and
reactive power at bus $i$. The variable $G_{ik}$ is the real part of the
element in the bus admittance matrix corresponding to the $i$th row and $k$th
column, and $B_{ik}$ is the imaginary part of the element. $\phi_{ik}$ is the
voltage angle between the $i$th bus and the $k$th bus. $|v_{i}|$ and $|v_{k}|$
are the voltage magnitudes at bus $i$ and bus $k$, respectively.

Generally, the power plants hope that the load is predictable and stable (or
at least slow-varying). If the load fluctuates too much, the power plants have
to ramp up and ramp down frequently, resulting in low efficiency and high cost
from committing spinning reserve [101]. Therefore, the fluctuation of the
active power and reactive power at the generators with and without EV charging
can be used as a metric to evaluate this “stress”. In particular, we use the
2-norm deviation of generating power (real power and reactive power) of all
generators in the power system to calculate the impacts of EV charging.

$B=||\mathbf{P}_{\textrm{g}}^{\textrm{base}}-\mathbf{P}_{\textrm{g}}^{\textrm{EV}}||^{2}_{2}+||\mathbf{Q}_{\textrm{g}}^{\textrm{base}}-\mathbf{Q}_{\textrm{g}}^{\textrm{EV}}||^{2}_{2},$
(3.27)

where
$\mathbf{P}_{\textrm{g}}^{\textrm{base}}=[P_{1}^{\textrm{base}},P_{2}^{\textrm{base}},\cdots,P_{M}^{\textrm{base}}]$
is a vector representing the active power generated by the $M$ generators
under the base power load scenario (without EV charging), and
$\mathbf{P}_{\textrm{g}}^{\textrm{EV}}=[P_{1}^{\textrm{EV}},P_{2}^{\textrm{EV}},\cdots,P_{M}^{\textrm{EV}}]$
is the vector of active power with EV charging (i.e., base power load
superposed by EV charging load). Similarly,
$\mathbf{Q}_{\textrm{g}}^{\textrm{base}}=[Q_{1}^{\textrm{base}},Q_{2}^{\textrm{base}},\cdots,Q_{M}^{\textrm{base}}]$
is the vector of reactive power of the base load, and
$\mathbf{Q}_{\textrm{g}}^{\textrm{EV}}=[Q_{1}^{\textrm{EV}},Q_{2}^{\textrm{EV}},\cdots,Q_{M}^{\textrm{EV}}]$
is the vector of reactive power with EV charging. For a specific power system,
$\mathbf{P}_{\textrm{g}}^{\textrm{base}},\mathbf{P}_{\textrm{g}}^{\textrm{EV}},\mathbf{Q}_{\textrm{g}}^{\textrm{base}}$,
and $\mathbf{Q}_{\textrm{g}}^{\textrm{EV}}$ can be calculated through solving
global power flow.

###  3.7 Spatial Competition and Optimal Placement through a Bayesian Game

It is pivotal for firms to choose the right location and product to compete
with rivals in the same industry. Business locations will affect business
competition, and conversely intensive competition will affect how firms choose
the appropriate locations. One question arises naturally is whether or not
firms from the same industry like to cluster their stores. There are some
classical literature on spatial competition, e.g. Hotelling’s location model
[102] and Salop’s circle model [97]. Firms have incentives for both clustering
and separation. On one hand, firms prefer clustering so that they can learn
from each other on how to improve manufacturing and research productivity
[103, 104], and learn demand from each other to reduce the cost of searching
for the optimal location. Firms also cluster for the labor pool and supplies.
In addition, firms can benefit from the spinoffs that are located near parent
firms. On the other hand, the fear of intensive price competition due to
clustering may motivate the firms to separate from each other.

The EV charging service providers face the similar dilemma. Therefore, we need
to investigate how the service providers will interact with each other in
choosing their charging station locations and setting the retail charging
prices. In practice, the exact placement costs and utility functions of the
competing service providers may not be known to the service provider _a
priori_. We thus formulate the problem as a Bayesian game [105] among the
service providers at each planning stage.

The main components of a Bayesian game include a set of players $\mathcal{I}$,
a strategy space $S_{k}$, a type space $\Theta_{k}$, a payoff function
$u_{k}$, and a joint probability of the types
$f(\Theta_{1},\Theta_{2},\Theta_{3})$. We will construct the utility function
of each service provider. The Bayesian Nash Equilibirum (BNE) of charging
station placement strategy can be derived by the first order of conditions
(FOC).

Before proceeding to analyze the Bayesian game, we need the following
assumptions.

$\mathbf{Assumption\;1}$: $f(S_{-k})$ is binomially distributed with parameter
0.5, _i.e._ $S_{-k}\backsim\textrm{Binomial}(2L,0.5)$.

$\mathbf{Remark\;1}$: The distribution of $S_{-k}$ reflects player $k$’s
conjecture on how other players will act during the game. Each player can form
their conjectures about other players according to their beliefs about the
competitors. For instance, a player may be risk neutral, risk aversion or risk
seeking. For simplicity, we assume that $S_{-k}$ has a binomial distribution
with parameter 0.5. However, the theoretical analysis can be applied to any
other distribution of $S_{-k}$.

$\mathbf{Assumption\;2}$: All service providers in the market are Bertrand
competitors.

$\mathbf{Remark\;2}$: Bertrand competitors are players that do not cooperate
with each other. Their goal is to maximize their own utility. They will not
form any type of “coalition” to manipulate the market.

For each player, the Bayesian Nash Equilibirum (BNE) of placement policy can
be derived from Eq. (3.16). To solve Equation (3.16), we need to know the
retail charging prices of all the service providers. In a Bertrand
competition, the retail prices for every combination of the charging station
placement policies are determined by the first order of conditions (FOC):

$\frac{\partial\Pi_{1}}{\partial
p_{1}}=\sum_{n=1}^{N}\sum_{j=1}^{L}q_{n}s_{j,1}\left[\Phi_{j,1}^{n}+(p_{1}-c_{j,1})\frac{\partial\Phi_{j,1}^{n}}{\partial
p_{1}}\right]=0$ (3.28) $\frac{\partial\Pi_{2}}{\partial
p_{2}}=\sum_{n=1}^{N}\sum_{j=1}^{L}q_{n}s_{j,2}\left[\Phi_{j,2}^{n}+(p_{2}-c_{j,2})\frac{\partial\Phi_{j,2}^{n}}{\partial
p_{2}}\right]=0$ (3.29) $\frac{\partial\Pi_{3}}{\partial
p_{3}}=\sum_{n=1}^{N}\sum_{j=1}^{L}q_{n}s_{j,3}\left[\Phi_{j,3}^{n}+(p_{3}-c_{j,3})\frac{\partial\Phi_{j,3}^{n}}{\partial
p_{3}}\right]=0$ (3.30)

where $c_{j,1},c_{j,2},$ and $c_{j,3}$ represent the LMP at each charging
station candidate.

$\mathbf{Remark\;3}$: For simulation simplicity, we assume the charging
stations affiliated to the same service provider have the same retail charging
prices ($p_{1},p_{2},\textrm{ and }p_{3}$). However, our analysis can be
easily generalized to the case where each charging station sets its own retail
price. Note that those retail prices obtained from Eq. (3.28)-(3.30) may not
be the real-time prices used in practice. They are only the equilibrium prices
in this market under the assumption of Bertrand competition. They can be
interpreted as the averaged charging prices of the service providers over a
long period of time. In practice, the service providers take turns to set the
retail price in response to the prices of the competitors. Additionally, if
some of the other factors change (i.e. consumer’s preference, crude oil price
soaring, etc.), the existing equilibrium breaks and a new equilibrium must be
computed using the same procedure.

$\mathbf{Theorem\;1}$ [Strategy Decision Condition]: Service provider $k$ will
choose placement policy $l(l=1,2,3,\cdots,2^{L})$ if the type space
$\Theta_{k}$ falls into the hypervolume specified by

$\displaystyle\mathcal{H}(l)=$ (3.31)
$\displaystyle\\{\Theta_{k}\in\mathbb{R}_{+}^{L}:\Theta_{k}^{\textrm{T}}\left(S_{k,j}-S_{k,l}\right)-(\mathbb{E}R_{k,j}-\mathbb{E}R_{k,l})$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+w(B_{k,j}-B_{k,l})>0;\forall
j\neq l\\},$

where $S_{k,j}$ and $S_{k,l}$ denote the placement strategy $j$ and $l$,
respectively. $\mathbb{E}R_{k,j}$ and $\mathbb{E}R_{k,l}$ denote the expected
total revenue with deployment strategy $j$ and $l$, respectively.

###### Proof.

Each service provider has $L$ location candidates, so there are $2^{L}$
different placement policies. The type space can be seen as an $L$-dimensional
space, and
$\Theta_{k}=[\theta_{1,k},\theta_{2,k},\cdots,\theta_{L,k}]^{\textrm{T}}$
represents a point in this space.

By Eq. (3.16), strategy $l$ is optimal if

$\displaystyle\mathbb{E}[R_{k,l}]-\Theta_{k}^{\textrm{T}}S_{k,l}-wB_{k,l}>\mathbb{E}[R_{k,j}]-$
(3.32)
$\displaystyle\;\;\;\;\;\;\;\;\;\;\Theta_{k}^{\textrm{T}}S_{k,j}-wB_{k,j};(j=1,2,\cdots,2^{L},j\neq
l).$

Rearranging the terms, we get

$\displaystyle\Theta_{k}^{\textrm{T}}\left(S_{k,j}-S_{k,l}\right)-(\mathbb{E}R_{k,j}-\mathbb{E}R_{k,l})+$
(3.33)
$\displaystyle\;\;\;\;\;\;\;w(B_{k,j}-B_{k,l})>0;(j=1,2,\cdots,2^{L},j\neq
l),$

where each inequality represents a hyperplane and the intersection of all the
inequalities defines a hypervolume in the type space. ∎

###  3.8 Simulation Platform Development and Case Study

We propose to develop a general-purpose simulation software—The EV Virtual
City 1.0 using Repast [106]. Our simulation software is designed to construct
a virtual digital city by integrating a variety of data and information, such
as geographic information, demographic information, spatial infrastructure
data, urban road network graph, electric power network graph, travel pattern,
diurnal variation in traffic flow, seasonal fluctuation of driving activities,
social interaction, etc. The platform is flexible that one can include or
exclude many modules to satisfy different simulation needs. See Fig. 3.1 for
the architecture of the simulation software.

Figure 3.1: The Architecture of The EV Virtual City 1.0

We will conduct a case study using the data of San Pedro District of Los
Angeles. We import the shapefiles of zip code tabulation area (ZCTA) and road
network data from the U.S. Census Bureau into our simulation software. In
addition, we have calculated the centroids of locations of residence,
restaurants, supermarkets, shopping centers and workplaces using Google Maps,
see Fig. 3.2.

Figure 3.2: Roads and Buildings of San Pedro District

Since travel pattern also plays a significant role in analysing the charging
behavior of EV owners, it is necessary to have a thorough study on the
statistics of travel pattern. From the 2009 National Household Travel Survey
(2009 NHTS) [107], we obtained the travel pattern statistics. See Fig. 3.3.

Figure 3.3: The Statistics of Travel Patterns

From the California Energy Commission website, we obtained the maps of
transmission line and substations of San Pedro District. This area has 107
substations in total. Thus we use the IEEE 118-bus power system test case in
our simulation. For each charging station placement policy, we used MATPOWER
[108] to calculate the LMP of each bus and the output power of each generator
with and without EV charging. See Fig. 3.4.

Figure 3.4: IEEE 118-Bus Power System Test Case

Figure 3.5: A Snapshot of EVs Movement

A snapshot of the moving EVs is shown in Fig. 3.5. Each red star represents an
EV owner. The traffic flow heatmap of EV owners is also plotted in this
figure. Figs. 3.6 to 3.9 correspond to the charging station placement for
stages 1 to 4, respectively. Fig. 3.10 is an overview of charging station
placement by superposing Figs. 3.6 to 3.9. Fig. 3.11 shows how the number of
charging station increases as the EV penetration rate increases.

Figure 3.6: Stage 1 Placement

Figure 3.7: Stage 2 Placement

Figure 3.8: Stage 3 Placement

Figure 3.9: Stage 4 Placement

Figure 3.10: Superimposing All Stages

Figure 3.11: Charging Station verses EV Penetration Rate

###  3.9 Conclusion

From the simulation results, we can make the following observations:

1\. The optimal charging station deployment is consistent with the EV traffic
flow heatmap. This suggests that our model can adequately capture the mobility
of EVs and provide EV owners with convenient charging services.

2\. As for the number of charging stations, Level 1 charging station is
predominant over Level 2 and Level 3. Level 3 has the least number of charging
stations. Notice that it takes a much longer time to finish charging for Level
1, so Level 1 service provider must place more charging stations to meet the
average delay probability constraint. The difference in quantity also reveals
that the service providers have different marketing strategies. Service
provider 1 tries to place the charging stations evenly across the entire area,
while service provider 3 is more likely to place the charging stations at some
“hot” locations.

3\. The number of charging stations grows almost linearly with the number of
EVs except for the initial stage. At the initial stage, Level 1 and Level 2
service providers tend to place more charging stations than the next stages.
This is because service providers must place more charging stations to meet
the average service coverage constraints. As the number of charging stations
increases, however, the service coverage constraint is less of a concern for
the service providers.

4\. Service providers prefer clustering instead of spatial separation. The
three service providers have segmented the EV charging market by providing
three different products (different charging level services) in terms of
voltage, current, charging speed and charging price. Due to product
differentiation, they significantly soften the price competition so that they
do not need to spatially separate from each other to further relax
competition. This observation supports the opinions in [109]-[110] that firms
do not have to maximize differentiation in every characteristic of the
product. In general, differentiation in one dominant characteristic is
sufficient to soften price competition.

##  Chapter 4 STOCHASTIC DYNAMIC PRICING FOR EV CHARGING STATIONS WITH
RENEWABLES INTEGRATION AND ENERGY STORAGE

###  4.1 Overview

This chapter studies the problem of stochastic dynamic pricing and energy
management policy for electric vehicle (EV) charging service providers. In the
presence of renewable energy integration and energy storage system, EV
charging service providers must deal with multiple uncertainties — charging
demand volatility, inherent intermittency of renewable energy generation, and
wholesale electricity price fluctuation. The motivation behind our work is to
offer guidelines for charging service providers to determine proper charging
prices and manage electricity to balance the competing objectives of improving
profitability, enhancing customer satisfaction, and reducing impact on power
grid in spite of these uncertainties. We propose a new metric to assess the
impact on power grid without solving complete power flow equations. To protect
service providers from severe financial losses, a safeguard of profit is
incorporated in the model. Two algorithms — stochastic dynamic programming
(SDP) algorithm and greedy algorithm (benchmark algorithm) — are applied to
derive the pricing and electricity procurement policy. A Pareto front of the
multi-objective optimization is derived. Simulation results show that using
SDP algorithm can achieve up to 7% profit gain over using greedy algorithm.
Additionally, we observe that the charging service provider is able to reshape
spatial-temporal charging demands to reduce the impact on power grid via
pricing signals.

###  4.2 Motivation and Related Work

Electric vehicles (EVs) exhibit many advantages over fossil fuel driven
vehicles in terms of operation and maintenance cost, energy efficiency, and
gas emission [111, 112, 113]. However, the fear of limited driving distance
(range anxiety) is hanging over EV drivers’ heads like the Sword of Damocles.
To alleviate this range anxiety, the capacity of on-board battery should be
increased and more EV charging stations should be deployed. Intensive research
work has been carried out to study how to strategically deploy charging
stations [114, 115, 116, 117, 118]. Currently, EV charging service is
primarily provided for free as one of the employee benefits in some
organizations or as a perk to those owners of some specific EV models (e.g.
Tesla). There is a lack of viable and profitable pricing and energy management
model for public charging stations. Our goal is to offer guidelines for
charging service providers to make informed and insightful decisions on
pricing and electricity procurement by jointly optimizing multiple objectives
under uncertainties.

There is a growing literature aimed at providing guidelines for economic
operation of EV charging stations. In [119, 120], the authors studied a
dynamic pricing scheme to improve the revenue of an EV parking deck. However,
their model did not take into account customer satisfaction and the impact on
power grid due to EV charging. In [121, 122, 123, 124], several algorithms
have been proposed for a power aggregator to manage EV charging loads and
submit bids to electricity market to provide regulation service (RS). Game
theory based approaches have been used to model the interplay among multiple
EVs or between EVs and power grid in [125, 126, 72, 127]. Yan _et al._
presented a multi-tier real time pricing algorithm for EV charging stations to
encourage customers to shift their charging schedule from peak period to off-
peak period [128]. Nevertheless, they did not consider that some customers may
strategically change their charging schedule in response to pricing signals.
In [129], Ban _et al._ employed multi queues to model the arrivals and
departures of EVs among multiple charging stations. Pricing signals were used
to guide EVs to different charging stations to satisfy the predefined quality
of service (QoS); but the interactions between EV charging and power grid was
not analysed in their model. A distributed network cooperative method was
proposed to minimize the charging cost of EVs while guaranteeing that the
aggregated load satisfies safety limits [130]. Their model, however, did not
incorporate renewable energy generation and consider charging demand
volatility.

In our model, we take a comprehensive view of these interweaving issues
pertaining to EV charging pricing and energy management. Specifically, we
formulate our problem to simultaneously optimize multiple objectives —
improving the profit, enhancing the customer satisfaction, and reducing the
impact on power grid in the light of renewable energy generation and energy
storage. Our model takes into account multiple uncertainties including
charging demand volatility, inherent intermittency of renewable energy
generation, and real time wholesale electricity price fluctuation. For each
type of uncertainty, an appropriate model is proposed and incorporated in the
overall optimization framework. Finally, a stochastic dynamic programming
(SDP) algorithm is employed to derive the charging prices and the electricity
procurement from the power grid for each planning horizon. Besides, SDP
algorithm has been used for water reservoir operation in [131, 132]. In terms
of the electricity retail market, a game theory based dynamic pricing scheme
is studied in [133] which also takes into account renewable integration and
local storage.

The main contributions of our work are as follows:

  * •

We proposed a multi-objective optimization framework to solve the problem, and
the solutions provide us insights into how to make a tradeoff among multiple
objectives of the profitability, the customer satisfaction, and impact on
power grid, and offer guidance to set charging prices to balance the charging
demand across the power system.

  * •

We used Newton’s method to derive a fast-computing metric to assess the impact
of EV charging on power grid, which frees us from solving the complete
nonlinear power flow equations. This metric also can be used to analyze other
electric load’s impact on power grid.

  * •

We derived the active power and reactive power sensitivities for the load
buses in a power system which can serve as a guideline for EV charging station
placement to alleviate the charging stress on the power grid.

  * •

In terms of market risk, we introduced a safeguard of profit for EV charging
service providers, which raises a warning when the profit is likely to reach a
dangerous threshold. This mechanism is beneficial for the charging service
provider to safely manage its capital and avoid severe financial losses.

###  4.3 Preliminary on Dynamic Programming

DP is an effective tool to solve complex optimization problems by partitioning
it into multiple simpler subproblems [134, 135]. DP is used to solve the
problems that have optimal substructures. Having formulated an optimization
problem with a large number of variables and constraints, we need to find an
efficient approach to solve the problem. DP takes a sequential or multistage
decision process containing independent variables and converts it into a
series of simpler subproblems, each involving only a few variables. After
solving the subproblems, we can then obtain the solution to the original
problem by combining the results of the subproblems.

####  4.3.1 Basic Model

The basic model for DP has two assumptions: (1) an underlying discrete-time
dynamic system, and (2) a cost function that is additive over time. For a
deterministic system, the system dynamics, under the influence of decisions at
the discrete instants of time, is expressed as follows

$x_{k+1}=f_{k}(x_{k},u_{k}),\;\;\;k=0,1,2,\cdots,N-1,$ (4.1)

where

  * •

$k$: index of the discrete time instant,

  * •

$x_{k}$: the state of the system at time $k$,

  * •

$u_{k}$: the decision variable at time $k$,

  * •

$N$: the total number of horizons,

and $f_{k}$ is the system state evolution function.

The cost incurred at time $k$ is denoted by $g_{k}(x_{k},u_{k})$, and the
total cost is obtained by summing the cost of all horizons

$g_{N}(x_{N})+\sum_{k=0}^{N-1}g_{k}(x_{k},u_{k}),$ (4.2)

where $g_{N}(x_{N})$ is a terminal cost incurred at the end of this process.
The optimization is taken over the control variables
$u_{0},u_{1},u_{2},\cdots,u_{N-1}$.

$J_{0}(x_{0})=\max_{u_{0},u_{1},\cdots,u_{N-1}}\left[g_{N}(x_{N})+\sum_{k=0}^{N-1}g_{k}(x_{k},u_{k})\right].$
(4.3)

Apply the state evolution function $x_{k+1}=f_{k}(x_{k},u_{k})$, we can
rewrite the optimization problem as

$J_{0}(x_{0})=\max_{u_{0},u_{1},\cdots,u_{N-1}}\left[g_{N}(x_{N-1},u_{N-1})+\sum_{k=0}^{N-1}g_{k}(x_{0},u_{0},u_{1},\cdots,u_{k})\right].$
(4.4)

Since horizon 0 does not depend on $u_{1},\cdots,u_{N-1}$, we can decompose
the optimization problem in the following way

$\displaystyle J_{0}(x_{0})$
$\displaystyle=\max_{u_{0}}\left[g_{0}(x_{0},u_{0})+\max_{u_{1},\cdots,u_{N-1}}\left(\sum_{k=1}^{N-1}g_{k}(x_{1},u_{1},u_{2},\cdots,u_{k})+g_{N}(x_{N-1},u_{N-1})\right)\right]$
(4.5) $\displaystyle=\max_{u_{0}}\left[g_{0}(x_{0},u_{0})+J_{1}(x_{1})\right]$
$\displaystyle=\max_{u_{0}}\left[g_{0}(x_{0},u_{0})+J_{1}(f_{0}(x_{0},u_{0}))\right].$

####  4.3.2 Principle of Optimality

$\mathbf{Principle\;of\;Optimality}$: Let
$\pi^{*}=\\{u_{0}^{*},u_{1}^{*},\cdots,u_{N-1}^{*}\\}$ be an optimal policy
for the basic problem. Consider the subproblem where we are at $x_{i}$ at
horizon $i$ and wish to minimize the “cost-to-go” from horizon $i$ to horizon
$N-1$

$g_{N}(x_{N})+\sum_{k=i}^{N-1}g_{k}(x_{k},u_{k}).$ (4.6)

Then the truncated policy $\\{u_{i}^{*},u_{i+1}^{*},\cdots,u_{N-1}^{*}\\}$ is
optimal for the subproblem.

A proof of the principle of optimality (by contradiction) simply states that
if the remaining decisions were not optimal then the whole policy could not be
optimal. Specifically, if the truncated policy
$\\{u_{i}^{*},u_{i+1}^{*},\cdots,u_{N-1}^{*}\\}$ was not optimal as stated, we
would be able to further reduce the cost by switching to an optimal policy for
the subproblem once we reach $x_{i}$.

The principle of optimality suggests that the optimal policy can be
constructed in a piecemeal manner. First, we construct an optimal policy for
the “tail subproblem” involving the last horizon, then we extend the optimal
policy to the “tail subproblem” involving the last two horizons, and continue
in this manner until the optimal policy for the entire problem is constructed.

###  4.4 Problem Formulation

In this study, we assume that an EV charging service provider operates a set
of charging stations within a large region. As a mediator between the
wholesale market and end customers (EVs), the charging service provider
procures electricity from the wholesale market and resells it to EVs. We also
assume that the service provider is able to harvest renewable energy (i.e.
solar or wind power) and save it in an energy storage system. An overview of
the EV charging service provider’s model is illustrated in Fig. 4.1.

Figure 4.1: The EV Charging Market

####  4.4.1 Profit of Charging Service Provider

In the United States, the Independent System Operator (ISO) or the Regional
Transmission Organization (RTO) collects supply offers from power plants and
demand bids from load serving entities (LSEs) or market participants,
calculates the day-ahead wholesale prices and real time spot prices,
coordinates and monitors the economic dispatch of electricity across a vast
region [136, 137, 138]. We assume that the charging service provider is an
LSE, who purchases electricity from the wholesale real time market and resells
it to EVs. Let $\mathcal{S}=\\{s_{1},s_{2},\cdots,s_{L}\\}$ denote the
charging stations operated by the service provider. A day is divided into $K$
planning horizons. At the start of each horizon, the service provider will
publish new charging prices during this horizon. Price differentiation is
allowed across charging stations. Let
$\mathcal{P}=\\{p_{k1},p_{k2},\cdots,p_{kL}\\},k=1,2,\cdots,K$ denote the
charging prices in the $k$-th horizon, and $o_{k}$ denote electricity
procurement from the wholesale real time market. We use wholesale real time
electricity market prices in our theoretical analysis. Let
$\mathcal{C}=\\{c_{1},c_{2},\cdots,c_{K}\\}$ represent wholesale real time
electricity prices. In addition, we assume that the service provider has an
energy storage system with capacity $E$ MWh. Let $I_{k}$ denote the
electricity in the storage at the beginning of the $k$-th horizon, and $u_{k}$
be the renewable energy generation during the $k$-th horizon. The profit made