Non-cooperative Optimization Algorithm of Charging Scheduling for
Electric Vehicle
Miyu Y
OSHIHARA∗, Mohamad H
AFIZULAZWAN MOHAMAD NOR∗, Akari K
ONO∗,
Toru N
AMERIKAWA∗, and Zhihua Q
U∗∗Abstract : In this paper, we aim to propose a charging scheduling algorithm for highway driving of electric vehicles. While the number of electric vehicles has been increasing recently, charging stations are not becoming widespread com-pared to gas stations. The distance that an electric vehicle can run on one charge is only around 120 km to 400 km. Therefore, it is necessary to plan to recharge in advance when driving long distances. Problems related to planning algo-rithms are called charging scheduling problems of electric vehicles. In this paper, we assume that there is no difference in the power of the electric vehicle and the charging station, and consider the situation where each acts to maximize its own profit. First, because the electric vehicle freely selects the charging station, we solve the optimal allocation problem of the electric vehicle to charging station using matching theory. Furthermore, we consider non-cooperative game theory for situations where electric vehicle and charging stations act to maximize only their own interests. The effectiveness of the proposed non-cooperative charging scheduling algorithm is confirmed by numerical simulation.
Key Words : charging scheduling, electric vehicle, matching theory, game theory.
1. Introduction
In recent years, the development of electric vehicles are pro-gressing due to environmental problems. Compared to conven-tional cars, electric vehicles have a remarkably short distance to travel with one charge. Therefore, when traveling over long dis-tance, it is necessary to plan the location and time of charging in advance. This planning problem is called charging scheduling problem of electric vehicle. Many algorithms were proposed using technology called Intelligent Transport System (ITS) and it is actively progressed as a solution to the scheduling problem. ITS utilizes Information Communication Technology (ICT) to integrate and cooperate with people, road infrastructures and vehicles, which is based on real-time traffic information ob-tained in order to solve problems related to road traffic man-agement, advanced operation, efficiency, and other traffic re-lated issues [1]. As a result, it is also expected to contribute to solving various problems such as alleviating traffic congestion, effective use of networks, improvement of safety, improvement of fuel consumption, and environmental preservation. In par-ticular, the Electronic Toll Collection system (ETC), which is the core technology of ITS, has brought about a great effect on the elimination of tollgate congestion in urban expressways [2]. In some parts of Europe and the United States, the electric ve-hicle needs to charge battery by paying an additional fee other than the electricity charge, and the extra price can be freely
∗
Department of System Design Engineering, Keio Univer-sity, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223-8522, Japan
∗∗Department of Electrical and Computer Engineering,
Univer-sity of Central Florida, Orlando, FL32816, USA E-mail: [email protected], [email protected], [email protected], [email protected], [email protected] (Received xxx 00, 2011) (Revised xxx 00, 2011)
decided by the charging station operator [3]. Based on the in-formation obtained by the ITS, it becomes possible to change the price in real time. Thus, as the number of charging stations increases, price competition between stations is expected to in-tensify, and station managers need to find pricing methods that maximize their revenue. Furthermore, when many electric ve-hicles concentrate on one charging station, the station manager will lose the profit, so it is desirable that the usage rates of all the charging stations become uniform. In other words, the sta-tion manager not only maximizes the profit by selling energy to the electric vehicle, but also aims to place the electric vehicle at the station desirably. On the other hand, the owner of the elec-tric vehicle selects the charging station according to his own purpose. Here, it is necessary to consider the situation where electric vehicles behave selfishly and compete with each other, and the amount of energy to be charged varies depending on the characteristics of the electric vehicle.
Various researches were conducted on the charging schedul-ing problem. Work in [3] dealt with the problem where the elec-tric vehicles select charging stations according to the price and distance. Further, prices are decided by the charging stations using game theory. Some drawbacks of this work are electric vehicles perform non-cooperative scheduling but they remain only in comparison between two charging stations, the mech-anism of determining the energy demand of electric vehicles was not provided in the algorithm, and no theoretical analysis on the equilibrium point in the game theory. In [4], cooper-ative distributed charging scheduling algorithm was proposed. They modeled the transition of the number of electric vehicles in the charging station by queuing theory and the problem of balancing the utilization of each charging station was solved by a consensus algorithm. At this time, there is a strong assump-tion that the vehicles are uniformly fully charged in charging station and scheduled in cooperation with each other. Further-more, it was not taken into consideration that the electric vehi-JCMSI 0001/11/0401–0001 c 2011 SICE
cle selects each charge station arbitrarily. In [5], they dealt with the charging problem of electric vehicles on highways but as-suming that deriving the waiting time is extremely difficult. The optimization problem of the driver’s selection was solved by us-ing the optimized route searchus-ing algorithm which is called the A* algorithm. In [6], they formulated assignment problems of electric vehicles and dynamic pricing of multiple stands. They solved the problem of minimizing the waiting time by introduc-ing the queue in the model of the station but the electric vehicle just reacts to the price and determines the behavior as well as concerning the energy demand. In [7], they dealt with Stack-elberg games where charging stations are leaders and electric vehicles are multiple followers, but there was no equilibrium analysis provided. The Stackelberg game used in some pa-pers require an assumption that there is a difference between the amount of information of the electric vehicle and the charg-ing station. In other words, the chargcharg-ing station knows all the personal information of the electric vehicle. This condition is unrealistic. Furthermore, although queuing model has been in-troduced by setting Poisson distribution as the occurrence prob-ability of electric vehicle demand but the model did not particu-larly consider waiting time. In [8], they dealt with the charging problem on the general road when the behavior of the electric vehicles are affected by waiting time as well as considering the case where the energy price is determined dynamically. The problem is that the charging stations are non-cooperative and do not consider waiting time. Queuing theory was used in var-ious studies such as modeling the traffic flow at a signalized intersection. Besides using the queuing theory to model the in-flow and outin-flow of electric vehicles at the charging stations which is handled in this paper, research and practical applica-tion also has been actively carried out in the United States in recent years [9] to provide the theoretical analysis of the smart parking system.
In this paper, we aim to propose a hierarchical uncoopera-tive optimal charging scheduling algorithm with the aim of lev-eling the utilization rate of charging stations and maximizing the profit only for themselves, i.e., charging station and elec-tric vehicle with the following contributions: 1) to express the charging station selection of electric vehicles using matching theory and propose a matching algorithm; 2) propose a charg-ing schedulcharg-ing algorithm uscharg-ing repetitive game which regards the charging stations and electric vehicles as non-cooperative players; 3) the equilibrium in repetitive games is generally dif-ficult to theoretically analyze and many of them have problems such as staying at numerical solution [7]. Therefore, the third contribution of this research is to theoretically derive the con-ditions and equilibrium points to achieve equilibrium against such a problem.
The remainder of this paper is structured as follows. In Sec-tion 2, we briefly describe the system model which is the re-quirement of this research. Then, we discuss the traffic flow model for the electric vehicle to enter and exit the charging sta-tion, the queuing model for the electric vehicle to charge their battery, and the state of charge of the electric vehicle. In Sec-tion 3, we present about our proposed non-cooperative charg-ing schedulcharg-ing algorithm which is based on matchcharg-ing theory and repetitive game. First, we address the problem of decid-ing which driver to charge at which station by matchdecid-ing theory. Second, the matched electric vehicle and charging station
de-termine the energy demand and energy price to maximize their own profit by using repetitive game. Third, we analyze that the energy price converges to the final equilibrium price by repeat-ing the iteration which solves the problem of maximizrepeat-ing the individual (charging station and electric vehicle) utility. In Sec-tion 4, we validate the proposed algorithm by numerical sim-ulation. Finally, we provide the conclusion of the paper and future works in Section 5.
2. Problem formulation
In this section, we briefly discuss about the system model, the model of the traffic flow, the queuing model of the elec-tric vehicle at charging station, and the utility functions of the charging station (CS) and electric vehicle (EV). Note that the charging station is regarded as leader while the electric vehicle is regarded as follower in this paper.
2.1 System model
An overview of the system model used in this research is shown in Fig. 1. Each CS belongs to the same business op-erator and exchanges information with each other. When CS scheduling interval is assumed to be T , each station presents the charging price to each vehicle at the scheduling time k = nT (n = 1, 2, . . .). The exchange of information between EV and CS can be achieved through vehicle-to-infrastructure (V2I) and infrastructure-to-vehicle (I2V) communications. In addition, each EV communicates with other neighboring EVs through vehicle-to-vehicle (V2V) communication to determine their de-sired charging demand while maintaining a non-cooperative be-havior towards other EVs. Note that setting up such communi-cation network is reasonable considering that most of the CSs are connected to the network for paying credit cards and car navigation systems are installed in EVs.
Fig. 1 System model
2.2 Traffic flow
The first component of the model describes the flow of EVs on the highway as shown in Fig. 2. From the figure, the in-terchange is represented by node i = 0, 1, ..., N where N is the total number of nodes. We consider a chain topology in which node i is connected only with the nodes of i − 1 and i + 1. Thus, edges represent visual links between two successive entrances and exits of the interchange.
Let α(k) be the average of EV flow arriving at a node i, which is given by (1)
Fig. 2 Traffic flow model αi(k) = ( γi(k), if i = 1 γi(k) + yi−1(k − di−1,i), if i , 1 (1) where γi(k) is the exogenous flow entering the chain network at node i at time k, yi−1(k) is average EV flow coming from node (i − 1) to node i, di−1,iis the time required for an EV to traverse the edge from node i−1 to node i. The number of EVs departing from node i, yi(k), can be written as follows:
yi(k) = αi(k) + gi(k) − fi(k), (2) where gi(k) represents EV flow coming out from charging sta-tion i, and fi(k) represents EV flow entering to charging station i. In the next subsection, we will explain the relationship
be-tween gi(k), fi(k), and xi(k) from Fig. 2.
2.3 Queuing model
We model the queue at each CS. Let xi(k) be the number of EVs currently being served or in the queue at CS i.
xi(k + 1) = xi(k) + fi(k) − gi(k) (3) where fi(k) is the number of vehicles flowing into the CS which is decided by EV allocation algorithm and gi(k) is the num-ber of outflow vehicles. However, even if scheduling is done, the time distribution at which the vehicle arrives cannot be de-termined precisely. Rather, the distribution itself of the event ”vehicle arrives” follows the Poisson distribution. Also, it is not possible to schedule exactly how much EV actually stays at CS. Based on these observations, we use the M/M/ci queu-ing model. In [4] and [9], the chargqueu-ing station and the parkqueu-ing lot are modeled by queuing. Kendall’s notation, i.e., M/M/ci is used to define the queue. It means distribution of customer arrival time / distribution of service time / number of contacts, respectively. M means the exponential distribution, where the number of chargers for CS i is ci. Furthermore, let λibe the average arrival rate of customers at every sampling time and µi be the average service rate at every sampling time. Then, the following assumption is introduced.
Assumption 1. The customer’s average arrival rate is no larger than the average service rate. Hence, λi< ciµi. 2.3.1 Approximation of gi(k)
In order to obtain xi(k), it is necessary to calculate gi(k) first. From the steady solution of M/M/ci,
xi= ρcii+1 cici! 1 1 − ρi ci !2ϕi,0+ρi (4) ϕi,0= ci−1 X n=0 ρn i n!+ ρcii ci! 1 − ρi ci ! −1 (5)
where ρi = λi/µi. From equation (3), when steady state is achieved, gi= fi=λi. Substituting this solution into the equa-tions (4) and (5) yields
xi= gcii+1 µcii+1cici! 1 1 − gi µici !2ϕi,0+ gi µi , (6) ϕi,0= ci−1 X n=0 gn i µn in! + g ci i µciici! 1 − ρi ci ! −1 . (7)
We could derive the relationship between gi(k) and xi, however it is impossible to solve gi(k) from (6) and (7). Instead, if ci= 1, the steady solution can be written by following equation:
xi= gi µi− gi =⇒ gi=µi xi 1 + xi (8) In this paper, we approximate giby considering M/M/cias ci× M/M/1: ˆgi(xi) = ciµi xi 1 + xi (9) 2.4 EV energy model
This subsection we model the power consumption of the EVs, which is given as
e−v,i+1= e+v,i− di,i+1r−v, (10) e+v,i= e−v,i+Ev,i
µv
, (11)
where e−v,i+1is the state of charge (SOC) when the generic EV
v arrives at node i + 1, and e+
v,i indicates the SOC when EV v leaves the node i. Since the time required to move from the node i to node i + 1 is di,i+1, r−v is the SOC required for unit time running. Hence, di,i+1rv−represents the amount of charge consumed to move from node i to node i + 1.
The equation (11) shows the SOC of the EV departing from node i. Ev,iis the amount of energy that EV v charges at node i, and µvis the battery capacity. Each EV bids the desired amount of charge to the CS, whereas the CS independently set prices to maximize their individual profits.
The charging strategy of each EV satisfies the following two constraints:
Eminv,i ≤ Ev,i≤ Emaxv,i , (12) e−v,i+Ev,i
µv
≤ 1. (13)
Inequalities (12) are the upper and lower bounds of the amount of energy that an EV can charge at CS, and inequality (13) de-scribes the fact that the SOC cannot exceed 100%.
2.5 Utility function of electric vehicle
Utility function of EV v, Uk
v,i represents the benefit that the EV obtains through buying energy from charging station. Mathematically, the function is defined as follows:
Ukv =µvEv,i(k) − 1
2θv,i(k) Ev,i(k) 2
− pv,i(k)Ev,i(k)− pv,i(k)
Ev,i(k) − ¯Ei(k)
where ¯Ei(k) is the average energy demand of all EVs and pv,iis the price of energy at node i. In addition, θv,i(k) is
θv(k) = 1 µv− e−v(k) P k 1 µv− e−v(k) ! . (15)
The equation (15) shows a satisfaction parameter indicating the measure of satisfaction of EV v obtained by charging a unit of energy with CS i. For example, if EV v has a higher need for energy demand than EV v + 1 (e.g., it is going to travel farther, has a larger battery, etc.) then EV v is the same to achieve satisfaction, more energy is required than EV v + 1. Therefore, it becomes θv(k) ≤ θv+1(k).
2.6 Utility function of charging station
The utility function of CS i is:
Qki =X v
pv,i(k)Ev,i(k) − a1
X v Ev,i(k) 2 −a2 2 pv,i(k) − p 2. (16)
p is the average market price for charging and a1and a2denote
the weighting factors of each term. The first term is the profit of the charging station, the second term is the energy supplied, and the third is the term relating to the difference between the general market price p of the charging with its own set price
pv,i(k). Considering the situation where the EV driver selects the charging station after knowing the charging price market, the charging station determines the difference between the mar-ket price p and set the price pv,i(k) as small as possible. By doing so, the utility is maximized. The optimal price is larger than the market price p, and if it exceeds the optimal price, the utility decreases because the difference from p in the third term increases.
2.7 Control objective
Each of the CSs aim to gain profits by selling energy to the EVs while operating the station efficiently. If many EVs line up at a specific CS, it causes not only congestion and service degradation but also neighboring CSs that are under-utilized are wasteful of resources. Therefore, the primary goal is to appro-priately distribute EVs by changing the charging price at each CS so that the usage rate of each CS becomes uniform. The second goal is to further maximize profits by selling energy. Meanwhile, the EV aims to charge the desired amount energy while competing with other EVs.
Optimization of this cyber-physical-human system which is called as a charging scheduling algorithm is proposed using Stackelberg game for this system. In the Stackelberg game, EVs and CSs are treated as players and mutual exchanges are expressed as games. The result of the non-cooperative charging scheduling algorithm using Stackelberg games must satisfy the goal of the CS and the purpose of the EV.
3. Non-cooperative charging scheduling algorithm In this paper, we divide the scheduling problem into two cat-egories. First is to determine which charging station the EV needs to enter and the second one is to determine on how much
each EV needs to charge at the CS. The details are provided as follows:
1. The CS determines the number of EVs to be scheduled in order to make the waiting time uniform ( uniform utiliza-tion rate)
2. EV determines the preference for charging station by wait-ing time and own SOC.
3. The CS determines the preference for the EV according to its own situation.
4. Perform matching.
5. Once the CS and EV pair are decided, energy demand and price are determined by using Stackelberg game.
3.1 EV allocation problem
3.1.1 Uniformity of waiting time
At the steady state condition of M/M/ci, the probability of n customers existing in the system of traffic intensity ρi= λµi
i is Pn= P0ρni 1 n!, (0 ≤ n ≤ ci) P0ρni 1 ci!cn−cii , (n ≥ ci) (17) P0= ci−1 X n=0 ρni 1 n!+ρ ci i 1 ci 1 1 −ρi ci −1 . (18)
When a customer arrives at the CS, the probability that the cus-tomer will wait into queue is equal to the probability of all ci contacts are occupied. That is,
E2,ci(ρi) = ∞ X n=ci Pn = ci ci− ρi Pci = ρcii ci ci ci− ρi 1 + ρi+ ρ2i 2! +· · · + ρcii−1 (ci− 1)! +ρ ci i ci! ci ci− ρi This equation is called Erlang C formula. Using the equation, the average waiting time in this system Wican be written by
Wi= E2,ci 1 µi(ci− ρi)
. (19)
In order to equalize the waiting time at each CS, we can control λiso that (19) is equal at each station. In order to solve for opti-mal value of λi, it is obvious thatPk fi(k) =P λiwhen infinite intervals are considered. Using this concept, we consider how many EVs should be charged at a scheduling time in order to equalize the waiting time.
Let the assumed time horizon be Hp. At this time, the CS solves the following problem and determines the optimum charging permitted number fi∗(k) at the k step.
fi∗(k) = arg min fi(k),i∈Nmaxi Wi (20) s.t. λi= 1 Hp H p−1 X l=0 fi(k − l) (21) Wi= ρcii ci ci ci− ρi 1 + ρi+ ρ2 i 2!+· · · + ρcii−1 (ci− 1)! +ρ ci i ci! ci ci− ρi × 1 µi(ci− ρi) (22) X i fi(k) = X i γi(k) (23) 3.1.2 EV preference
In this paper, we will consider the optimum allocation of EVs to the CS using matching theory. First, in the matching theory, preferences is defined as follows.
Definition 1. On set X, preference of player i, iis a binary
relation on X that satisfies the following condition. 1. x ix, ∀x ∈ X
2. [x iy and y iz] ⇒ x iz, ∀x, y, z ∈ X 3. x iy or y ix, ∀x, y ∈ X
x ≺i y indicates that player i prefer y more than x under the preference of individual i.
Each EV considers the choice of CS under the following con-ditions:
• SOC at the arrival of the CS (lower is preferable, but it is not an option if it becomes 0 or less).
• Estimated waiting time (smaller is preferable).
• Other factors such as personal preference and tolerance level, etc.
Let’s set the current SOC of EV v at node i0as e0
v,i0. At this
time, in determining the preference, the evaluation function of EV v to CS i can be written as follows.
Jiv= ω1ˆe−v,i+ω2Wi+ω3, if ˆe− v,i> 0 ω4, (otherwise) (24)
ˆe−v,i= e0v,i0−
i−1 X
j=i0
dj, j+1r−v. (25)
The first term of (25) indicates the estimated SOC when arriv-ing at CS i, the second term is related to waitarriv-ing time, and the third term is other factors. ω1, ω2, ω3are appropriate weights.
ω4 ≫ 0 is a penalty to CS i which cannot be reached without
charging. In this paper, by setting ωvto be preference for itself of EV v, we set 0 ≪ ωv < ω4to avoid matching with CS that
cannot be reached without charging.
Since EV v is the preferred CS i in descending order of the evaluation function in (24) and (25), we calculate it for each i and decide the preference vector Pivby obtaining the index i in ascending order. Here, we introduce assumption 2.
Assumption 2. All EVs have an initial SOC that can reach at least the nearest CS when entering the highway.
Hence, each EV has one CS that is more favorable than it at least.
3.1.3 CS preference
Charging stations have no requirement for EVs in particular, but for EVs that can not reach the next CS unless charging, charging must be permitted. Let the next available CS of CS i be i′, then the evaluation function for EV v can be written with the following equation:
Jiv= χ1 if ˆe− v,i′ < 0 χ2 if ˆe− v,i< 0 χ3 (otherwise) (26)
where χ1 ≪ 0, χ2 ≫ 0, χ1 < χ3 < χ2. The first condition
of (26) indicates that the EV cannot reach the next CS without charging and the second condition means that the EV cannot reach the CS i. For CS i, the EV v is not subject to scheduling is equivalent to not matching with that EV. We set the evaluation function value of CS i to itself as χi. By setting the condition of χito χ3 < χi< χ2, it is possible to exclude matching with the
EV that is not subject to scheduling.
Since the smaller the evaluation function Jv
i is better for EV, so we calculate the function in order and obtain the index v to decide the CS preference vector Pv
i. Here, we introduce the following assumption to discuss the stability of matching. Assumption 3. At scheduling step k, the number of EVs with ˆe−v,i′< 0 in CS i is always equal or smaller than fi∗(k).
3.1.4 EV allocation algorithm based on matching theory Consider allocating CS i for each EV using matching theory based on the determined preference. After preferences are de-cided, there are several algorithms to decide actual matching. In general, matching theory has a problem where the number of iterations increases exponentially as the scale of the problem gets bigger. Even the number of iterations is low, there is a possibility that the stability of matching cannot be guaranteed. Algorithm 1 Charging station allocation algorithm
Require: f∗
i(k), Piv, Pvi,and a strongly connected communication topology
between EVs and CSs. 1: Initialization: Set initial Xk′={}
2: for v = 1, 2, . . . ,P iγi(k) do
3: EV v applies for charging to CS i with the most preference from Pi v.
4: if |X′
k(i)| < f
∗
i(k) then
5: CS i accepts EV v and forms a temporary pair X′
k(i). 6: Update X′ k(i). 7: end if 8: if |X′ k(i)| = f ∗
i(k) and v ≻iX′k(i) then
9: CS i resolves pair with v′such that v′ = X′
k(i) and accepts the
application of EV v. 10: Update X′
k(i).
11: Exclude CS i from v′preference and update Pi v′.
12: Set v → v′and restart from step 3.
13: end if
14: if |X′
k(v)| = f
∗
i(k) and v ≺iXk′(i) then
15: Exclude CS i from v preference and update Pi v.
16: Restart from step 3.
17: end if
18: end for 19: X(k) = X′(k)
The scale of the problem is not so large in this paper and therefore, Gael-Sharpley algorithm which is superior in terms of stability is used even though the number of times of search-ing is larger than the other algorithms [14]. We denote Xk as
the final matching set in step k and Xk′ as a set of temporary matching in Algorithm 1.
3.2 Energy demand and price decision problem
In this section, we consider the problem of determining the energy price and the energy demand by interchanging the allo-cated CS and EV.
At time k, EVs that move toward the CS i which has ci charger is expressed as Fi(k) := {1, . . . fi(k)}. EV can deter-mine the optimal energy demand Ev,i(k), and CS can achieve a reasonable price. The set of energy demand of the target EV is expressed as E(k) = [E1,i(k), . . . , EK(k),i(k)].
In this regard, when the EV informs the CS of the energy demand, the CS presents the charging price to the EV so that it can maximize its own benefit, the electric vehicle provides the charging price and again declares the energy demand that will maximize its utility. Therefore, this problem is formulated as a repeated game of one leader and multiple followers, i.e., a non-cooperative game. An illustration is shown in Fig. 3. The leader here simply refers to the player who acts ahead.
Fig. 3 Illustration of Stackelberg game
3.2.1 Follower action
According to the utility function of the EV (follower) dis-cussed previously, the behavior of EV v that corresponds to the presented price pi(k) can be written as follows.
max Ev,i(k)U
k
v,i (27)
s.t. Eminv,i ≤ Ev,i≤ Emaxv,i (28) To solve this problem, the Lagrangian function at time k and EV v are as follows.
Lkv=νvEv,i(k) − 1
2b1θv(k)(Ev,i)
2(k) − b
2pv,i(k)Ev,i(k) − b3Ev,i(k) 1 ¯ν fi(k) − 1 νv ! − κv(k)
Eminv,i − Ev,i(k)
− λv(k)
Ev,i(k) − Emaxv,i
(29) where κv(k), λv(k) are non-negative Lagrange multipliers for constrain equations (12) and (13) where they are updated by using gradient method. At the optimum, ∂L
k v
∂Ev,i(k) = 0 is satisfied, then we get optimal energy demand as
E∗v,i(k) = 1 b1θv νv− b2pi− b3 1 ¯ν fi(k) − 1 νv ! + (κv(k) − λv(k)) ! . (30) 3.2.2 Leader action
From the utility function of the CS (leader) discussed previ-ously, the optimization problem for the CS can be written be-low.
max pi(k) Q
k
i (31)
In order to maximize its utility, the CS presents the optimal price p∗
i(k) to the EV based on the demand response of E
∗(k)
from all EVs, i.e., ∂Qi ∂pi(k) =X v Ev,i(k) − a2(pi(k) − p) (32) By setting ∂Qi
∂pi(k) = 0, the optimal energy price is p∗i(k) = P vEv,i(k) a2 + p (33) 4. Numerical Simulation
Numerical simulation was performed to confirm the effec-tiveness of the proposed algorithm. A simulation area was cre-ated between Japanese New Tomei Expressway Ohi Matsuda Interchange and Suruga Bay Numazu Interchange, and a sim-ulation map was created as in Fig. 4. The circle indicates the interchange and the square indicates the service area. Black numbers between nodes mean traveling time and red numbers show the number of charging stations in each service area. The number of vehicles inflow from outside of model is shown in Fig. 5 and the battery capacity of all vehicles and the initial SOC when inflowing are shown in Fig. 6.
Fig. 4 Simulation map
Simulation was performed by using parameters in Table 1. From Fig. 7 and Fig. 8, it can be confirmed that the inflow-ing EVs are allocated to each charginflow-ing station without leakage. Also, as a result of the allocation of EV, the graph of Fig. 9 and Fig. 10 which indicate the estimated waiting time are almost in agreement and therefore, the waiting time equalization prob-lem is correctly explained. From Fig. 11 and Fig. 12, it can be confirmed that the energy demand of each EV and the energy price presented by the CS converges repeatedly in game.
5. Conclusion
In this paper, we proposed a non-cooperative optimal charg-ing schedulcharg-ing algorithm uscharg-ing matchcharg-ing theory and Stackel-berg game. First, we proposed a matching algorithm by ex-pressing the electric vehicle allocation problem. The objective
0 20 40 60 80 100 120 step 0 0.5 1 1.5 2 2.5 3 3.5 Inflow vehicle Fig. 5 Inflow 0 5 10 vehicle number 0 20 40 60 80 100
Capasity & Initial SOC
Fig. 6 Initial SOC Table 1 Simulation parameter
Parameter Symbol setting
Number of step K 120 [min]
Sampling time k 1 [min]
Scheduling interval T 15 [min]
Battery usage r−
v 0.05 [%/min]
Average service rate µi 1.1 [veh. / k]
Market price of charge p 23[yen] Utility function weight a1, a2 0.03,30 b1, b2, b3 1,0.1,0.01
Preference weight ω1, ω2, ω3, ω4 10,1,1,100
χ1, χ2, χ3 1,100,10
Initial Lagrangian multipliers κ(0) 1
λ(0) 1
Updating step size x 0.2
y 0.2
of the matching algorithm is to equalize the utilization ratio at the charging station and to assist the electric vehicle in making selection of the charging station. Furthermore, we described energy demand and energy price decision problem using Stack-elberg game and provided its solution. It was shown from the theoretical analysis and numerical simulation that the energy price converged to the final equilibrium price.
Future works include dealing with issues that consider prices as factors of the EV allocation problem. In this case, the Stack-elberg game and the matching problem are solved alternately, and it is expected that it is difficult to analyze the convergence. In addition, it is necessary to propose a problem generalizing the Stackelberg game that requires a strong assumption.
0 50 100 step 0 0.5 1 1.5 2 2.5 f 2 (k) Fig. 7 Inflow to CS 2 0 50 100 step 0 0.5 1 1.5 2 2.5 f 6 (k) Fig. 8 Inflow to CS 6 0 20 40 60 80 100 120 step 0 1 2 3 4 5 6 7 Waiting time at CS2
Fig. 9 Waiting time at CS 2 References
[1] Ministry of Land, Infrastructure, Transport and Tourism Road Bureau of Japan website: http://www.mlit.go.jp/road/road e/p1 its.html, last accessed 20 March 2019.
[2] ITS Technology Enhancement
As-sociation website:
https://www.its-tea.or.jp/english/its etc/service purposeAndEffect.html, last accessed 11 February 2019.
[3] W. Yuan, J. Huang, and Y. J. Zhang: Competitive Charging Station Pricing for Plug-In Electric Vehicle, IEEE Transaction
on Smart Grid, Vol. 8, No. 2, pp. 627–639, 2017.
[4] A. Gusrialdi, Z. Qu, M. A. Simaan: Distributed Scheduling and cooperative control for charging of electric vehicles at highway service stations, IEEE Transaction on Intelligent
0 20 40 60 80 100 120 step 0 1 2 3 4 5 6 7 Waiting time at CS6
Fig. 10 Waiting time at CS 6
0 50 100 150 200
repeated game step
20 21 22 23 24 25 26 Energy price CS A CS B
Fig. 11 Energy price (k = 120)
0 50 100 150 200
repeated game step
0 50 100 150 200 250 Energy demand EV1 EV2 EV3 EV4 EV5 EV6 EV7 EV8 EV9 EV10 EV11 EV12 EV13
Fig. 12 Energy demand
[5] V. d. Razo and H.A.Jacobsen: Smart Charging Schedules for Highway Travel With Electric Vehicle, IEEE Transaction on
Transportation Electrification, Vol. 2, No. 2, pp. 160–173,
2016.
[6] D. Ban, G. Michailidis, and M. Devetsiliotis: Demand Re-sponse Control for PHEV Charging Stations by Dynamic Price Adjustments, Proc. of Innovative Smart Grid Technologies, pp. 1–8, 2012.
[7] I. S. Bayram, G. Michailidis, and M. Devetsikiotis, Unsplit-table Load Balancing in a Network of Charging Stations Under QoS Guarantees, IEEE Transaction on Smart Grid, Vol. 6, No. 3, pp.1292–1302, 2015.
[8] J.tan and L. wan: Real-Time Charging Navigation of Electric Vehicle to Fast Charging Stations: A Hierarchical Game Ap-proch, IEEE Transaction on Smart Grid, Vol.8, No. 2, pp.846– 856, 2017.
[9] L.J. Ratliff, C. Dowling, E. Mazumdar, B. Zhang: To Observe
or Not to Observe: Queuing Game Framework for Urban Park-ing, IEEE Conference on Decision and Control, pp.5286–5291, 2017.
[10] H. Yang, X. Xie, and A. V. Vasilakos: Noncooperative and Co-operative Optimization of Electric Vehicle Charging Under De-mand Uncertainty: A Robust Stackelberg Game, IEEE
Trans-action on Vehicular Technology, Vol. 65, No. 3, pp.1043–1057,
2016.
[11] F. Facchinei and C. Kanzow: Generalized Nash equilibrium problems and Newton methods, Mathematical Programming, Vol. 117, No. 1–2, pp.163–194, 2007.
[12] D. Ardagna, B. Panicucci, and M. Passacantando: A Game Theoretic Formulation of the Service Provisioning Problem in Cloud Systems, Proc. of World Wide Web Conference, pp.177– 186, 2011.
[13] M. V. Solodov and B. F. Svaiter: A New Projection Method for Variational Inequality Problems, SIAM Journal on Control and
Optimization, Vol. 37, No.3, pp.765–776, 1999.
[14] David Gale, Lloyd S. Shapley: College Admissions and the Stability of marriage, The American Mathematical Monthly, Vol.69, No.1, pp.9–15 1962.
[15] T. Basar and G. J. Olsder: Dynamic Noncooperative Game
Theory, 2nd Edition, SIAM, 1999.
[16] Dario Bauso: Game Theory with Engineering Applications, SIAM, 2016.
Miyu YOSHIHARA
She received the B.E. degree in system design engi-neering from Keio University, Kanagawa, Japan, in 2017. She is currently pursuing the M.E. degree at Keio Uni-versity, Kanagawa, Japan. Her research interests include control systems, and charging scheduling problem for electric vehicle.
Mohamad HAFIZULAZWAN MOHAMAD NOR
He received the B.Eng. and M.Phil. degrees in elec-tronic systems engineering from the Universiti Teknologi Malaysia (UTM), Kuala Lumpur, Malaysia, in 2015 and 2017, respectively. He is currently a full-time Ph.D. stu-dent at Keio University, Kanagawa, Japan. His current research interests include connected and automated vehi-cles and multi-agent systems.
Akari KONO
She is currently pursuing the B.E. degree in system de-sign engineering at Keio University, Kanagawa, Japan. Her research interests include charging scheduling prob-lem for electric vehicle.
Toru NAMERIKAWA(Member)
He received the B.E., M.E., and Ph.D. in electrical and computer engineering from Kanazawa University, Japan, in 1991,1993 and 1997, respectively. From 1994 until 2002, he was with Kanazawa University as an Assistant Professor. From 2002 until 2005, he was with the Na-gaoka University of Technology as an Associate Profes-sor, Niigata, Japan. From 2006 until 2009, he was with Kanazawa University again. In April 2009, he joined Keio University, Yokohama, Japan, where he is currently a Professor at Department of Sys-tem Design Engineering, Keio University. He held visiting positions at Swiss Federal Institute of Technology in Zurich in 1998, University of Cal-ifornia, Santa Barbara in 2001, University of Stuttgart in 2008 and Lund University in 2010. He received 2014 Pioneer Technology Award from SICE Control Division and 2017 Outstanding Paper Award from SICE. His main research interests are robust control, distributed and cooperative control and their application to power network and transportation network systems. He is a member of IEEE CSS and ISCIE.
Zhihua QU
He received the Ph.D. degree in electrical engineer-ing from Georgia Institute of Technology, Atlanta, in 1990. Since then, he has been with University of Cen-tral Florida, Orlando. He is currently the SAIC En-dowed Professor with the College of Engineering and Computer Science, a Pegasus Professor and the Chair of Electrical and Computer Engineering, and the Director of FEEDER Center (one of DoE-funded centers on distributed technologies and smart grid). His areas of expertise are nonlinear systems and control, with applications to energy and power systems, low-speed power genera-tion, dynamic stability of distributed power systems, anti-islanding control and protection, distributed generation and load sharing control, distributed VAR compensation, distributed optimization, and cooperative control. He serves as the Chair of the IEEE CSS Technical Committee on Smart Grid and an IEEE Distinguished Lecturer.
