# On the Optimization Strategy of EV Charging Station Localization and Charging Piles Density

Authors: Wenzao Li; Lingling Yang; Zhan Wen; Jiali Chen; Xi Wu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

The penetration rate of electronic vehicles (EVs) has been increasing rapidly in recent years, and the deployment of EV infrastructure has become an increasingly important topic in some solutions of the Internet of Things (IoT). A reasonable balance needs to be struck between the user experience and the deployment cost of charging stations and the number of charging piles. The deployment of EV’s charging station is a challenging problem due to the uneven distribution and mobility of EV. Fortunately, EVs move with a certain regularity in the urban environment. It makes the deployment strategy design of EV charging stations feasible. Therefore, we proposed a deployment strategy of EV charging station based on particle swarm optimization algorithm to determine the charging station localization and number of charging piles. This strategy is designed based on the nonuniform distribution of EV in a city scene map, at the same time, the distribution of EV at different times, which makes the strategy more reasonable. Extensive simulation results further demonstrated that the proposed strategy can significantly outperform the K-means algorithm in the urban environment.


---

## Body

## 1. Introduction

### 1.1. Background and Motivation

Electric vehicle (EV) has gradually played a pivotal role in the people’s life due to the rapid development of EV and the Internet of Things (IoT) technology. The first half of 2020 was attacked by the COVID-19 virus, causing unprecedented deciles for vehicle sales. We can find that the number of global EV reached more than two hundred million in 2019, which is 9% higher than for 2018 [1]. Therefore, the construction of EV infrastructure has a crucial impact on the experience of EV consumers. The distributed charging station localization and charging pile density are two important issues in the fundamental infrastructure construction [2, 3]. Obviously, it affects the construction cost and user service quality. Most of the state-of-art estimation location approach for EV charging stations depends on the distribution of vehicles [4]. Unfortunately, area EV density is changing at any time due to the movement of EV. Therefore, the static EVs’ distribution cannot effectively reflect the effect of the charging station localization strategy. Deploying many charging stations can improve the user experience to some extent, but it will lead to increased construction costs. Conversely, it will increase the charging queue time of users. Thus, the traditional systematic approach usually discusses the solution to balance the requirements between the customers’ experience and economic efficiency [5]. As the IoT technology evolves, reasonable charging pile layout will greatly benefit the development of intelligent transportation [6]. For such reason, we propose the development strategy of charging stations under the change of EV density in urban areas. Besides, we give a calculation approach of the number of charging piles for each charging station.


### 1.2. Limitations of Prior Work

There were various locations estimating approaches, which were based on the range of EV and traffic density in cities. Catalbas et al. proposed the estimation method. Besides, they have modeled it as a basic optimization problem [7]. It adopts the average number of EVs and average driving distance as the important parameters in the approach. But this method does not consider the vehicle density changes. Schmidt and Eisel consider the user charging habits, and these historical data can estimate the localization of charging stations [8]. Yan et al. also adopt the particle swarm optimization algorithm to solve the localization problem of charging stations. It not only considered the planning of charging station location but also include the capacity of charging stations [9]. In the above researches, some of them did not consider the density changes, and some researchers did not adopt more realistic vehicle distribution data. Besides, the cost of charging stations and EV queuing time should be important factors in proposed algorithms.


### 1.3. Challenges and Solutions

There are several challenges for the localization of charging stations and charging pile density determination. First, the density change of EV is not only related to time, but also related to map information in urban environments. Therefore, to design the optimization algorithm, such as the heuristic method, should consider dynamic changes of EV. Second, the distributed data of EV needs to be closed to the actual situation which is based on the map information. Besides, the EV should conform to the movement model of EV. And such many EV distribution data collection is quite difficult. Third, as the number of EVs increases, the number of charging stations and charging piles should be flexible in the calculation strategy. Under a certain number of EV infrastructure scenario, user experiment is difficult to quantify. Based on the above challenges, we set up Working Day Movement (WDM) models to obtain EVs’ position at different moments. Then, Improved Particle Swarm Optimization (IPSO) algorithm and K-means approach solve the optimization problems after building an economic cost and user experience model.


### 1.4. Contributions and Organization

The contributions of this paper are summarized as follows. This paper models the charging station localization and charging pile density based on more reasonable data sets. Then, the proposed IPSO algorithm, which outperforms the K-means approach, is used to determine the location of charging stations. Besides, a strategy is proposed to calculate the number of charging piles based on user queue time. It is a flexible method to calculate the number of charging piles based on the constraint of user queuing time. Finally, we compare and verify the proposed method based on the distribution of EVs at different time points. This verification approach is more persuasive in such scenarios.The rest of this paper is organized as follows. In Section2.1, we introduce the scenario and system model. In Section 2.2, we give the details of the proposed algorithm based on the above scenario and the determination method of charging piles. The simulation scenario and results are presented in Section 3. Section 4 discusses related works, and finally, conclusion is in Section 5.


## 1.1. Background and Motivation

Electric vehicle (EV) has gradually played a pivotal role in the people’s life due to the rapid development of EV and the Internet of Things (IoT) technology. The first half of 2020 was attacked by the COVID-19 virus, causing unprecedented deciles for vehicle sales. We can find that the number of global EV reached more than two hundred million in 2019, which is 9% higher than for 2018 [1]. Therefore, the construction of EV infrastructure has a crucial impact on the experience of EV consumers. The distributed charging station localization and charging pile density are two important issues in the fundamental infrastructure construction [2, 3]. Obviously, it affects the construction cost and user service quality. Most of the state-of-art estimation location approach for EV charging stations depends on the distribution of vehicles [4]. Unfortunately, area EV density is changing at any time due to the movement of EV. Therefore, the static EVs’ distribution cannot effectively reflect the effect of the charging station localization strategy. Deploying many charging stations can improve the user experience to some extent, but it will lead to increased construction costs. Conversely, it will increase the charging queue time of users. Thus, the traditional systematic approach usually discusses the solution to balance the requirements between the customers’ experience and economic efficiency [5]. As the IoT technology evolves, reasonable charging pile layout will greatly benefit the development of intelligent transportation [6]. For such reason, we propose the development strategy of charging stations under the change of EV density in urban areas. Besides, we give a calculation approach of the number of charging piles for each charging station.


## 1.2. Limitations of Prior Work

There were various locations estimating approaches, which were based on the range of EV and traffic density in cities. Catalbas et al. proposed the estimation method. Besides, they have modeled it as a basic optimization problem [7]. It adopts the average number of EVs and average driving distance as the important parameters in the approach. But this method does not consider the vehicle density changes. Schmidt and Eisel consider the user charging habits, and these historical data can estimate the localization of charging stations [8]. Yan et al. also adopt the particle swarm optimization algorithm to solve the localization problem of charging stations. It not only considered the planning of charging station location but also include the capacity of charging stations [9]. In the above researches, some of them did not consider the density changes, and some researchers did not adopt more realistic vehicle distribution data. Besides, the cost of charging stations and EV queuing time should be important factors in proposed algorithms.


## 1.3. Challenges and Solutions

There are several challenges for the localization of charging stations and charging pile density determination. First, the density change of EV is not only related to time, but also related to map information in urban environments. Therefore, to design the optimization algorithm, such as the heuristic method, should consider dynamic changes of EV. Second, the distributed data of EV needs to be closed to the actual situation which is based on the map information. Besides, the EV should conform to the movement model of EV. And such many EV distribution data collection is quite difficult. Third, as the number of EVs increases, the number of charging stations and charging piles should be flexible in the calculation strategy. Under a certain number of EV infrastructure scenario, user experiment is difficult to quantify. Based on the above challenges, we set up Working Day Movement (WDM) models to obtain EVs’ position at different moments. Then, Improved Particle Swarm Optimization (IPSO) algorithm and K-means approach solve the optimization problems after building an economic cost and user experience model.


## 1.4. Contributions and Organization

The contributions of this paper are summarized as follows. This paper models the charging station localization and charging pile density based on more reasonable data sets. Then, the proposed IPSO algorithm, which outperforms the K-means approach, is used to determine the location of charging stations. Besides, a strategy is proposed to calculate the number of charging piles based on user queue time. It is a flexible method to calculate the number of charging piles based on the constraint of user queuing time. Finally, we compare and verify the proposed method based on the distribution of EVs at different time points. This verification approach is more persuasive in such scenarios.The rest of this paper is organized as follows. In Section2.1, we introduce the scenario and system model. In Section 2.2, we give the details of the proposed algorithm based on the above scenario and the determination method of charging piles. The simulation scenario and results are presented in Section 3. Section 4 discusses related works, and finally, conclusion is in Section 5.


## 2. The Charging Station Deploying Scenario and System Model

In Urban areas, EVs are unevenly distributed in locations where roads are available. Besides, in the deployment of charging stations, the station service capacity of each charging station needs to be considered. EV with reasonable radius coverage has multiple station choices, but different choices will lead to different charging costs. In this paper, we refer to reference [10] to plan the charging station deploying scenario and system model. Therefore, the cost in this paper mainly includes EV’s driving cost and charging station’s construction cost. From the perspective of user cost, we formulated this driving cost as the driving time cost between EV and charge station, energy consumption cost for the charging road, and queuing time or line time cost. The construction cost is mainly reflected in the number of charging stations and charging piles. Achieve the minimum amount in terms of satisfying the charging requirements for EVs. The coverage of EVs with EV charging stations is the key point of charging station deployment. The driving cost φζi is between the current position of EV i and the charging station ζ, which can be represented as equation (1).
(1)φζi=VTCivi,dζi+VTEivi,dζi+CSLiNζ,where theVTCivi,dζi represents the travel time cost of the EV i to the charging station ζ, VTEivi,dζi represents the energy consumption cost of the EV i to the charging station ζ, and CSLiNCS represents the queue time cost of the EV i at the charging station ζ.We also define the driving distance to the charging station. In the complex urban traffic situation, the constant speed model is not conductive to the reality of the scenario. In order to simulate the driving situation of road more realistically, we consider the nonlinear coefficient and back coefficient of road in the distance factor. The same in this paper, we consider the nonlinear coefficient of urban roads to calculate the distance traveled by EV, which can be given as equation (2).
(2)Dζi=λζi∗γζi∗dζi,where theγζi is the reentry coefficient of the EV journey from the EV i to the charging station ζ, dζi represents the linear distance from the EV i to the charging station ζ, and λζi denotes the nonlinear coefficient of the urban road from the EV i to the charging station ζ, which can be represented as the equation (3).
(3)λζi=dt_ζidζi.The minimum value ofλζi is 1, and the smaller the λζi, the more convenient the trip between the two points.The time-consuming cost of EVs on road can be calculated as equation (4).
(4)VTCivi,dζi=TβtimeNc∑ζ∈CS∑i∈CDDζivi,where theβtime represents the time cost of EVs, vi is the average driving speed of EVs, and T is the time period. The cost of charging period for an EV is considered a relatively long cycles to estimate for more realistic. At the same time, a year was chosen because it would cost the same as the charging station cost. Nc is the number of daily charging of EVs.
(5)Nc=E1km∗kB,where theE1km represents the energy consumption of EVs, k represents the daily mileage of EVs, and B represents the battery capacity of EVs.The cost of energy consumption for EVs to reach the charging station can be calculated as equation (6).
(6)VTEivi,dζi=TmNc∑ζ∈CS∑i∈CDDζiE1km,where them denotes the electricity price in the planned area.The construction cost of the charging station is composed of the fixed construction cost and the annual operating cost of the charging station, which can be calculated by equation (7).
(7)CSCζNζ=∑ζ∈CSfζNζRZ+uζNζ,where theCSCζNζ implies the construction cost of the charging station.The fixed construction costfζNζ of the charging station ζ can be denoted as function (8).
(8)fζNζ=Wζ+qζNζ+mζ,where theWζ is the fixed investment cost of each charging station, qζ is the construction investment cost related to the charger in the charging station, mζ is the investment cost related to the transformer in the charging station, and Nζ is the number of charging piles in charging station ζ.By reading a large number of references and combining the simulation environment of this paper, the annual operating cost of the charging stationζ can be represented as function (9). The coefficient of fζ was adopted by the reference [10].
(9)uζNζ=0.1fζNζ.RZ is the discount factor of the charging station which can be represented as function (10).
(10)RZ=rr1+rrms1+rrms−1,where therr is the discount rate and ms is the depreciation period of the charging station.The construction of the charging station not only needs to consider the construction cost of the charging station, but also needs to consider the driving cost of EVs. This paper focuses the total cost of charging stations and EVs. It includes the charging stations’ construction cost and EV’s driving cost. We establish a mathematical model for the location of EV charging stations, which can be described as equation (11).
(11)Costtotal=CSCζNζ+φζi,where the Costtotal is the total cost, CSCζNζ is the construction cost of the charging station, and φζi is the EV’s driving cost.


### 2.1. The Determination Method on the Deployment Number of Charging Pile in Charging Station

The EV needs to wait in line for idle charging pile for energy supplement. In order to reduce the waiting time and increase the user experience, queuing theory is a more effective solution. Queuing theory is through statistical research on the arrival and service time of service objects, to obtain statistical laws of quantitative indicators such as waiting time, queue length, and length of a busy period. It can improve the structure of the service system or reorganize the service objects according to above laws. So that the service system not only meets or closes to the requirements of the service’s target, but also can make the organization’s expenses the most economical or some indicators are optimal. The planning of the number of charging piles for each EV charging station is to meet the needs of EVs and to optimize the economics of the charging station. Therefore, this strategy adopted queuing theory multiservice desk model (M/M/S) to establish charging stations’ capacity allocation model. In the queuing system of the charging station, the arrival time of EV obeys the Poisson distribution with the parameterλ, and the service time of each service desk is independent of each other and obeys the negative exponential distribution with the parameter μ. The average queue length Ls of the EV at the charging station can be denoted as function (12).
(12)Ls=P0ρNζρNζNζ!1−ρNζ2+ρ,where theP0 is the probability that all charging piles in the charging station are idle, which can be represented as function (13).
(13)P0=∑n=0Nζ−1ρnn!+ρNζNζ!1−ρNζ−1,where the n is the number of EVs.
(14)ρNζ=ρNζ=λNζμ.The residence time of the EV at the charging station can be represented as function (15).
(15)Ws=Lsλ.The cost of the waiting time of an EV at a charging station can be represented as function (16).
(16)CSLiNζ=TβtimeNc∑ζ∈CS∑i∈CDWs−1μ.The objective function of this paper can be represented as function (17).
(17)Cost=minCosttotal,where the cost is the lowest cost considering the cost of the charging station (construction cost and annual operating cost) and the cost of the EV (road travel time cost, energy consumption cost, and waiting time cost at charging station).


### 2.2. The Constraints of Formulated Model

In determining the number of charging piles, the number of charging piles should be a reasonable value. Similarly, the constraints of charging stations and electric vehicles are reflected in the distance traveled. The number of EV services is also fixed in the charging station. Therefore, we enumerate the relevant constraints in the problem in this subsection.The number of charging piles in each charging stationζ can be represented as function (18).
(18)Nζ∈Nζ,min,Nζ,max,where the Nζ,min is the minimum number of charging piles included in the charging station ζ and Nζ,max is the maximum number of charging piles included in the charging station ζ.The distance constraint between charging stations can be represented as function (19).
(19)Dcs_ζ1,ζ2≥Dmin,where the Dmin is the minimum distance between two charging stations ζ1andζ2.The distance constraint from the EVi to the charging station ζ can be represented as function (20).
(20)Di_ζ≤Dmax,where theDmax is the maximum distance to the charging station ζ when the EV i needs to be charged.In order to avoid the long queue of EVs at the charging station and ensure the stability of the queuing system, the arrival rate of EVs should be less than the product of the service rate of the charging station and the number of charging piles, which can be represented as function (21).
(21)λ≤μNζ.The residence time limit of EVi at charging station ζ can be represented as function (22).
(22)Ws≤Ws−max,where the Ws−max is the maximum residence time of the EV i at the charging station ζ (Ws−max=40min).


## 2.1. The Determination Method on the Deployment Number of Charging Pile in Charging Station

The EV needs to wait in line for idle charging pile for energy supplement. In order to reduce the waiting time and increase the user experience, queuing theory is a more effective solution. Queuing theory is through statistical research on the arrival and service time of service objects, to obtain statistical laws of quantitative indicators such as waiting time, queue length, and length of a busy period. It can improve the structure of the service system or reorganize the service objects according to above laws. So that the service system not only meets or closes to the requirements of the service’s target, but also can make the organization’s expenses the most economical or some indicators are optimal. The planning of the number of charging piles for each EV charging station is to meet the needs of EVs and to optimize the economics of the charging station. Therefore, this strategy adopted queuing theory multiservice desk model (M/M/S) to establish charging stations’ capacity allocation model. In the queuing system of the charging station, the arrival time of EV obeys the Poisson distribution with the parameterλ, and the service time of each service desk is independent of each other and obeys the negative exponential distribution with the parameter μ. The average queue length Ls of the EV at the charging station can be denoted as function (12).
(12)Ls=P0ρNζρNζNζ!1−ρNζ2+ρ,where theP0 is the probability that all charging piles in the charging station are idle, which can be represented as function (13).
(13)P0=∑n=0Nζ−1ρnn!+ρNζNζ!1−ρNζ−1,where the n is the number of EVs.
(14)ρNζ=ρNζ=λNζμ.The residence time of the EV at the charging station can be represented as function (15).
(15)Ws=Lsλ.The cost of the waiting time of an EV at a charging station can be represented as function (16).
(16)CSLiNζ=TβtimeNc∑ζ∈CS∑i∈CDWs−1μ.The objective function of this paper can be represented as function (17).
(17)Cost=minCosttotal,where the cost is the lowest cost considering the cost of the charging station (construction cost and annual operating cost) and the cost of the EV (road travel time cost, energy consumption cost, and waiting time cost at charging station).


## 2.2. The Constraints of Formulated Model

In determining the number of charging piles, the number of charging piles should be a reasonable value. Similarly, the constraints of charging stations and electric vehicles are reflected in the distance traveled. The number of EV services is also fixed in the charging station. Therefore, we enumerate the relevant constraints in the problem in this subsection.The number of charging piles in each charging stationζ can be represented as function (18).
(18)Nζ∈Nζ,min,Nζ,max,where the Nζ,min is the minimum number of charging piles included in the charging station ζ and Nζ,max is the maximum number of charging piles included in the charging station ζ.The distance constraint between charging stations can be represented as function (19).
(19)Dcs_ζ1,ζ2≥Dmin,where the Dmin is the minimum distance between two charging stations ζ1andζ2.The distance constraint from the EVi to the charging station ζ can be represented as function (20).
(20)Di_ζ≤Dmax,where theDmax is the maximum distance to the charging station ζ when the EV i needs to be charged.In order to avoid the long queue of EVs at the charging station and ensure the stability of the queuing system, the arrival rate of EVs should be less than the product of the service rate of the charging station and the number of charging piles, which can be represented as function (21).
(21)λ≤μNζ.The residence time limit of EVi at charging station ζ can be represented as function (22).
(22)Ws≤Ws−max,where the Ws−max is the maximum residence time of the EV i at the charging station ζ (Ws−max=40min).


## 3. The Details of Proposed Algorithm in the Charging Station Deployment Scenario

### 3.1. Location Data Acquisition under Dynamic Change of EVs

As the density of EVs varies with the time in the urban areas, the change should be fully considered in the deployment approach. In order to obtain the distributed data of EVs that are closer to the real scene, the Opportunistic Network Environment (ONE) is adopted as the data generator [11]. Fortunately, the movement of EVs is regularly in urban areas. They move daily among offices, homes, and markets that result in the regularity of density changes [12]. Therefore, we use the Working Day Movement (WDM) model to collect EV distribution data set at different times for the localization approach [13]. Obviously, such a strategy can effectively avoid the process of measuring dynamic changes with distributed data.We comprehensively consider the location distribution of EVs at 8th hour, 16th hour, and 24th hour and formulate a strategy for the location and capacity of charging stations. Then, we use the position distribution of EVs at 32nd hour, 40th hour, and 48th hour to verify whether the strategy is optimal, which can be represented as Figure 1:Figure 1
The strategy for location determination of charging stations.


### 3.2. The Final Location of the Charging Station

In this paper, the main purpose is to plan the deployment of charging stations in the city. Therefore, according to the location distribution of EVs at different times, the optimal location of charging stations will vary to a certain extent. Therefore, we have formulated a strategy for determining the location of the charging station, considering the deployment of the charging station at 8th hour, 16th hour, and 24th hour, and determining the final location deployment strategy for the charging station, which can be described as Figure 2.Figure 2
Schematic diagram of the final location of the charging station.According to the location distribution of EVs, the optimal location of the charging station and the number of charging piles in the charging station are calculated when different numbers of charging stations are deployed.


### 3.3. The Details of Proposed Localization Algorithm

K-means algorithm is a clustering algorithm based on distance. In the K-means algorithm, first, randomly selectN points to form the cluster center, and then, divide the data in the data set into the clusters where the nearest cluster center is located, so the data set samples will be divided into several disjoint subsets. In each cluster, the distance from the objects in the subset to the center of the subset is less than the distance to the centers of other subsets. Finally, recalculate the new cluster center based on the new cluster. In the location of the charging station, we assume that the EV is charged at the nearest charging station.In the K-means algorithm, the center of each cluster is the location of the charging station, and the data set is the location of the EV. We getN clusters, and the data set contained in each cluster is the location of the EV served by the charging station. Therefore, we obtain the location distribution of the charging stations and the service range of the charging station through the K-means algorithm. When the N charging stations are deployed, then we can obtain the number of charging piles in the charging station through the proposed method. The specific implementation of the algorithm can be represented in Algorithm 1:Algorithm 1. K-means algorithm
Input: EV location data setU,U=x1,y1,x2,y2,⋯,xm,ym.Output: the location and number of charging stations and the number of charging piles in the charging station under the optimal costminCosttotal.1: According to the location and quantity of EVs in the planned area, estimate the range of the number of charging stations in the planned areaNmin,Nmax2: Set the initial value of the number of charging stationsNCS=Nmin3: whileNmin≤NCS≤Nmax4:   Randomly selectNCS group data from U as the initial position data set CS of the charging station, CS=X1,Y1,X2,Y2,⋯,XNCS,YNCS5:   repeat6:    LetCζ=∅1≤ζ≤NCS7:    fori=1,2,⋯,mdo8:       Calculate the Euclidean distancedζi from EV i, xi,yi to each charging station ζ1≤ζ≤NCS,Xζ,Yζ9:      According to the principle of closest distance, determine which charging station each EV belongs to:αi=argminζ∈1,2,⋯,NCSdζi10:       Assign EVsxi,yi to the corresponding charging stations: Cαi=Cαi∪xi,yi11:      end for12:      forζ=1,2,⋯,NCSdo13:         Calculate the location of the new charging station:Xζ,Yζ′=1/∣Cζ∣∑x,y∈Cζx,y14:         ifXζ,Yζ′=Xζ,Yζthen15:          Update the current charging station locationXζ,Yζ to Xζ,Yζ′16:       else17:           Keep the current mean vector unchanged18:        end if19:     end for20:   until the current charging station location is no longer updated21:   Current output: division of service scope of charging stationsC=C1,C2,⋯,CNCS22:   Use queuing theory [M/M/S] to calculate the number of charging piles in the charging stationNpiles=NC1,NC2,⋯,NCNCS23:  Calculate the total cost of deployingNCS charging stations CostNCS, CostNCS=CostCS_construction+CostCS_run+CostEV_road_time+CostEV_road_energy+CostEV_line_time。24 end while25:  Calculate the total cost of deploying different numbers of charging stations and get the total cost data setCosttotal, Costtotal=CostNmin,CostNmin+1,⋯,CostNmaxBy Algorithm1, we can obtain the locations of the charging stations. Besides, the number of charging piles of a charging station can be determined. When different numbers of charging stations are deployed at different times, then we can obtain the final charging station location by the charging station location determination strategy. It also comprehensively considers the number of charging piles in the charging station at each time to determine the final number of charging piles.The particle swarm algorithm adopts a group of initialized groups to search in parallel in the search space and realizes the evolution of the population through the competition and cooperation between individuals in the population. In the particle swarm algorithm, each particle represents a potential solution to the problem, and the fitness function is used to judge the quality of the particle. The initial value of the particle swarm is a group of random particles, searching for the optimal solution according to iterations. In each iteration, the particles update their position and velocity according to the individual optimal value and the global optimal value.The IPSO algorithm adopts differential evolution algorithm to increase the activity of particles in the particle swarm. Therefore, the particles can jump out of the local optimum to better global optimum.In this algorithm, we use the site of the charging station as the dimension of each particle. IfN charging stations need to be defined, the dimension of the particle is 2N. According to the size of PopSize, each charging station randomly generates PopSize site coordinates at the same time. Then, the service range of the charging station is divided according to the Voronoi diagram to obtain the number of charging piles. Then, we can calculate the fitness value of each particle and update the speed and position of the particle through the speed and position update formula. Finally, find the optimal solution through a number of iterations. Therefore, after calculating by the IPSO algorithm, we obtain the location distribution states and the service range of the charging station. We can also obtain the number of charging piles through the method of determining the number of charging piles when N charging stations are deployed. The specific implementation of the algorithm can be represented in Algorithm 2:Algorithm 2. Improved Particle Swarm Optimization (IPSO) algorithm
Input: EV position data setU, U=x1,y1,x2,y2,⋯,xm,ym.Output: the location and number of charging stations and the number of charging piles in the charging station under the optimal costminCosttotal.1: According to the location and quantity of EVs in the planned area, estimate the range of the number of charging stations in the planned areaNmin,Nmax2: Set the initial value of the number of charging stationsNCS=Nmin3:  whileNmin≤NCS≤Nmax4:     Set the maximum number of iterations of the algorithm MaxIter, particle population size PopSize, random valuesr1, r2, learning factors c1, c2, inertia weight ω5:    fori=1,2,⋯,PopSize do6:        Randomly selectNCS group data from U as the charging station initial position data set Xi, Xi=X1,Y1,X2,Y2,⋯,XNCS,YNCSi. Initial particle velocity Vi, Vi=rand7:        Use the Voronoi diagram to divide the service scope of the charging stationA, A=A1,A2,⋯,ANCS8:        Assign EVsxm,ym to the nearest charging station ANCS, ANCS=ANCS∪xm,ym9:        Use queuing theory [M/M/S] to calculate the number of charging piles in the charging stationNpiles,Npiles=NC1,NC2,⋯,NCNCS10:         Calculate the total cost when deployingNCS charging stations in combination with constraint conditions Cost1i11:     The optimal statistical particle individual isPbest_i, Pbest_i=X1,Y1,X2,Y2,⋯,XNCS,YNCSi12:     end for13:  The particle population cost data set isCost1, Cost1=Cost11,Cost12,⋯,Cost1PopSize14:  The optimal data set of individual particles isP1best, P1best=Pbest_1,Pbest_2,⋯,Pbest_PopSize15:  Set the particle global optimal valueBest1, Best1=minCost1, the corresponding particle is the global optimal particle gbest116:  repeat17:     forj=1,2,⋯,PopSizedo18:         Update particle velocityVj, Vj=ω∗Vj+c1r1Pbest_j−Xj+c2r2gbest1−Xj19:         Update particle positionXj, Xj=Xj+Vj20:         Calculate the total cost when deployingNCS charging stations in combination with constraint conditions Cost2j21:         Get the optimal position of each particlePbest_2j22:       ifCost2j≤Cost1jthen23:Pbest_j=Pbest_2j24:       else25:          Keep the current particle positionPbest_j unchanged26:       end if27:     end for28:   The particle population cost data set isCost2, Cost2=Cost21,Cost22,⋯,Cost2PopSize29:   Set the global optimal valueBest2, Best2=minCost2, determine the global optimal particle gbest230:    ifBest2≤Best1then31:gbest1=gbest232:    else33:      Keep the current particle positiongbest1 unchanged34:    end if35:  until the number of cycles reaches MaxIter36: end while37: Current output: output the optimal location for deployingNCS charging stations38: Use the optimal location to calculate the total cost of deployingNCS charging stations CostNCS and the number of charging piles in the charging station.39: Calculate the total cost of deploying different numbers of charging stations and get the total cost data setCosttotal,Costtotal=CostNmin,CostNmin+1,⋯,CostNmaxIn Algorithm2, we obtain the location of the charging station and the number of charging piles in the charging station when different numbers of charging stations are deployed. Then, the charging station location determination strategy can be used to obtain the final charging station location. And to determine the final number of charging piles is feasible.


## 3.1. Location Data Acquisition under Dynamic Change of EVs

As the density of EVs varies with the time in the urban areas, the change should be fully considered in the deployment approach. In order to obtain the distributed data of EVs that are closer to the real scene, the Opportunistic Network Environment (ONE) is adopted as the data generator [11]. Fortunately, the movement of EVs is regularly in urban areas. They move daily among offices, homes, and markets that result in the regularity of density changes [12]. Therefore, we use the Working Day Movement (WDM) model to collect EV distribution data set at different times for the localization approach [13]. Obviously, such a strategy can effectively avoid the process of measuring dynamic changes with distributed data.We comprehensively consider the location distribution of EVs at 8th hour, 16th hour, and 24th hour and formulate a strategy for the location and capacity of charging stations. Then, we use the position distribution of EVs at 32nd hour, 40th hour, and 48th hour to verify whether the strategy is optimal, which can be represented as Figure 1:Figure 1
The strategy for location determination of charging stations.


## 3.2. The Final Location of the Charging Station

In this paper, the main purpose is to plan the deployment of charging stations in the city. Therefore, according to the location distribution of EVs at different times, the optimal location of charging stations will vary to a certain extent. Therefore, we have formulated a strategy for determining the location of the charging station, considering the deployment of the charging station at 8th hour, 16th hour, and 24th hour, and determining the final location deployment strategy for the charging station, which can be described as Figure 2.Figure 2
Schematic diagram of the final location of the charging station.According to the location distribution of EVs, the optimal location of the charging station and the number of charging piles in the charging station are calculated when different numbers of charging stations are deployed.


## 3.3. The Details of Proposed Localization Algorithm

K-means algorithm is a clustering algorithm based on distance. In the K-means algorithm, first, randomly selectN points to form the cluster center, and then, divide the data in the data set into the clusters where the nearest cluster center is located, so the data set samples will be divided into several disjoint subsets. In each cluster, the distance from the objects in the subset to the center of the subset is less than the distance to the centers of other subsets. Finally, recalculate the new cluster center based on the new cluster. In the location of the charging station, we assume that the EV is charged at the nearest charging station.In the K-means algorithm, the center of each cluster is the location of the charging station, and the data set is the location of the EV. We getN clusters, and the data set contained in each cluster is the location of the EV served by the charging station. Therefore, we obtain the location distribution of the charging stations and the service range of the charging station through the K-means algorithm. When the N charging stations are deployed, then we can obtain the number of charging piles in the charging station through the proposed method. The specific implementation of the algorithm can be represented in Algorithm 1:Algorithm 1. K-means algorithm
Input: EV location data setU,U=x1,y1,x2,y2,⋯,xm,ym.Output: the location and number of charging stations and the number of charging piles in the charging station under the optimal costminCosttotal.1: According to the location and quantity of EVs in the planned area, estimate the range of the number of charging stations in the planned areaNmin,Nmax2: Set the initial value of the number of charging stationsNCS=Nmin3: whileNmin≤NCS≤Nmax4:   Randomly selectNCS group data from U as the initial position data set CS of the charging station, CS=X1,Y1,X2,Y2,⋯,XNCS,YNCS5:   repeat6:    LetCζ=∅1≤ζ≤NCS7:    fori=1,2,⋯,mdo8:       Calculate the Euclidean distancedζi from EV i, xi,yi to each charging station ζ1≤ζ≤NCS,Xζ,Yζ9:      According to the principle of closest distance, determine which charging station each EV belongs to:αi=argminζ∈1,2,⋯,NCSdζi10:       Assign EVsxi,yi to the corresponding charging stations: Cαi=Cαi∪xi,yi11:      end for12:      forζ=1,2,⋯,NCSdo13:         Calculate the location of the new charging station:Xζ,Yζ′=1/∣Cζ∣∑x,y∈Cζx,y14:         ifXζ,Yζ′=Xζ,Yζthen15:          Update the current charging station locationXζ,Yζ to Xζ,Yζ′16:       else17:           Keep the current mean vector unchanged18:        end if19:     end for20:   until the current charging station location is no longer updated21:   Current output: division of service scope of charging stationsC=C1,C2,⋯,CNCS22:   Use queuing theory [M/M/S] to calculate the number of charging piles in the charging stationNpiles=NC1,NC2,⋯,NCNCS23:  Calculate the total cost of deployingNCS charging stations CostNCS, CostNCS=CostCS_construction+CostCS_run+CostEV_road_time+CostEV_road_energy+CostEV_line_time。24 end while25:  Calculate the total cost of deploying different numbers of charging stations and get the total cost data setCosttotal, Costtotal=CostNmin,CostNmin+1,⋯,CostNmaxBy Algorithm1, we can obtain the locations of the charging stations. Besides, the number of charging piles of a charging station can be determined. When different numbers of charging stations are deployed at different times, then we can obtain the final charging station location by the charging station location determination strategy. It also comprehensively considers the number of charging piles in the charging station at each time to determine the final number of charging piles.The particle swarm algorithm adopts a group of initialized groups to search in parallel in the search space and realizes the evolution of the population through the competition and cooperation between individuals in the population. In the particle swarm algorithm, each particle represents a potential solution to the problem, and the fitness function is used to judge the quality of the particle. The initial value of the particle swarm is a group of random particles, searching for the optimal solution according to iterations. In each iteration, the particles update their position and velocity according to the individual optimal value and the global optimal value.The IPSO algorithm adopts differential evolution algorithm to increase the activity of particles in the particle swarm. Therefore, the particles can jump out of the local optimum to better global optimum.In this algorithm, we use the site of the charging station as the dimension of each particle. IfN charging stations need to be defined, the dimension of the particle is 2N. According to the size of PopSize, each charging station randomly generates PopSize site coordinates at the same time. Then, the service range of the charging station is divided according to the Voronoi diagram to obtain the number of charging piles. Then, we can calculate the fitness value of each particle and update the speed and position of the particle through the speed and position update formula. Finally, find the optimal solution through a number of iterations. Therefore, after calculating by the IPSO algorithm, we obtain the location distribution states and the service range of the charging station. We can also obtain the number of charging piles through the method of determining the number of charging piles when N charging stations are deployed. The specific implementation of the algorithm can be represented in Algorithm 2:Algorithm 2. Improved Particle Swarm Optimization (IPSO) algorithm
Input: EV position data setU, U=x1,y1,x2,y2,⋯,xm,ym.Output: the location and number of charging stations and the number of charging piles in the charging station under the optimal costminCosttotal.1: According to the location and quantity of EVs in the planned area, estimate the range of the number of charging stations in the planned areaNmin,Nmax2: Set the initial value of the number of charging stationsNCS=Nmin3:  whileNmin≤NCS≤Nmax4:     Set the maximum number of iterations of the algorithm MaxIter, particle population size PopSize, random valuesr1, r2, learning factors c1, c2, inertia weight ω5:    fori=1,2,⋯,PopSize do6:        Randomly selectNCS group data from U as the charging station initial position data set Xi, Xi=X1,Y1,X2,Y2,⋯,XNCS,YNCSi. Initial particle velocity Vi, Vi=rand7:        Use the Voronoi diagram to divide the service scope of the charging stationA, A=A1,A2,⋯,ANCS8:        Assign EVsxm,ym to the nearest charging station ANCS, ANCS=ANCS∪xm,ym9:        Use queuing theory [M/M/S] to calculate the number of charging piles in the charging stationNpiles,Npiles=NC1,NC2,⋯,NCNCS10:         Calculate the total cost when deployingNCS charging stations in combination with constraint conditions Cost1i11:     The optimal statistical particle individual isPbest_i, Pbest_i=X1,Y1,X2,Y2,⋯,XNCS,YNCSi12:     end for13:  The particle population cost data set isCost1, Cost1=Cost11,Cost12,⋯,Cost1PopSize14:  The optimal data set of individual particles isP1best, P1best=Pbest_1,Pbest_2,⋯,Pbest_PopSize15:  Set the particle global optimal valueBest1, Best1=minCost1, the corresponding particle is the global optimal particle gbest116:  repeat17:     forj=1,2,⋯,PopSizedo18:         Update particle velocityVj, Vj=ω∗Vj+c1r1Pbest_j−Xj+c2r2gbest1−Xj19:         Update particle positionXj, Xj=Xj+Vj20:         Calculate the total cost when deployingNCS charging stations in combination with constraint conditions Cost2j21:         Get the optimal position of each particlePbest_2j22:       ifCost2j≤Cost1jthen23:Pbest_j=Pbest_2j24:       else25:          Keep the current particle positionPbest_j unchanged26:       end if27:     end for28:   The particle population cost data set isCost2, Cost2=Cost21,Cost22,⋯,Cost2PopSize29:   Set the global optimal valueBest2, Best2=minCost2, determine the global optimal particle gbest230:    ifBest2≤Best1then31:gbest1=gbest232:    else33:      Keep the current particle positiongbest1 unchanged34:    end if35:  until the number of cycles reaches MaxIter36: end while37: Current output: output the optimal location for deployingNCS charging stations38: Use the optimal location to calculate the total cost of deployingNCS charging stations CostNCS and the number of charging piles in the charging station.39: Calculate the total cost of deploying different numbers of charging stations and get the total cost data setCosttotal,Costtotal=CostNmin,CostNmin+1,⋯,CostNmaxIn Algorithm2, we obtain the location of the charging station and the number of charging piles in the charging station when different numbers of charging stations are deployed. Then, the charging station location determination strategy can be used to obtain the final charging station location. And to determine the final number of charging piles is feasible.


## 4. The Simulation Scenario and Results

Based on collecting several node distribution data of the Helsinki city map on ONE simulator, we carried out numerical experiments. This paper sets the simulation parameters based on the reference [14] simulation environment, which can be represented as Table 1.Table 1
The key simulation parameters.
ParameterValueFixed investment (Wζ)2 millionInvestment related to the unit price of the charging piles in the charging station (q)0.35 millionThe investment cost related to the transformer in the charging station (eζ)0.2 millionDiscount rate (rr)0.08Charging station depreciation period (ms)20 yearsAverage driving speed of EVs (v)30 km/hTime period (T)365 daysNonlinear coefficient of the urban road (λiζ)1.2Minimum number of charging piles in the charging station (Nζ,min)3Maximum number of charging piles in the charging station (Nζ,max)30Minimum number of charging stations (Nmin)3Maximum number of charging stations (Nmax)6Minimum distance between two charging stationsζ1,ζ2(Dmin)1.2 kmMaximum distance to the charging stationζ when the EV i needs to be charged3 kmIn this paper, we estimate that the cost of the final location and capacity solution is1.5∗107. Due to the mobility of EVs, there are certain differences in the locations of EVs at different time periods. We considered the position distribution of EVs in the 8th hour, 16th hour, and 24th hour time points and calculated the actual total cost of deploying different numbers of charging stations in different time periods as a percentage of the estimated total cost. The result of the K-means algorithm and the IPSO algorithm can be represented as Figure 3.Figure 3
The ratio of actual total cost to estimated total cost.From Figure3, we can observe that both of two algorithms are optimal with 4 stations in the deployment area.When planning the number of charging piles in a charging station, use queuing theory to calculate the number of charging piles in each charging station. Because the queuing time of EVs is considered in this paper, when there is no queuing time limit, the number of charging piles in the charging station is the initial value of the number of charging piles. When 4 charging stations are deployed in different time periods, the initial number of charging piles in each charging station is obtained. The calculation results under the K-means algorithm and the IPSO algorithm can be represented as Figure4:Figure 4
The initial number of charging piles in the charging station.When there is a queuing time limit, the number of charging piles is increased on the basis of the initial value. Through calculation, the relationship between the number of charging piles in the charging station and the queuing time of EVs can be obtained. The calculation results under the K-means algorithm can be represented as Figure5, and the calculation results under the IPSO algorithm can be represented as Figure 6:Figure 5
The relationship between the number of charging pile and the queue time of EVs (K-means algorithm).Figure 6
The relationship between the number of charging pile and the queue time of EVs (IPSO algorithm).As it is shown in Figures5 and 6, the dotted line y=10 represents the maximum queuing time Wmax of EVs at the charging station. By observing Figures 5 and 6, we can find that as the number of charging piles in the charging station increases, the average queue time of EVs at the charging station gradually decreases. The dotted ellipse indicates that no matter what time period, when the number of charging piles is deployed at the charging station ζ, the queue time of EVs at the charging station ζ is within 10 minutes. Therefore, when using the K-means algorithm, we finally select the number of charging piles in the charging station to be [22; 20; 15; 12]. When using the IPSO algorithm, we finally select the number of charging piles in the charging station as [24; 15; 15; 13].In order to verify the effectiveness, we chose multiple time points (32nd hour, 40th hour, and 48th hour) to calculate the cost. The ratio of the total cost of each time to the estimated total cost can be represented as Figure 7.Figure 7
The ratio of actual total cost.By observing Figure7, we can find that when 4 charging stations are deployed in different time periods, the cost is the lowest. It shows that whether it is based on the K-means algorithm or the IPSO algorithm, it is relatively better to deploy 4 charging stations when planning the charging station. At the same time, we can find that when 4 charging stations are deployed, the total cost when using the IPSO algorithm is better than the K-means algorithm.In the 32nd hour, 40th hour, and 48th hour time points, the average queuing time of EVs is calculated by queuing theory. The average queue time of EVs can be shown in Figure 8:Figure 8
Average queue time of EVs.From Figure8, we apply the termination method to calculate the number of charging piles at the charging station. And the average queue time of EVs can be less than 10 minutes, which meets the original design intention.At different moments, based on the K-means algorithm and the IPSO algorithm, the charging station location and service range are described in Figure9(K-means algorithm_8th hour and K-means algorithm_16th hour), Figure 10(K-means algorithm_24th hour and IPSO algorithm_8th hour), and Figure 11(IPSO algorithm _16th hour and IPSO algorithm _24th hour). It can be seen from these figures that the results of the two algorithms are similar to those of the service area division. However, the cost of the calculation based on the service area still shows the pros and cons of the two solutions.Figure 9
Location and service range of charging stations.Figure 10
Location and service range of charging stations.Figure 11
Location and service range of charging stations.With the K-means algorithm, the actual total cost of deploying 4 charging stations is 50.70% of the estimated total cost. With the particle swarm algorithm, the actual total cost of deploying 4 charging stations is 46.45% of the estimated total cost. With the IPSO algorithm, the actual total cost of deploying 4 charging stations is 46.04% of the estimated total cost. The total cost of IPSO algorithm is 9.19% lower than the K-means algorithm in such scenario.


## 5. Related Works

The planning of EV charging stations and charging piles and some short-range communication techniques are attractive research fields for charging demand intelligence guidance [15–17]. At the same time, it is also an important issue in Smart Cities (SC) [18]. The difficulties focus on charging station determination in charging planning. Eisel et al. formulated the charging problem based on user’s charging habits and proposed a method for selecting the location of charging stations [19]. Tang et al. proposed a weighted Voronoi diagram (VD) approach to determine the location of EV charging stations [20]. Nahum and Hadas proposed a multiobjective optimal allocation approach for bus charging planning [21]. It can be found from these studies that EV charging problem is a typical resource allocation problem. Therefore, the heuristic algorithm and clustering method can get better results. Particle swarm optimization has advantages in this kind of problem [22, 23]. But there are some problems with the above research. First, the implementations of the proposed algorithms are based on different system models, which are incomplete for result analysis. Second, the simulated data set does not take into account the variation of EV density. The validation of algorithm results is not sufficiently supported. Third, some researchers discussed the location of charging stations, and some discussed the number of charging piles; thus, it lacked systematic and comprehensive analysis.


## 6. Conclusions

The charging station localization and charging pile determination based on the distribution of EVs can effectively decrease the cost of users and urban construction. There are many detects in the direct addressing of the static EV’s distribution data, because the distribution of EVs changes with time and geographic area. Thus, this paper introduces a strategy with IPSO-based algorithm, which is used for determining the location of the charging station. Besides, we also provide an approach to determine the number of charging piles in a charging station according to user demand. And based on this strategy, we proposed the addressing method based on K-means algorithm. Though numerical experiments are based on more realistic data set, we found that the algorithm based on IPSO outperforms the K-means. Moreover, we have fully discussed the results, which have great significance to the EV charging station deployment and user’s experiments.



---

*Source: 6675841-2021-02-23.xml*