A Study of the Analytical Method for the Location
Planning of Charging Stations for Electric Vehicles

Hisatomo Hanabusa1 , Ryota Horiguchi1
1i-Transport Lab. Co., Ltd.,
3F, Jimbocho1-4BLDG, Kanda Jimbocho 1-4, Chiyoda-ku, Tokyo, 101-0051, Japan{hanabusa, rhoriguchi}@i-transportlab.jp

Abstract. This study describes an analytical method for the location planningof charging stations for electric vehicles (EVs). EVs are expected to help CO2
reduction and to improve road environment such as noise level. In this paper,
the theoretical framework of the optimum location of charging stations isexplained. We assume that the number of charging stations to install and thebasic performance are given. This framework has the base of the traffic
assignment technique with Stochastic User Equilibrium (SUE) and its
optimization will be achieved with the idea of the entropy maximization.

Keywords: Electric Vehicle, Charging Station, Stochastic User Equilibrium
Assignment, Entropy Maximization

1Introduction

The purpose of this study is to develop an analytical method for the location
planning of charging stations for electric vehicle (EV)s. This method optimizes thelocations of charging stations considering the route choice behavior of EV drivers andthe spatial distribution of the electric demand from EVs. The optimization here isaiming that the travel cost of each EV including its charging time is to be minimized
and that the electric demand for each charging station is to be equalized.
In recent years, the performance of EV has been suitable for practical use such asbattery capacity. EV is needed electronic power and used electric motors to drive.
Thus it is said that the CO2 emission by driving can be zero because EV is not usedgasoline engine. In addition to this, the noise level of electronic motors of EV is lower
than the engine of gasoline-powered vehicle. Therefore EV is expected to help CO2
reduction and to improve road environment such as noise level. Generally, themaximum driving range of EV is limited comparing to gasoline-powered vehicles.
And it is also said that the way and the location to refill the energy of EV (electricity)
can be different from the way of gasoline-powered vehicle (gasoline). Furthermore,the charging time of EV is longer than that of gasoline-powered vehicle. Therefore,
the behavior of the EV driver will be affected by the location of charging stations.
The location planning of charging stations will be a serious issue as the market of EV
growing in the future. Many existing studies concerned with the charging station planningfocused only on the minimization of EV users' cost [1] [2] [3] [4]. For example, Koyanagi et al.
the analytical location planning method to optimize the accessibility to the public transport
station, main road, parking lot and shopping center [1]. However, it is rarely discussed about
the location optimization from the viewpoint of the power supply side. We need to aware of thepossibility that if the balance of the power supply is unstable, some charging station is not able
to supply enough and the re-planning of the electric infrastructure is needed.

. In this study, we try to harmonize those two objectives, i.e. the equilibrium ofusers' costs and the equalization of the electric demand for each charging station in
the location planning. In section 2, we discuss about the formulation of the location
planning of charging station using examples from some past studies. In section 3, theassumption of the driving behavior of EV is discussed for the formulation, and weshow the framework of the optimum location method of charging station in section 4.
In section 5, the case study applied the method. Finally, we conclude this paper
through the result of the case study and show the future works in section 6.

2

Development principles for the optimum location method

Before the development of the optimum method of charging station, we review thepast studies and consider the principle of the formulation.
There are many studies about optimum location method. These studies applied
the approach from mathematical programming. To develop the optimizing model, avariety of optimization method is applied including Meta-heuristic Methods such as
Genetic Algorithms and Neural Networks [5]. Other some are coming from the fieldof physics such as perturbation theory [6]. According to some studies developed theoptimum location methods, these methods are considered the factors to impact thefacilities such as demand of customers, population, distances from the facilities. For
example, Furuta et. al. [7] describes the optimum location method of commerce
facility considering the behavior of customer. They assumed the relationship between
the purchasing power of customer and the facilities which compete in sales. Berman[8] describes a solution for the flow-demand facility location problem based on thesituation that customers travel (go shopping etc.) with several purpose who can bechanged the original trip. Basically, the optimum location method for charging station
can also be applied to same analytical steps. And most of these methods are
considered to minimize the distance to destination or the cost such as money, travel
time and waiting time.
In this study, we focused on the factor associated with the location planningwhich is assumed from the characteristics of EV and formulate the optimum location
planning for charging station considering the following issues.
1) The size of the target area issued in this method will cover a city-scale network
which covers the trips in daily activities.

2)

The number of charging stations to install and their charging performance(number of charger and charging rate) are given as inputs.
3) The demand of EVs to each charging station can be calculated using the traffic
assignment algorithm assuming the route choice behavior of EVs from origin
to destination we assumed.
4) The route cost from origin to destination consists of the travel time and thewaiting time at the charging station. The location of charging station isdecided such that the route cost of each EV is minimized and each charging
station is maintained a certain distance.

3

Route choice behavior of EV and charging station

In this section, let us summarize the feature of EV and the charging station for theformulation.
An EV consumes electricity stored in the battery in proportion to its travel
distance. EV users can charge their EVs at their home, any charging stations, theiroffices, shopping centers and so on. EV is needed to charge the battery before whenState of Charge (SOC) reaches to zero. SOC can be regarded as a fuel gauge for thebattery. If EV is needed to charge on the way to the destination, the route might bechanged to charging station. Therefore, we assume that there are three behaviors of
EV to the destination. Fig.1 shows the behavior of EV to the destination.

Fig.1. Behavior of EV to the destination
The issue we should focus on is the waiting time at charging station. The waitingtime can be formulated as the M/M/1 queueing theory from the relationship between
the electric capacity of charging station and the electric demand of EV for charging.
Let e gx denote the supply rate of the charger g in the charging station x. The electric
capacity rate of the charging station E xsh per unit time h is formulated the following
equation:

Exsh   egxh(1)g G x

Where Let G x the set of charger of the charging station x. On the other hand, theelectric demand can also be formulated from the characteristic of EV (in Fig.1). It is
assumed that EV is charged the energy to the destination or the next charging station.
next
Let d kx h denote the distance to the destination or the next charging station x next
along the route k. Let f kxh denote the number of EV via the charging station x along
the route k. And let S the fuel efficiency (electric energy consumption for unit
distance) of EV. The electric demand rate of EV for the charging station x E xdh perunit time h is formulated the following equation:E  dhxd kx

nextk Kˆ xhf kxh(2)

SFrom the equations (1) and (2), the average waiting time for h can be formulated
as the cost of EV. Let x denote the arrival rate for the electric demand of E xdh . Let x is the service rate for the electric capacity of E x . The utilization ratio  x is thefollowing equation:shx 

x Exdh x Exsh(3)Therefore, the waiting time at the charging station x can be found using the equation(3). We assumed that the waiting time is added the penalty time in the situation
when  x  1 or the calculated waiting time is larger than or equal to the unit time h.
The equation of the waiting time Twx per unit time h is formulated changing theinterpretation of M/M/1 theory as: xT   (1   x ) x
hxw

 x  1,x

(1   x )x  h(4)otherwise
wait

Finally, the average cost for the waiting time at the charging station x t x

includingthe charging time is calculated as:

t xwait  Twx  1  x(5)

4Optimum location method for charging station

In this section, we explain the optimum location method for the location planning ofcharging station. Basically, it is said that EV driver has 3 behaviors showed in Fig.1.
From the view point of EV driver, it is important that the cost to the destination suchas travel time should be minimized. On the other hand, from the view point of theadministrator, it may say that the electric demand from the infrastructures for EV
should be controlled not to have demand bias for each region. Therefore, it is possible
to build up two hypotheses. We assume the objectives of the optimum location
method as follows:
1) The cost for one trip (from Origin to Destination) which is included thewaiting time of the battery charging at charging station should be minimized(Objective 1).
2) The bias of the electric demand for each charging station should beminimized (Objective 2).
The objective 1 depends on the route from origin to destination and the waitingtime of the battery charging. Especially, the time of battery charging is theunfavorable condition than the waiting time for gasoline charging. Thus it is said thatthe minimizing of the waiting time of charging is an important factor for the solution.
The object of calculation is the EVs that are needed to charge at charging station.
In the objective 2, a possibility of the bias of EV users is indicated. For example,
if many charging stations are located in an area, the electric demand of each charging
station might be low. However, the charging stations in other areas are needed tohandle the high demand. From this viewpoint, the location of charging station should
be considered to give equal charging opportunities for EV users and to equalize theelectric demand of the battery charging. In this study, it can be discussed that thedesign problem is defined the optimum location problem consists of two stages. The
formulation is explained in subsection 4.1 and 4.2.
4.1

Method for the objective 1

Here, let ckrs denote the route cost of the route k in the set of route for the OD pair rs( K rs ). And let

f krs

denote the path flow of the route k in the set of route K rs . The

solution for the objective 1 is formulated using the total cost of EVs Z as follows:
Minimize Z c fkK rs

Subject torskrskxa    ars,k f krsa A f -Q  0rs  f krs  0k  K rs , rs  rsrskkk

rs

(6)

Where xa is the traffic flow of the link a,  a,rsk is the variable with a condition that ifthe link a on the route k of the OD pair rs is included,  a,rsk is 1 and the otherwise is 0.

Q rs is the OD flow of OD pair rs. Using this equation, the traffic assignment tominimize the total cost of EV is examined. Here a total cost of a charging station x
c x is calculated as:c x   ckrs f krs
kKˆ xrs(7)

rs

Where K̂ x is the subset of route of the OD pair rs via the charging station x. Next
ckrs is assumed the situation that some charging stations are located at some nodes.

Therefore ckrs is included the link costs and the waiting times at the charging stations.
Let t a denote the link cost of the link a on the route k of OD pair rs. And let

t xwait denote the waiting time of battery charging at the charging station x on the route
k of OD pair rs. Then ckrs can be formulated as:ckrs   t a   t xwaitaAˆ krsxXˆ krs(8)

Fig.2 shows the image of the definition of EV cost from origin to destination.

Fig.2. Cost to the destination of EV
Finally, the link cost t a is considered the penalty cost in when the cruising distanceof EV is over the available (or maximum) cruising distance. The link cost t a isdefined as the following equation:   (c  trsa ,kta rskapenaltya(v))

vVkrsf krs,a0t apenalty (v)  t adsocv(9)  lak  0rsak Aˆ kavotherwise

Where ca is the link travel time of the link a, tapenalty (v) is the penalty cost of thepassing EV v in link a, and f krs,a is the count of the passing EVs for link a. d vsoc is theaccumulated distance from the origin for the EV v. la is the link length of the link akon the route k in the link subsetrsÂkav that the EV v selected until the link a. Thisequation using d vsoc is the condition to check whether the accumulated distance isover the available distance or not.
To find the solution for equation (6), the traffic assignment listing the paths for
all OD pairs should be done. In this study, we apply the Dial’s algorithm [9]. The
Dial’s algorithm is a traffic assignment technique with SUE not to list the paths fromorigins to destinations. The following is the calculation step of the Dial’s algorithm.
As the first step, the minimum cost c (i ) to each node (destination) i from the origin ris calculated.

c (i )  C min[ r  i ](10)Then, the link likelihood L[i  j ] from the node i to the node j is calculated for alllinks.

exp[ c( j )  c(i )  tij ]
L[i  j ]  
0c(i )  c( j )(11)otherwise

Where  is the logit parameter and tij is the link cost which is equal to t a . As thesecond step, we consider the node in ascending order of the cost c (i ) from (near) theorigin r. The link weight W [i  j ] is calculated as: L[i  j ]W [i  j ]   L[i  j ] [m  i ]mI ifor i  rotherwise(12)

Where I i is the set of node which inflow to the node i. As the third step, we consider
the node in descending order of the cost c (i ) from (far from) the origin r. the link
flow (traffic count) from the node i to the node jequation.

xij is calculated by the following

xij  (qrj   x jm )mO jW [i  j ] W [m  j ]

(13)

mI j

Where qrj is the OD flow from the origin r to the destination j and O j is the set ofnode which outflow from the node j. Each route of EV is determined from the thirdstep. At the same time, the route cost without the waiting time for battery charging
can be also calculated. Basically, the traffic assignment including the Dial’s
Algorithm have iteration process. In this method, the first assignment process iscalculated by the default link cost and is not considered the waiting time for battery
charging. From the second assignment process, the waiting time is calculated and isconsidered with the previous result of link cost.
4.2

Method for the objective 2In this subsection, we set up the equation for the objective 2. To set up theformulation, we apply the idea of Principle of Maximum Entropy. First, the total
electric demand of all of charging station Ed can be formulated as:Ed   E xdx X(14)Secondary, the percentage of the electric demand of charging station x of the total
electric demand Pe (x) is the following:

Edx
Pe ( x) Ed(15)Then it is clear that we have the following equation.

 P ( x)  1xXe(16)Finally, the entropy of the combination of the location of charging station H p can becalculated when we assume that Pe (x) is the probabilistic distribution satisfied thecondition of equation (16).
MaximizeH p    Pe ( x) log Pe ( x)xX

Subject to P ( x)  1xX(17)eFrom the viewpoint of principle of maximum entropy, it is said that the entropy
have a trend to be increased if the distribution of the electric demand is closed to theequal probability. Therefore, if the entropy is maximized, we can find the optimum
location of charging station satisfied the objective 2.

5Implementation of the optimum location method

This section is discussed the implementation of the optimum location method in
section 4. Fig.3 shows the flow chart for the implementation. This process consists ofthree steps. In the first step, the locations of charging stations are decided. To decide
the location, the suitable search algorithm is needed to feedback the result of entropy.
In the second step and the third step, we apply the Dial’s algorithm and the optimum
method we suggest.

Fig.3. Flow chart for implementation

6Future Works

In this paper, we explained a method for the design problem of EV charging
station. As the future works, we will apply the virtual road network such as grid
network first for the verification. After the verification, a case study using this method
will be examined for the real road network. Fig.4 shows the target area of the casestudy.
The issues to be tackled for the implementation are the decision methodology ofthe initial location of charging station and to find the search algorithm for the methodwith the validation of the calculation time.

Fig.4. Target area for case study

References
1. Fumiko KoyanagiKeinii Iwata:Decision of Priority Order of Recharger Installation inMusashino City by Domain Division, The Journal of the Faculty of Science and Technology,Seikei University, Vol.46, No.1, June 2009
2. Inês Frade, Anabela Ribeiro, António Pais Antunes (FCTUC), & Gonçalo Gonçalves (ISTIDMEC)Ines Frade, AAn Optimization Model for Locating Electric Vehicle Charging
Stations in Central Urban Areas, Transportation Research Board 90th Annual Meeting,January 23-27, 2011, Washinton, D.C.
3. Masao Koyama: Optimal Quick Charging Station Arrangementing-Tourist Behavioral
Simulation-, Innovations to Social Systems through Secondary Battery Applications FifthForum, 2010, Tokyo.
4. Fumiko Koyanagi, Yoshihisa Uriu: Proper Configuration of the Charging Station for Electric
Vehicle by Weighted Voronoi Mapping Method, 10th, 125-131, A, The Institute of ElectricalEngineers of Japan, 1999
5. S Parashar, C L Bloebaum: Robust Multi-Objective Genetic Algorithm Concurrent
Subspace Optimization (R-MOGACSSO) for Multidisciplinary Design, in Aerospace
Engineering (2006).
6. Brooks, O.: Solving Discrete Resource Allocation Problems using the Simultaneous
Perturbation Stochastic Approximation (SPSA) Algorithm, Proceedings of the Spring
Simulation Multiconference, 25–29 March 2007, Norfolk, VA, USA, pp. 55–62.
7. Takehiro Furuta, Maiko Uchida, Keisuke Inakawa, Atsuo Suzuki: A New Approach forLocation Multiple Facilities in a Network Competitive Environment, Transactions of theOperations Research Society of Japan, 2006, No.49, 32-45.
8. Berman, O.: Deterministic flow-demand location problem, Journal of Operational ResearchSociety, Vol. 48, pp. 75-81 (1997).
9. Dial R. B. (1971) A probabilistic multipath traffic assignment model which obviates pathenumeration, Transportation Research, Vol. 5, 83-111.