# A Novel Dynamic Capacity Expansion Framework Includes Renewable Energy Sources for an Electric Vehicle Charging Station

Authors: T. S. Geetha; V. Amudha; C. Chellaswamy
Journal: International Transactions on Electrical Energy Systems
 (2022)

---

## Abstract

This paper proposes a novel capacity expansion framework for electric vehicle charging stations (EVCSs) through short-term functional decisions and long-term planning under stochastic power demand. Energy resources such as solar, wind, energy storage systems, and microgas turbines supply energy to the microgrid. An EVCS works as a vehicle-to-grid (V-G), and it can send energy to the microgrid. The capacities of solar panels, storage systems, and wind turbines can be expanded by implementing capacity expansion planning in a microgrid. The short-term and long-term expansion problem has been solved by optimizing the hourly operation of the resources and with a five-year planning horizon, respectively. A hybrid algorithm combining the sample average approximation technique and the apriori progressive hedging algorithm (SAAT-APHA) has been proposed in this study. The impact of the availability of different resources, including wind, solar, and V-G power on the system performance has been analyzed. Finally, a comparison has been performed with three other algorithms, and the results show the superiority of the proposed method.


---

## Body

## 1. Introduction

For a long time, fossil fuels have been served as the predominant source of energy for vehicles. There has been much advancement in the technology used in cars but not its energy sources. Natural gases, hybrid fuels, electricity, and hydrogen have been tried as alternatives to fossil fuels because fossil fuels are limited, and thus renewable energy technologies are needed. This also leads to lower greenhouse gas emissions. However, attempts to replace fossil fuels are few and ineffective. The electric vehicle (EV) adoption rate is slowed due to a range of anxieties [1]. This problem can be addressed by advancing battery technology and continuous research about in this technology. For example, Tesla’s EVs run for more than 300 miles due to the advancement in lithium-ion batteries, and Samsung made its vehicles run for 370 miles using lithium-ion batteries, which can be fully charged within 20 minutes. However, the lack of availability of charging stations also hinders the promotion of EVs [2]. Therefore, improvement in the usage of the EV is possible by implementing proper infrastructure in changing stations. The U.S government initiated the EV everywhere to promote the use of electric vehicles. The collaboration between electricity generation departments and light-duty EVs may reduce the total cost [3, 4].In recent years, microgrids have been developed as important parts of electrical grids. Microgrids can also be used in expansion planning [5]. A regional-based demand-side response is considered for electric vehicle charging (RDR-EV) including renewable energy sources. The capacity for energy and line resources is fewer in microgrids compared to electric power systems. However, the expansion model of these systems is similar to electrical networks that are available on large scale [6, 7]. Microgrids can be integrated with many energy resources like diesel generation, wind and gas turbines, solar power, and storage systems for storing energy [8]. In the upcoming years, load demand can be met by expanding energy resources. We can also expand the capacity of the line between the upstream network and the microgrid. The systems that store energy act as an important part of the microgrid [9]. Various technical advantages are obtained by the microgrid’s hybrid energy storage systems (ESSs)—both short-term with battery fly-wheels and long-term with a compressed air-super capacitor. In the future, hybrid ESS can be applied in unbalanced and nonlinear loads [10].This paper discusses the long-term planning decisions for charging stations such as size, location, and time to open charging stations and short-term operational decisions for using charging stations on an hourly basis, such as having storage for several batteries, which can be discharged through B2G and grid power usage under the same framework [11]. This paper proposes a two-stage programming model under random power demand and prespecified planning horizon which optimizes long-term planning decisions and short-term operational decisions at the same time. Due to the dynamic traffic demands, hard location design, availability of renewable energy sources, and other factors that affect the hourly power management, battery charging and discharging planning will be a challenging. To reduce these problems, a customized hybrid algorithm has been proposed which combines the sample average approximation technique (SAAT) [12] with the apriori progressive hedging algorithm (SAAT-APHA) [13]. This hybrid algorithm provides an improvement in the local and global maxima problems. This algorithm was implemented in the road network of Berlin, Germany, to solve the real-time problem.The proposed two-stage stochastic programming model differs from the existing model in the following ways: (a) The expanded long-term planning model of a charging station has the size, ability to open facilities, and location; it can respond to the demand on a short-term hourly basis. In the existing models, planning decisions are made as long-term and short-term operational decisions but no other existing models discuss the effects due to the integration of both long-term planning decisions and short-term operational decisions under the same framework. This may result in an inaccurate estimation of cost and subpar decisions. The integration of these models has many methodological challenges, and solving these efficiently will enhance the engineering policies and guidelines that are important for the new vehicular system. (b) To obtain high utilization of renewable energy, this model can be extended by using expected value and economic constraints. To minimize the overall system cost, the integration of sources is an important facet. Different algorithmic improvements like techniques for updating penalty parameters and local and global heuristic are also used. A real case study was constructed to test the performance of the model. The performance of the proposed SAAT-APHA was studied. The impact of using different resources for EV charging, gris power on system perfromance, renewable energy, and V2G has been studied. Finally, a comparison of the SAAT-APHA with other state-of-art methods and sensitivity analysis has been performed.The rest of the paper is organized as follows. Section2 describes the literature review of the capacity expansion of the EVCS. Section 3 explains the problem description and formulation of the model. The sample average approximation and apriori progressive hedge algorithm are described in Section 4. The result of the proposed in the charging station expansion plan, comparison, and sensitivity analysis are described in Section 5. Finally, conclusion is given in Section 6.


## 2. The Literature Review

Dynamic capacity expansion framework is one of the conventional methods focused on load growth. To manage the load growth, the available components, transmission or distribution, and energy resources are expended. The short-term expansion planning often considered as houril or as daily whereas long-term expansion planning is considered for years to decades [14]. The generation expansion planning expands the capacity of the available generating units and/or installed a new generating technology. The expansion of generation can be expressed as a nonlinear or linear model; mathematically it can be represented as an optimization programming [15]. The energy storage systems are easily integrated with the generation expansion. A generation expansion planning was proposed by Opathella et al. including various storage technologies and studied the performance of the system. Here, the planning cost was reduced efficiently [16].Bornapour et al. suggested a capacity expansion for the existing generating unit including new technologies. It is an optimization program and can be denoted as a linear or nonlinear model [17]. The novel generating system size, technology, installation time, and operation pattern are determined by these problems, and the investment, maintenance, operational, and environmental costs are optimized [18]. Optimization problem is solved by considering the constraints related to the technical, security, and economic aspects of the system. Some of the challenges faced in the generation expansion are risk assessment, power and natural gas systems, demand-side management programs, EVs, ESS, the role of optimal short-term operation on long-term planning, environmental impact, policy-security issues, and renewable energy integration [19]. The expansion for generation is implemented with ESS. Planning costs are reduced by shifting the energy of storage technologies over hours or days. The expansion planning problem gives us idea about the different storage technologies [20].Power system reliability and stability can be maintained if there is an exact balance between real-time supply and demand of electricity. It causes power system planning and operational challenges as there is uncertainty in the renewable energy sources (RESs) and variability [21]. The availability of vehicle-to-grid (V-G) services varies at different periods of the day as V-G is stochastic and reliant on the EVs passing through the charging stations. Therefore, the actual benefits cannot be realized even if we integrate renewable energy and V-G. Before now, research has addressed problems relating to charging schedules and suggested charging schedules for the EVs as planned with or without the integration of V-G sources and renewable energy [22]. To minimize the cost globally, a local scheduling model to decide the discharging and charging decisions has been introduced by He et al. [23]. Better security and efficiency can be achieved by integrating V-G and power systems. Results can be improved using this coordination with the existing infrastructure [24]. The power supply is made stable by using EVs as mobile energy sources. Haddadian et al. proposed a method introducing different price approaches throughout a single day when renewable energy is integrated with the power system of a charging station [25].In addition to this, more research studies have been conducted to develop a random model to determine the location of the EVCS. A two-stage random program was developed by Pan et al. to find the location of the EVCS before realizing the battery demands, loads, and capacity of renewable power sources [26]. A three-step method that can combine simulation and optimization is used to find out the location of the EVCS and the level of charging to be installed at each CS [27]. A multi-time period linear mixed-integer programming model is used to find out an optimal control strategy for an EVCS that has energy storage, renewable energy sources, and integrated EVs. Further, a random chance-constrained programming model was proposed by them that manages demand and power generation, connection and disconnection times, and state of the EV charge [28]. Using the limited amount of information about EV’s adoption rate, Mak et al. proposed an optimization model to build the infrastructure for the EV swapping stations [29]. A two-stage station location model based on a finite number of situations that have traffic flow uncertainty and using stochastic refueling was proposed by Hosseini and Mir Hassani [30]. The optimization problem was solved by a two-step algorithm in which the problem size was reduced in the first step by solving the original model and the location of the EVCS was determined by using a greedy algorithm in the second step [31]. A stochastic model was proposed to operate EVCS effectively under stochastic demand using an energy storage device [32]. An optimized framework provides multiple EVCS and allocates charging option for many cars simultaneously. The key idea in using this optimal control method is to reduce the charging cost and to establish an optimal rate for charging [33]. An optimized EV charging including renewable energy sources (EV-RES) has been studied by Jin et al. [34]. Dynamic control algorithm has been developed based on Lyapunov optimization for monitoring the energy demand and the renewable energy generation. Various works related to the proposed method is listed in Table 1. The objective function used in the methods, type of charging, sensitivity, load modelling of EVs, and uncertainty are described in Table 1.Table 1
Taxonomy table for the proposed SAAT-APHA.
Author, yearMethod usedV2G schemeObjective functionCharging typeSensitivity analysisLoad modellingUncertaintyMoradijoz et al., 2013 [35]GAYPower loss cost, reliability cost, cost of purchased energy, capital cost, and revenue costL2NPNPNPPashajavid and Golkar, 2013 [36]PSONCost of bus voltage deviation and grid power loss cost—NPPPSadeghi-Barzani et al., 2014 [37]GANEV loss costs, station electrification, grid loss, and station developmentL3NPNPNPEl-Zonkoly and dos santos Coelho, 2015 [38]Abc, FANGarage charging/discharging costs, power from DER, power loss, and power from the gridL1NPNPNPZhang et al., 2016 [39]PSONTime costs, electricity investment, and operation.L3PPPKazemi et al., 2016 [40]GA, LPYDN operator profit, EV owner profit, operating and maintenance cost, and investment cost.L2NPPPAmini et al., 2017 [41]GA, PSONPower loss cost, reliability, bus attraction of EVs, and land cost.L1, L3NPPPIslam et al., 2018 [42]BLSANSubstation energy loss cost, station buildup cost, and transportation energy loss cost.L3NPNPNPJiang et al., 2018 [43]MAS simulationNPower loss voltage deviation, charging travel time, charging waiting time, and charging cost.L3NPNPNPHosseini and Sarder, 2019 [44]BNNSocial criterion cost, technical, economic, and environmental.L3PPPShukla et al. [45]GWONPower loss cost and EV flowL3PPPHadian et al., 2020MPSONBenefit of DSO and EVCSL2NPPPSengupta and data, 2021 [46]BPSONCumulative voltage deviation and power loss cost,L3PNPNPBitencourt, 2021 [47]BANPower loss cost, charging zone deviation, and environmental.L3NPPPGA: genetic algorithm, PSO: particle swarm optimization, ABC: artificial bee colony, FA: firefly algorithm, LP: linear programming, BLSA: binary lightning search algorithm, MAS: multiagent system, BN: Bayesian network, GWO: grey wolf optimization, MOPSO: multiobjective particle swarm optimization, BPSO: binary PSO, BA: ABT algorithm, L1, L2, and L3: slow, medium, and fast charging; P: performed, and NP: not performed.


### 2.1. Findings of the Literature Review and Contribution of This Paper

From the above literature, it is found that several issues have not been solved in the existing work.(i)
There is currently no research on long-term expansion decisions of charging stations and short-term operational decisions on an hourly basis under the same framework. It leads to inaccuracy in cost estimation.(ii)
In the existing decision, researchers did not consider alternate energy resources and reliable sources.(iii)
The decision model has less accuracy and needs improvement.In this study, the above issues have been solved. The main contribution of the study is as follows:(i)
The proposed EVCS has integrated both the long-term planning decision and short-term operational decision under the same framework.(ii)
A hybrid decomposition algorithm has been proposed which combines both the apriori progressive hedging algorithm and sample average approximation technique.(iii)
The performance of the proposed EVCS has been compared with that of other three state-of-art methods.


## 2.1. Findings of the Literature Review and Contribution of This Paper

From the above literature, it is found that several issues have not been solved in the existing work.(i)
There is currently no research on long-term expansion decisions of charging stations and short-term operational decisions on an hourly basis under the same framework. It leads to inaccuracy in cost estimation.(ii)
In the existing decision, researchers did not consider alternate energy resources and reliable sources.(iii)
The decision model has less accuracy and needs improvement.In this study, the above issues have been solved. The main contribution of the study is as follows:(i)
The proposed EVCS has integrated both the long-term planning decision and short-term operational decision under the same framework.(ii)
A hybrid decomposition algorithm has been proposed which combines both the apriori progressive hedging algorithm and sample average approximation technique.(iii)
The performance of the proposed EVCS has been compared with that of other three state-of-art methods.


## 3. Problem Description and Model Formulation

This section deals with the description of the problem, and then the two-stage mixed-integer linear programming (MILP) model has been discussed to minimize the cost of electricity flow when compared to other established charging stations. It efficiently met the demands of electricity.


### 3.1. Problem Description

A two-stage MILP model was developed under random power demand and previously specified planning horizon that addressed long-term expansion decisions of charging station and short-term operational decisions on an hourly basis. Therefore, a set of cells were made by dividing the transportation network, and each cell denoted a specific location to set a charging station over a set of hours and a set of years.A two-way connection was established between the EV charging station and the power grid (PG); therefore, the charging station could buy electricity from the grid when needed or it could sell the electricity back to the grid through battery-to-grid when profitable. Based on the capacity of electric supply, two different types of charging station were utilized in this research. In type-I charging stations, PG, RES, and V2G were used as power sources. In type-II, swappable batteries were used in addition to power sources used in the type-I charging stations. Four different energy sources such as PG, stored batteries, RES (solar and wind power), and power discharge of EVs into the grid through V2G connection were used to supply the electricity to the charging station. The PV panels are used to provide electricity when sun light is available. It absorbs the sun’s rays and converts them into electricity. It consists of a collection of solar (or photovoltaic) cells, which can be used to generate electricity through photovoltaic effect. Figure1 shows the integration of different energy sources with a charging station.Figure 1
Various energy sources integrated with a charging station.Large budget was needed for the long-term decisions and was required in advance for the whole predefined planning horizon. As an essential strategy, the long-term decision was applied in the charging station to meet the needs for charging the EVs. Therefore, several time-stages of equal length (for both hours and years) were predetermined whereas short-term operational decisions for 24-hour period were decided as a representative from each year in the planning horizon. Even though the charging station required a continuous operation, a day was divided into 24 hours for easy traceability and it was equal to the whole year’s average demand. At the start of each year, a decision for opening the charging stations was made.Estimation of the flow of the EVs was quite challenging, and it depended upon traffic and the geometry of the road. We estimated the flow in the following ways:(i)
A routing algorithm was developed in such a way that the number of vehicles passing through each link of the physical network was obtained by deploying the EVs from multiple sources to the endpoint.(ii)
From the previous result, cells on the network were developed. In consequence, the number of the EVs passing through each cell was estimated for a given period.The flow of the EV also varies from hour to hour. Hence, in case of the two-stage programming model, it was mandatory to check a large set of data to estimate the flow of the EV. Indeed, the availability of the EVs in the tested region helped to predict the availability of the EVs in the future. Monte Carlo simulation was used to simulate the flow of the EVs in the tested region. Each cell demand was considered as an uncertain variable, and the probability distribution was not known in advance. Each cell demand was estimated based on the expected number of the EVs passing through the cell, and the percentage of the vehicles was calculated for each scenario. In the same manner, the availability of V2G electricity was estimated based on the percentage of vehicles to be discharged for each scenario. With this, we predicted the choice of drivers in terms of charging station.


### 3.2. Solution Approach

Amina and Roussons introduced nonlinear programming (NLP) for an incapacitated facility location problem (IFLP) [48]. The problem specified in this paper can also be considered as a special case of the IFLP under the following conditions:(1)
Time period is one, i.e., |T| = 1 and |K| = 1(2)
PG fulfils the primary electricity demand (Yntka&Rntka=0∀nϵN,tϵT,kϵK,aϵA)(3)
One demand scenario is considered, i.e., |A| = 1(4)
No power shortage because there is no restriction on the consumption of PG(5)
Charging price does not rely on the power usage at each period (|R| = 1)(6)
In Type-I charging stations, battery-related activities are not taken into account, i.e.,Dntka,LntkA,Qntka,BntkA=0,nϵN,tϵT,kϵK,aϵA(7)
Type-I charging station is considered in this study, i.e., |K| = 1Thus, it is concluded that the problem mentioned in this paper is an NLP-hard problem and it cannot be solved in polynomial time. Commercial solvers (CPLEX and GUROBI) cannot be used to solve such problems. The two-stage programming model optimized the planning decision including the size of the charging station, location, several battery storages, renewable energy, grid power usage, and power through B2G. Moreover, the existing models do not integrate short-term operational and long-term planning decisions under the same framework. To overcome these difficulties, a hybrid decomposition algorithm was proposed which combines APHA with SAAT. The performance of the progressive hedging algorithm is improved by applying heuristic strategies [49].


### 3.3. Two-Stage Stochastic Model

This section introduces a two-stage decision variable for the two-stage charging station expansion problem. Stage-I decision variables indicate the type, location, and year to open a charging station. It can be expressed as follows:(1)Znsk=1,if station is opened∀nϵN,sϵS,kϵK,0,otherwise.The II-stage decision variable includesD=DntkanϵN,tϵT,kϵK,a∈A, which represents the number of batteries demanded at cell nϵN,tϵT,kϵK under scenario aϵAF=FntkAnϵN,tϵT,kϵK,a∈A, which represents the amount of energy storage at cell nϵN,tϵT,kϵK under scenario aϵAL=LntkAnϵN,tϵT,kϵK,a∈A, which represents the number of batteries charging at cell nϵN,tϵT,kϵK under scenario aϵAQ=QntkAnϵN,tϵT,kϵK,a∈A, which represents the number of fully charged batteries at cell nϵN,tϵT,kϵK under scenario aϵAB=BntkAnϵN,tϵT,kϵK,a∈A, which represents the number of batteries discharging at cell nϵN,tϵT,kϵK under scenario aϵAY=YntkAnϵN,tϵT,kϵK,a∈A, which represents the demand of cell satisfied by V2G power at cell nϵN,tϵT,kϵK under scenario aϵAE=EntkAnϵN,tϵT,kϵK,a∈A, which represents the demand of cell satisfied through grid power at cell nϵN,tϵT,kϵK under scenario aϵAR=RntkAnϵN,tϵT,kϵK,a∈A, which represents the demand of cell satisfied by renewable power at cell nϵN,tϵT,kϵK under scenario aϵAThe objective function model aims to minimize the cost of locating charging stations in the I-stage and cost of the II-stage expected value. The MILP model for the two-stage electric vehicle charging station can be expressed as follows:(2)Minimizez∈Z∑n∈N∑s∈S∑k∈KZnsk+∑a∈APaGZ,a,subject to(3)∑s∈SZnsk≤1∀nεN,kεK,Znsk−1≤Znsk∀nϵN,sϵS,kϵKZnsk∈0,1∀nϵN,sϵS,kϵKGZ,a=MinimizeD,F,L,Q,B,Y,E,R∑n∈N∑t∈T∑k∈KvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntka+μtkFntkA+ΩtkQntka−ηtkBntkA.The objective function (equation (1)) was the sum of the cost of the stage-I and the expected value of cost of stage-II. The yearly maintenance and construction cost of the charging station was minimized by the first-stage decisions. The first constraint guaranteed that at least one EVCS was installed in a given cell. The second constraints indicated that the EVCS was already installed in previous years and was under operation in the successive years. The third constraint sets the limit (binary) for stage-I.


### 3.4. Power Grid Terminology

The power grid or electrical grid was an interconnected electrical network used to distribute electricity from the generation station. It consisted of electricity generating stations (EGSs), substations, high voltage transmission lines (HTLs), and distribution lines (DLs). The EGS produced electric power, and the substations stepped down and stepped up the electrical voltage for distribution and transmission, respectively. The DLs were connected to the individual customers, whereas the HTL carried power from remote sources to substations. Since large amount of energy could not be stored, the generated electricity was used. The power distribution grid had the capability to shift and distribute the electricity based on the requirement. The power grid is evolving technology, which can be used to sell the own generated electricity (solar and wind generator).Nowadays, microgrid being developed with digital technology for managing the resources efficiently, it is capable for interacting with the competitive network and modelled as a generic power system that contains a controller, storage asset, load, and a production asset. Based on the heterogeneous set of participants, the load profiles and asset capacities vary. The development of smart grid and the EVs create V-G technology. It turns the EV into ESS and allows storing excess energy from the EV battery to the grid.


## 3.1. Problem Description

A two-stage MILP model was developed under random power demand and previously specified planning horizon that addressed long-term expansion decisions of charging station and short-term operational decisions on an hourly basis. Therefore, a set of cells were made by dividing the transportation network, and each cell denoted a specific location to set a charging station over a set of hours and a set of years.A two-way connection was established between the EV charging station and the power grid (PG); therefore, the charging station could buy electricity from the grid when needed or it could sell the electricity back to the grid through battery-to-grid when profitable. Based on the capacity of electric supply, two different types of charging station were utilized in this research. In type-I charging stations, PG, RES, and V2G were used as power sources. In type-II, swappable batteries were used in addition to power sources used in the type-I charging stations. Four different energy sources such as PG, stored batteries, RES (solar and wind power), and power discharge of EVs into the grid through V2G connection were used to supply the electricity to the charging station. The PV panels are used to provide electricity when sun light is available. It absorbs the sun’s rays and converts them into electricity. It consists of a collection of solar (or photovoltaic) cells, which can be used to generate electricity through photovoltaic effect. Figure1 shows the integration of different energy sources with a charging station.Figure 1
Various energy sources integrated with a charging station.Large budget was needed for the long-term decisions and was required in advance for the whole predefined planning horizon. As an essential strategy, the long-term decision was applied in the charging station to meet the needs for charging the EVs. Therefore, several time-stages of equal length (for both hours and years) were predetermined whereas short-term operational decisions for 24-hour period were decided as a representative from each year in the planning horizon. Even though the charging station required a continuous operation, a day was divided into 24 hours for easy traceability and it was equal to the whole year’s average demand. At the start of each year, a decision for opening the charging stations was made.Estimation of the flow of the EVs was quite challenging, and it depended upon traffic and the geometry of the road. We estimated the flow in the following ways:(i)
A routing algorithm was developed in such a way that the number of vehicles passing through each link of the physical network was obtained by deploying the EVs from multiple sources to the endpoint.(ii)
From the previous result, cells on the network were developed. In consequence, the number of the EVs passing through each cell was estimated for a given period.The flow of the EV also varies from hour to hour. Hence, in case of the two-stage programming model, it was mandatory to check a large set of data to estimate the flow of the EV. Indeed, the availability of the EVs in the tested region helped to predict the availability of the EVs in the future. Monte Carlo simulation was used to simulate the flow of the EVs in the tested region. Each cell demand was considered as an uncertain variable, and the probability distribution was not known in advance. Each cell demand was estimated based on the expected number of the EVs passing through the cell, and the percentage of the vehicles was calculated for each scenario. In the same manner, the availability of V2G electricity was estimated based on the percentage of vehicles to be discharged for each scenario. With this, we predicted the choice of drivers in terms of charging station.


## 3.2. Solution Approach

Amina and Roussons introduced nonlinear programming (NLP) for an incapacitated facility location problem (IFLP) [48]. The problem specified in this paper can also be considered as a special case of the IFLP under the following conditions:(1)
Time period is one, i.e., |T| = 1 and |K| = 1(2)
PG fulfils the primary electricity demand (Yntka&Rntka=0∀nϵN,tϵT,kϵK,aϵA)(3)
One demand scenario is considered, i.e., |A| = 1(4)
No power shortage because there is no restriction on the consumption of PG(5)
Charging price does not rely on the power usage at each period (|R| = 1)(6)
In Type-I charging stations, battery-related activities are not taken into account, i.e.,Dntka,LntkA,Qntka,BntkA=0,nϵN,tϵT,kϵK,aϵA(7)
Type-I charging station is considered in this study, i.e., |K| = 1Thus, it is concluded that the problem mentioned in this paper is an NLP-hard problem and it cannot be solved in polynomial time. Commercial solvers (CPLEX and GUROBI) cannot be used to solve such problems. The two-stage programming model optimized the planning decision including the size of the charging station, location, several battery storages, renewable energy, grid power usage, and power through B2G. Moreover, the existing models do not integrate short-term operational and long-term planning decisions under the same framework. To overcome these difficulties, a hybrid decomposition algorithm was proposed which combines APHA with SAAT. The performance of the progressive hedging algorithm is improved by applying heuristic strategies [49].


## 3.3. Two-Stage Stochastic Model

This section introduces a two-stage decision variable for the two-stage charging station expansion problem. Stage-I decision variables indicate the type, location, and year to open a charging station. It can be expressed as follows:(1)Znsk=1,if station is opened∀nϵN,sϵS,kϵK,0,otherwise.The II-stage decision variable includesD=DntkanϵN,tϵT,kϵK,a∈A, which represents the number of batteries demanded at cell nϵN,tϵT,kϵK under scenario aϵAF=FntkAnϵN,tϵT,kϵK,a∈A, which represents the amount of energy storage at cell nϵN,tϵT,kϵK under scenario aϵAL=LntkAnϵN,tϵT,kϵK,a∈A, which represents the number of batteries charging at cell nϵN,tϵT,kϵK under scenario aϵAQ=QntkAnϵN,tϵT,kϵK,a∈A, which represents the number of fully charged batteries at cell nϵN,tϵT,kϵK under scenario aϵAB=BntkAnϵN,tϵT,kϵK,a∈A, which represents the number of batteries discharging at cell nϵN,tϵT,kϵK under scenario aϵAY=YntkAnϵN,tϵT,kϵK,a∈A, which represents the demand of cell satisfied by V2G power at cell nϵN,tϵT,kϵK under scenario aϵAE=EntkAnϵN,tϵT,kϵK,a∈A, which represents the demand of cell satisfied through grid power at cell nϵN,tϵT,kϵK under scenario aϵAR=RntkAnϵN,tϵT,kϵK,a∈A, which represents the demand of cell satisfied by renewable power at cell nϵN,tϵT,kϵK under scenario aϵAThe objective function model aims to minimize the cost of locating charging stations in the I-stage and cost of the II-stage expected value. The MILP model for the two-stage electric vehicle charging station can be expressed as follows:(2)Minimizez∈Z∑n∈N∑s∈S∑k∈KZnsk+∑a∈APaGZ,a,subject to(3)∑s∈SZnsk≤1∀nεN,kεK,Znsk−1≤Znsk∀nϵN,sϵS,kϵKZnsk∈0,1∀nϵN,sϵS,kϵKGZ,a=MinimizeD,F,L,Q,B,Y,E,R∑n∈N∑t∈T∑k∈KvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntka+μtkFntkA+ΩtkQntka−ηtkBntkA.The objective function (equation (1)) was the sum of the cost of the stage-I and the expected value of cost of stage-II. The yearly maintenance and construction cost of the charging station was minimized by the first-stage decisions. The first constraint guaranteed that at least one EVCS was installed in a given cell. The second constraints indicated that the EVCS was already installed in previous years and was under operation in the successive years. The third constraint sets the limit (binary) for stage-I.


## 3.4. Power Grid Terminology

The power grid or electrical grid was an interconnected electrical network used to distribute electricity from the generation station. It consisted of electricity generating stations (EGSs), substations, high voltage transmission lines (HTLs), and distribution lines (DLs). The EGS produced electric power, and the substations stepped down and stepped up the electrical voltage for distribution and transmission, respectively. The DLs were connected to the individual customers, whereas the HTL carried power from remote sources to substations. Since large amount of energy could not be stored, the generated electricity was used. The power distribution grid had the capability to shift and distribute the electricity based on the requirement. The power grid is evolving technology, which can be used to sell the own generated electricity (solar and wind generator).Nowadays, microgrid being developed with digital technology for managing the resources efficiently, it is capable for interacting with the competitive network and modelled as a generic power system that contains a controller, storage asset, load, and a production asset. Based on the heterogeneous set of participants, the load profiles and asset capacities vary. The development of smart grid and the EVs create V-G technology. It turns the EV into ESS and allows storing excess energy from the EV battery to the grid.


## 4. Proposed Algorithm

### 4.1. Sample Average Approximation

The hourly percentage of EV chargingctka in a charging station with “n” cells (nϵN) during “t” hour (tϵT) of k-th year (kϵK) is considered for sample average approximation. It differs from hour to hour for the year. It is mandatory to estimate a large set of data to give some information for the decision-makers. However, there are a lot of computational complexities while estimating these large sets of data for the electric vehicle charging problem. To overcome, a sampling technique called a sample average approximation technique (SAAT) was used to solve the problem without any complexity. SAAT was previously used to solve many network flow problems on a large scale [50, 51]. In SAAT, a sample a1, a2, ... aN of random vector a is generated from A and a normal probability distribution P was solved repeatedly to achieve a prespecified gap. The SAAT approximates the electric vehicle charging problem:(4)Minimizez∈ZVPy:∑n∈N∑s∈S∑k∈KγnskZnsk+1N∑i=1IGZ,i.When the sample size increases, the optimal solution of the above equation converges with probability one to an optimal solution of the original EVCS problem [52]. Assume that absolute optimality gap δ ≥ 0 and sample size “U” is estimated as follows:(5)U≥3σmax2τ−δ2NSKlog2−logφ,where τ > δ, φ∈0,1, and σmax2 is a maximal variation of certain function differences [28]. The SAAT gives a valid statistical lower and upper bound for the original problem in each iteration, and the process ends when the gap between the estimators is lesser than the prespecified threshold value. The following are the steps to solve the EVCS problem using the SAAT:Step 1. Generate Q independent scenarios for the percentage of the EV recharging with size Rn, i.e., cq1a,cq2a,…,cqRa,∀q=1,…,Q where c=ctka;∀tϵT,kϵK,aϵA. To solve the SAAT problem, each sample consists of N random scenarios.(6)Minimizez∈ZUPy:∑n∈N∑s∈S∑k∈KγnskZnsk+1U∑i=1IGZ,i,UPy is the optimal objective value and Z^Py is the optimal solution. Y = 1...Y.Step 2. The variance (σZ^Py2) and average (U¯Py) of the optimal solutions can be obtained by(7)σZ^Py2=1Q−1Q∑q=1QUPy−U¯Py2,whereZ¯Py is the lower bound value of the objective function for the charging station expansion problem; it is expressed as follows:(8)Z¯Py=1Q∑q=1QUPy.Step 3. Choose a feasible solution (U˜∈U) from Step 1 of the SAAT, and estimate the original objective function for the problem using the reference sample N′ which is expressed as follows:(9)wN′˜U˜≅∑n∈N∑s∈S∑k∈KγnskZnsk+1U′∑n=1N′GZ,i.The estimatorwN′˜U˜ provides an upper bound for the vehicle charging problem. The sample size was chosen larger value, i.e., N′≫N [38]. The variance can be expressed as follows:(10)σN′2V˜=1N′−1N∑x=1X′∑n∈N∑s∈S∑k∈KγnskZnsk+GZ,i−wN′˜U˜2,whereGZ,i is the solution including all the constraints of the problem.Step 4. From the steps 2 and 3, find the optimality gap (Ogap), and its variance (σOgap2) can be expressed as follows:(11)OgapU˜=wN′˜U˜−U¯Py,σOgap2=σN′2U˜−σZ^Py2.


### 4.2. Progressive Hedging Algorithm

A two-stage programming model was used to solve the SAAT, including N scenarios. The computational performance of the SAAT depends onN,K,T which provide a significant impact on the charging station expansion problem. Decomposition methods are often used to divide a large problem into manageable subproblems [53]. This encourages the authors to solve subproblems of the SAAT using the APHA. Various applications solved using the APHA provides high-quality solution [54, 55]. The two-stage objective function for the EVCS expansion can be expressed as follows:(12)MinimizeD,F,L,Q,B,Y,E,R∑x∈X∑t∈T∑k∈K1X∑s∈Sγnskznskq∑t∈TvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntka+μtkFntkA+ΩtkQntka−ηtkBntkA,Subject to(13)∑s∈SZnsk≤1∀nϵN,kϵK,x∈X,Znsk−1≤Znsk∀nϵN,sϵS,kϵK,x∈X,Znsk∈0,1∀nϵN,sϵS,kϵK,x∈X,Entka+Rntka+Yntka≥∑s∈Smka1znskq∀nϵN,sϵS,kϵK,t∈T,x∈X,maxβentkctka−dntk+rntk+αctkaentkβ,0znskqDntka∀nϵN,kϵK,t∈T,s=s2,x∈XQntka≤bkznskq∀nϵN,kϵK,t∈T,s=s2,x∈XLntka≤jkinznskq∀nϵN,kϵK,t∈T,s=s2,x∈XBntkA≤jkoutznskq∀nϵN,kϵK,t∈T,s=s2,x∈X.βDntka≥mka2znskq∀nϵN,kϵK,t∈T,s=s2,x∈XRntka≤∑s∈Srntkznskq∀nϵN,kϵK,t∈T,x∈XYntka≤∑s∈Sαctkaentkznskq∀nϵN,kϵK,t∈T,x∈XEntka≤∑s∈Sdntkznskq∀nϵN,kϵK,t∈T,x∈Xznskq∈0,1∀nϵN,kϵK,s∈S,x∈Xznskq=Z¯nsk∀nϵN,kϵK,s∈S,x∈XTo relax equation (13), the augmented Lagrangian strategy was followed in this study based on [56]. The objective function can be expressed as follows:(14)MinimizeD,F,L,Q,B,Y,E,R∑x=1X∑t∈T∑k∈K1X∑s∈Sγnskznskq+∑t∈TvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntkaμtkFntkAΩtkQntkaηtkBntkA∑s∈Sψnskqznskqz¯nsk12∑s∈Sπznskqz¯nsk2.The Lagrangian multiplierψnskq was used to relax the constraints and π represent the penalty ratio. After solving the quadratic term of equation (14), the above objective function can be expressed as shown in [55] as follows:(15)MinimizeD,F,L,Q,B,Y,E,R∑x=1X∑t∈T∑k∈K1X∑s∈Sγnsk+ψnskq−πznskq+π2znskq+∑t∈TvtkPGEntkavtksRntkavtkPGβDntkaVtkV−GYntkaμtkFntkAΩtkQntkaηtkBntkA−∑s∈Sψnskqznskq+12∑s∈Sπz¯nsk.The last two terms of equation (15) become constant when the value of z¯nsk is fixed. Therefore, this term can be removed. This will permit us to decompose the subproblem by the scenarios xЄX. The overall problem can be expressed including each scenario as shown in [56] as follows:(16)MinimizeD,F,L,Q,B,Y,E,R∑t∈T∑k∈K∑s∈Sγnsk+ψnskq−πznskq+π2znskq+∑t∈TvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntka+μtkFntkA+ΩtkQntka−ηtkBntkA.For more details, the authors can refer [55, 56]. The progressive hedging algorithm terminates if it satisfies any one of the following conditions:(i)
The predefined tolerance gapξ≥∑n∈N∑s∈S∑k∈Kznskq−z¯nsk(ii)
The maximum number of iterations,Imax = 100(iii)
Maximum number of consecutive nonimprovement iterations,IN = 10(iv)
Maximum time limit,Tmax = 500 seconds


### 4.3. The Apriori Progressive Hedging Algorithm

Although the progressive hedging algorithm provides faster convergence, it failed to give a better solution in large problems and motivated the authors to improve the basic progressive hedging algorithm including heuristic strategies. Two different heuristic strategies such as the local heuristic and the global heuristic were included to enhance the performance of the progressive hedging algorithm [56]. The local heuristic adjusted the value of γnsk within the scenario level whereas the global heuristic adjusted the value of γnsk at the end of each iteration.The EVCS expansion problem was decomposed intoM subproblems. At the end of each iteration, the parameter z¯nsk provided information about the charging station of type sЄS and number of stations opened in cell nЄN of year kЄK. When z¯nsk was higher, the charging station of type sЄS was placed in the cell nЄN at year kЄK indicative to the previous repeated iterations. On the other hand, a lower value of z¯nsk points out that most of the previous iterations did not follow favourable decisions. UL and LL denoted the upper and lower limit of the threshold values, respectively. The fixed cost of opening an EVCS station was lower when z¯nsk>UL. In the same way, z¯nsk<LL; then, the fixed cost of opening an EVCS station was increased. The global adjustment strategy can be expressed as follows:(17)γnskj=Sγnskj−1ifznskj−1>LL1Sγnskjifz¯nskj−1>ULγnskj−1otherwise,where γnskj is the modified fixed cost of opening an EVCS of type sϵS at cell nϵN in year kϵK and j represents the iteration. The upper and lower limits are set to 0 < LL < 0.3 and 0.7 < UL < 1. The local heuristic strategy can be expressed as follows:(18)γnski,j=Sγnskiifznski,j−1−z¯nskj≥Trznskj−1=11Sγnskjifznski,j−1−z¯nskj≥Trznskj−1=0γnskjotherwise,where γnski,j is the modified γnsk opening an electric vehicle charging station of type sϵS at cell nϵN in year kϵK under aϵA scenario at iteration j. The threshold value selected in this study is 0.5 < Tr < 1. The performance of the progressive hedging algorithm was increased locally within the scenario but it required many trial vectors and many iterations [57] and decreased the efficiency. To overcome this limitation, we have introduced an apriori method for increasing the processing speed thus ensuring faster convergence and increased efficiency.The apriori method created a high-dimensional frequent set of items with lengthL from the low-dimensional frequent sets with length L-1 over the database [58]. To determine the frequent set of items in the database, an example is illustrated in Figure 2. Initially, the number of occurrences of each member should be identified. Generate the first set of items from the database for size 1. In the second step, all pairs of frequent items were generated [59]. Here, except for the pair {1,3}, all the pairs were the frequent set of items, and the larger set which contains {1,3} could not be the frequent. As a result, the pair {1,3} was pruned (assume that below the threshold). In the third step, the triple containing the pair {1,3} was excluded.Figure 2
Example of apriori method.The sets {1,2,3} and {1,2,4} were the superset of the pair {1,3}, and the set {2,3,4} was below the minimum threshold and was excluded. Thus, the processing speed of the progressive hedge algorithm increases by including apriori algorithm. Algorithm 1 showed the high-level pseudo-code for the apriori method.Algorithm 1: Apriori algorithm.
(1)
Output: F_freq,FN, N = 1,2.(2)
Input: setting minimum threshold (Tmin), Datasets (DN).(3)
Initialize,N = 1, F1 = Ф;(4)
Estimate the first itemset F1, with support = Tmin(5)
N = 2;(6)
while FN-1 ≠ Ф(7)
AN = Ф;(8)
% steps used for combining(9)
Take each items in FN-1, combine with F itemsets, and generate a new candidate (Knew).(10)
for each item inKnew(11)
if length of the item = = N & support =Tmin(12)
add item inAN(13)
end(14)
end(15)
% Prune item(16)
Duplicate itemsets present inAN can be removed(17)
The elements inAN that are often used can be pruned.(18)
AddAN into FN;(19)
N=N+1; end(20)
end(21)
ReturnFN.


## 4.1. Sample Average Approximation

The hourly percentage of EV chargingctka in a charging station with “n” cells (nϵN) during “t” hour (tϵT) of k-th year (kϵK) is considered for sample average approximation. It differs from hour to hour for the year. It is mandatory to estimate a large set of data to give some information for the decision-makers. However, there are a lot of computational complexities while estimating these large sets of data for the electric vehicle charging problem. To overcome, a sampling technique called a sample average approximation technique (SAAT) was used to solve the problem without any complexity. SAAT was previously used to solve many network flow problems on a large scale [50, 51]. In SAAT, a sample a1, a2, ... aN of random vector a is generated from A and a normal probability distribution P was solved repeatedly to achieve a prespecified gap. The SAAT approximates the electric vehicle charging problem:(4)Minimizez∈ZVPy:∑n∈N∑s∈S∑k∈KγnskZnsk+1N∑i=1IGZ,i.When the sample size increases, the optimal solution of the above equation converges with probability one to an optimal solution of the original EVCS problem [52]. Assume that absolute optimality gap δ ≥ 0 and sample size “U” is estimated as follows:(5)U≥3σmax2τ−δ2NSKlog2−logφ,where τ > δ, φ∈0,1, and σmax2 is a maximal variation of certain function differences [28]. The SAAT gives a valid statistical lower and upper bound for the original problem in each iteration, and the process ends when the gap between the estimators is lesser than the prespecified threshold value. The following are the steps to solve the EVCS problem using the SAAT:Step 1. Generate Q independent scenarios for the percentage of the EV recharging with size Rn, i.e., cq1a,cq2a,…,cqRa,∀q=1,…,Q where c=ctka;∀tϵT,kϵK,aϵA. To solve the SAAT problem, each sample consists of N random scenarios.(6)Minimizez∈ZUPy:∑n∈N∑s∈S∑k∈KγnskZnsk+1U∑i=1IGZ,i,UPy is the optimal objective value and Z^Py is the optimal solution. Y = 1...Y.Step 2. The variance (σZ^Py2) and average (U¯Py) of the optimal solutions can be obtained by(7)σZ^Py2=1Q−1Q∑q=1QUPy−U¯Py2,whereZ¯Py is the lower bound value of the objective function for the charging station expansion problem; it is expressed as follows:(8)Z¯Py=1Q∑q=1QUPy.Step 3. Choose a feasible solution (U˜∈U) from Step 1 of the SAAT, and estimate the original objective function for the problem using the reference sample N′ which is expressed as follows:(9)wN′˜U˜≅∑n∈N∑s∈S∑k∈KγnskZnsk+1U′∑n=1N′GZ,i.The estimatorwN′˜U˜ provides an upper bound for the vehicle charging problem. The sample size was chosen larger value, i.e., N′≫N [38]. The variance can be expressed as follows:(10)σN′2V˜=1N′−1N∑x=1X′∑n∈N∑s∈S∑k∈KγnskZnsk+GZ,i−wN′˜U˜2,whereGZ,i is the solution including all the constraints of the problem.Step 4. From the steps 2 and 3, find the optimality gap (Ogap), and its variance (σOgap2) can be expressed as follows:(11)OgapU˜=wN′˜U˜−U¯Py,σOgap2=σN′2U˜−σZ^Py2.


## 4.2. Progressive Hedging Algorithm

A two-stage programming model was used to solve the SAAT, including N scenarios. The computational performance of the SAAT depends onN,K,T which provide a significant impact on the charging station expansion problem. Decomposition methods are often used to divide a large problem into manageable subproblems [53]. This encourages the authors to solve subproblems of the SAAT using the APHA. Various applications solved using the APHA provides high-quality solution [54, 55]. The two-stage objective function for the EVCS expansion can be expressed as follows:(12)MinimizeD,F,L,Q,B,Y,E,R∑x∈X∑t∈T∑k∈K1X∑s∈Sγnskznskq∑t∈TvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntka+μtkFntkA+ΩtkQntka−ηtkBntkA,Subject to(13)∑s∈SZnsk≤1∀nϵN,kϵK,x∈X,Znsk−1≤Znsk∀nϵN,sϵS,kϵK,x∈X,Znsk∈0,1∀nϵN,sϵS,kϵK,x∈X,Entka+Rntka+Yntka≥∑s∈Smka1znskq∀nϵN,sϵS,kϵK,t∈T,x∈X,maxβentkctka−dntk+rntk+αctkaentkβ,0znskqDntka∀nϵN,kϵK,t∈T,s=s2,x∈XQntka≤bkznskq∀nϵN,kϵK,t∈T,s=s2,x∈XLntka≤jkinznskq∀nϵN,kϵK,t∈T,s=s2,x∈XBntkA≤jkoutznskq∀nϵN,kϵK,t∈T,s=s2,x∈X.βDntka≥mka2znskq∀nϵN,kϵK,t∈T,s=s2,x∈XRntka≤∑s∈Srntkznskq∀nϵN,kϵK,t∈T,x∈XYntka≤∑s∈Sαctkaentkznskq∀nϵN,kϵK,t∈T,x∈XEntka≤∑s∈Sdntkznskq∀nϵN,kϵK,t∈T,x∈Xznskq∈0,1∀nϵN,kϵK,s∈S,x∈Xznskq=Z¯nsk∀nϵN,kϵK,s∈S,x∈XTo relax equation (13), the augmented Lagrangian strategy was followed in this study based on [56]. The objective function can be expressed as follows:(14)MinimizeD,F,L,Q,B,Y,E,R∑x=1X∑t∈T∑k∈K1X∑s∈Sγnskznskq+∑t∈TvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntkaμtkFntkAΩtkQntkaηtkBntkA∑s∈Sψnskqznskqz¯nsk12∑s∈Sπznskqz¯nsk2.The Lagrangian multiplierψnskq was used to relax the constraints and π represent the penalty ratio. After solving the quadratic term of equation (14), the above objective function can be expressed as shown in [55] as follows:(15)MinimizeD,F,L,Q,B,Y,E,R∑x=1X∑t∈T∑k∈K1X∑s∈Sγnsk+ψnskq−πznskq+π2znskq+∑t∈TvtkPGEntkavtksRntkavtkPGβDntkaVtkV−GYntkaμtkFntkAΩtkQntkaηtkBntkA−∑s∈Sψnskqznskq+12∑s∈Sπz¯nsk.The last two terms of equation (15) become constant when the value of z¯nsk is fixed. Therefore, this term can be removed. This will permit us to decompose the subproblem by the scenarios xЄX. The overall problem can be expressed including each scenario as shown in [56] as follows:(16)MinimizeD,F,L,Q,B,Y,E,R∑t∈T∑k∈K∑s∈Sγnsk+ψnskq−πznskq+π2znskq+∑t∈TvtkPGEntka+vtksRntka+vtkPGβDntka+vtkV−GYntka+μtkFntkA+ΩtkQntka−ηtkBntkA.For more details, the authors can refer [55, 56]. The progressive hedging algorithm terminates if it satisfies any one of the following conditions:(i)
The predefined tolerance gapξ≥∑n∈N∑s∈S∑k∈Kznskq−z¯nsk(ii)
The maximum number of iterations,Imax = 100(iii)
Maximum number of consecutive nonimprovement iterations,IN = 10(iv)
Maximum time limit,Tmax = 500 seconds


## 4.3. The Apriori Progressive Hedging Algorithm

Although the progressive hedging algorithm provides faster convergence, it failed to give a better solution in large problems and motivated the authors to improve the basic progressive hedging algorithm including heuristic strategies. Two different heuristic strategies such as the local heuristic and the global heuristic were included to enhance the performance of the progressive hedging algorithm [56]. The local heuristic adjusted the value of γnsk within the scenario level whereas the global heuristic adjusted the value of γnsk at the end of each iteration.The EVCS expansion problem was decomposed intoM subproblems. At the end of each iteration, the parameter z¯nsk provided information about the charging station of type sЄS and number of stations opened in cell nЄN of year kЄK. When z¯nsk was higher, the charging station of type sЄS was placed in the cell nЄN at year kЄK indicative to the previous repeated iterations. On the other hand, a lower value of z¯nsk points out that most of the previous iterations did not follow favourable decisions. UL and LL denoted the upper and lower limit of the threshold values, respectively. The fixed cost of opening an EVCS station was lower when z¯nsk>UL. In the same way, z¯nsk<LL; then, the fixed cost of opening an EVCS station was increased. The global adjustment strategy can be expressed as follows:(17)γnskj=Sγnskj−1ifznskj−1>LL1Sγnskjifz¯nskj−1>ULγnskj−1otherwise,where γnskj is the modified fixed cost of opening an EVCS of type sϵS at cell nϵN in year kϵK and j represents the iteration. The upper and lower limits are set to 0 < LL < 0.3 and 0.7 < UL < 1. The local heuristic strategy can be expressed as follows:(18)γnski,j=Sγnskiifznski,j−1−z¯nskj≥Trznskj−1=11Sγnskjifznski,j−1−z¯nskj≥Trznskj−1=0γnskjotherwise,where γnski,j is the modified γnsk opening an electric vehicle charging station of type sϵS at cell nϵN in year kϵK under aϵA scenario at iteration j. The threshold value selected in this study is 0.5 < Tr < 1. The performance of the progressive hedging algorithm was increased locally within the scenario but it required many trial vectors and many iterations [57] and decreased the efficiency. To overcome this limitation, we have introduced an apriori method for increasing the processing speed thus ensuring faster convergence and increased efficiency.The apriori method created a high-dimensional frequent set of items with lengthL from the low-dimensional frequent sets with length L-1 over the database [58]. To determine the frequent set of items in the database, an example is illustrated in Figure 2. Initially, the number of occurrences of each member should be identified. Generate the first set of items from the database for size 1. In the second step, all pairs of frequent items were generated [59]. Here, except for the pair {1,3}, all the pairs were the frequent set of items, and the larger set which contains {1,3} could not be the frequent. As a result, the pair {1,3} was pruned (assume that below the threshold). In the third step, the triple containing the pair {1,3} was excluded.Figure 2
Example of apriori method.The sets {1,2,3} and {1,2,4} were the superset of the pair {1,3}, and the set {2,3,4} was below the minimum threshold and was excluded. Thus, the processing speed of the progressive hedge algorithm increases by including apriori algorithm. Algorithm 1 showed the high-level pseudo-code for the apriori method.Algorithm 1: Apriori algorithm.
(1)
Output: F_freq,FN, N = 1,2.(2)
Input: setting minimum threshold (Tmin), Datasets (DN).(3)
Initialize,N = 1, F1 = Ф;(4)
Estimate the first itemset F1, with support = Tmin(5)
N = 2;(6)
while FN-1 ≠ Ф(7)
AN = Ф;(8)
% steps used for combining(9)
Take each items in FN-1, combine with F itemsets, and generate a new candidate (Knew).(10)
for each item inKnew(11)
if length of the item = = N & support =Tmin(12)
add item inAN(13)
end(14)
end(15)
% Prune item(16)
Duplicate itemsets present inAN can be removed(17)
The elements inAN that are often used can be pruned.(18)
AddAN into FN;(19)
N=N+1; end(20)
end(21)
ReturnFN.


## 5. Results and Discussion

To analyze the performances of the algorithms, the solar panel of 25 kW, wind turbine of 25 kW, and 12 kW microturbine with a two-energy storage system of 10 kW and 25 kW were considered. The fuel cost of the microturbine was 0.18 Euro/kWh. The cost for installing different resources and the functional cost are listed in Table2. The algorithm was coded in GAMS24.2.1 [45], and Intel core i5, 4.4 GHz was used as a processor with 16 GB RAM for execution. The design of the electricity supply network was determined by the annual decision on established charging stations. Therefore, there was difference in critical factors that changed the network design. Available energy resources, the impact of the percentage of the vehicle charging, minimum power required to develop a charging station, and the utilization of renewable power have been analyzed. Input parameters required for the case study, the results of the experimental studies, and the performance of the hybrid sample average approximation-based apriori progressive hedging algorithm have been discussed in the following section.Table 2
Installation and functional cost of different resources.
ResourcesInvestment cost (Euro/kW)Operational cost (Euro/kWh)Maintenance cost (Euro/kWh)Wind power11800.10.05Solar power19000.050.05Power of microturbine5500.150.10Capacity of energy storage5000.10.05Power of energy storage5500.050.05


### 5.1. Input Parameter Setting

A network was divided into cells (|N| = 50), and each cell covered an area of one mile. The specific parameters were the cells that were obtained only if there was a road passing through it or else when the value for these cells was considered as zero. Thus, only the active cells were considered as a potential location for installing a charging station. The five-year (|K| = 5) planning horizon was considered and started from 2018 and will end in 2022. For short-term operational decisions, a period of 24 hours (|T| = 24) was chosen (6 am to 5 am) as a representative from each year of the planning horizon. We assumed that all the cost components were estimated based on the 2019 Euro rate and were adjusted depending upon inflation. A fast EVCS station (γnsk1) at cell “n” costs around 50,100 Euro [60], and the charging station with a battery swap station (γnsk2) costs around 501,000 Euro [61]. The EV charging was adopted using V-G technology. It was capable of charging four EVs at the same time. The hourly profile of renewable energy, including load, is presented in Table 3. The data used in Table 3 are taken from a prior study [62, 63].Table 3
Hourly profile of renewable sources with load.
HourSolar power (%)Wind power (%)Load power (%)Electricity price (Euro/kWh)610501010715551510825603010940724510106582651011857095151210085100151310070951514908780151580757515165565702017354580201810588520190657020200100752021085702022090657230755072406040510552052045205307010540651055070105


### 5.2. Impact of Vehicle Charging Percentage Variabilityctka on System Performance

Three different scenarios were created to show the impact of vehicle charging percentage variation on the system performance. In the first scenario, the EVCS model was solved using the input parameters (base case). The charging percentage variation wasε=10% (low variation) and ε=50% (high variation) for the second and third scenarios, respectively. The Monte Carlo method was used to generate different vehicle charging (ctka) scenarios between c˜tka1−ε,c˜tka1+ε where c˜tka represents the mean vehicle charging percentage scenario for each hour t∈T in year k∈K.The impact of vehicle charging percentage variability on system performance is shown in Figure3. Results show that the amount of power used to meet the demand for electricity from different power sources such as solar, grid, and V2G was increased when the level of vehicle charging percentage variability ctka was increased. Hourly operational decisions of a charging station located in the cell n∈N of a given year k∈K depended on variables, such as solar power availability, the flow of vehicles, and electricity prices. When solar power was not available (i.e., from 6.00 pm to 7.00 am), demand for electric power was met through the grid and V-G. During peak hours and when solar power was available (i.e., from 7.00 am to 6.00 pm), demand was fulfilled mainly through renewable energy and then through the grid and V-G. Figure 4 shows the impact of vehicle charging percentage variability on the battery-related decision when type-II charging stations were installed in the tested region. To manage the high power demand, the batteries were charged during the off-peak hours in the charging station and discharged during the peak hours which are shown in Figures 4(a) and 4(b), respectively. Since more batteries were charged during the off-peak hours, more batteries were kept in the charging stations. The number of batteries demanded at the cell and the number of full batteries are shown in Figures 4(c) and 4(d), respectively.Figure 3
Impact of different resources utilization for vehicle charging (ckA): (a) average demand of cell satisfied through grid power, E¯ntka; (b) average demand of cell satisfied through renewable power, R¯ntka; (c) average demand of cell satisfied by V-G power, y¯ntka.
(a)(b)(c)Figure 4
Impact of real-time demand on vehicle charging percentage variability (ckA): (a) average number of batteries charging at the cell, L¯ntkA; (b) average number of batteries discharging at the cell, B¯ntkA; (c) average number of batteries demanded in the cell, D¯ntkA; (d) average number of batteries fully charged batteries in the cell, Q¯ntkA.
(a)(b)(c)(d)


### 5.3. Impact ofdntk, rntk, and htn on System Performance

The proposed EVCS model depends on three different parameters: renewable energy available at cellrntk, availability of grid power at cell dntk, and V-G power, which in turn depends on the percentage discharging htn. Any change in the availability of the power will deviate from the necessary quality of the operation, and hence it should be measured and carefully estimated. To verify the impact of these parameters, four sets of experiments were conducted by varying their availability by ±25% and ±40% from the base case scenario, and they are shown in Figures 5–7. The performance of the system based on grid power availability dntk is shown in Figure 5. Renewable power and availability of V-G power were kept at their base values. When the availability of grid power was increased, the average utilization of grid power Entka also increases as shown in Figure 5(a). However, when the availability of grid power was decreased by 40%, 42.75% of supplementary stations are installed to meet the demand of the EV charging as shown in Figure 5(b).Figure 5
Impact of grid power on the system performance:(a) availability of grid powerdntk and (b) variability of grid power.
(a)(b)Figure 6
Impact of renewable power on the system performance: (a) availability of renewable powerrntk and (b) variability of renewable power.
(a)(b)Figure 7
Impact of V-G power on the system performance: (a) availability discharged power of vehiclehtn (b) variability of discharged power of vehicle.
(a)(b)In the case of renewable energy, when the availability was decreased by 40%, 18.96% of additional charging stations were installed to meet the power demanded. When comparing the impact of the unavailability of renewable power on system performance with that of impact due to the unavailability of grid power, renewable power is less sensitive than grid power unavailability. When the source was available, the average utilization of renewable energyrntka increased in a charging station and it is shown in Figure 6(a). On the other hand, when rntk was decreased, the requirement of recharging stations was also increased. The percentage of rntk on the system performance is illustrated in Figure 6(b). The performance of the availability of V-G power depends on the system performance (Figure 7). When the availability of V-G power was increased, the average utilization of V-G power was also increased, as is shown in Figure 7(a).An additional 14.70% of charging stations were installed for a 50% decrease inhtn, and it is illustrated in Figure 7(b). Results showed that system had less impact on a V-G energy source when compared to the unavailability of the grid and renewable power. This is since the grid was followed by renewable energy and was the main source of energy for the charging stations and the unavailability of these sources affected the system severely when compared to V-G power. Finally, it was concluded that long-term charging station location decisions and short-term hourly operational decisions depend on the availability of grid, renewable, and V-G energy.


### 5.4. Results of Charging Station on an Expansion Plan

The EVCS was considered as a flexible load on the microgrid by optimizing the charging process. In some cases, the interval charging station can act as a generating unit because of the V-G technology. To study the impact of the charging station on the expansion, the model was simulated without V-G technology, i.e., power was not flowed in to the microgrid (Table4) and there was an enhancement in the total cost of expansion by 28%. It shows that large-capacity resources are needed by the microgrid to compensate for load growth.Table 4
Expansion plan without V-G technology.
ResourcesAnnual expansion cost (Euro/year)Wind power (kW)22,210.53Solar power (kW)1350.25Microturbine (kW)29,742.48Capacity of energy storage (kWh)8245.87Power of energy storage (kW)935.53Total cost of expansion (Euro/year)62,484.66The resources with various capacities that were needed to cope with the load growth for the five-year planning horizon are listed in Table5. The profile of wind energy was larger than solar energy; therefore, the growth of wind energy was more than that of solar energy. Consequently, the microgrid cropped more energy through the connected wind turbines. It was noticed that 54.7% of microturbines were installed in the fifth year of the planning horizon for managing the load growth. Lastly, the capacity and power of the ESS were expanded in different years to shift the power based on the peak hour load. Figure 8 shows the power exchanged between the upstream to the microgrid during a day for the five-year planning horizon. The capacity between the upstream to the microgrid was 230 kW. As a result, the maximum traded power was 230 kW. It was noted that load growth is managed by the available resources and new installed resources. Because of the limited trading power, the load demand should be managed by installing new resources (solar, wind, ESS, and microturbine). To manage the load efficiently, the model optimized the newly installed resources. The operation of the ESS in the planning horizon during the five years is shown in Figure 9. The load was shifted from the higher price to the lower price for saving costs and to avoid peak-loading problems.Table 5
Percentage of resources expansion for the five-year planning horizon.
ResourcesYear 2019 (%)Year 2020 (%)Year 2021 (%)Year 2022 (%)Year 2023 (%)Wind power1008522.4——Solar power1015—21.6—Power of microturbine————54.7Capacity of energy storage10020.518.417.5—Power of energy storage—10.342.737.3—Figure 8
Power exchanged between upstream network and microgrid during a day of the five years planning horizon.Figure 9
Operation of the ESS during a day of the planning horizon.To minimize the cost, the operation of the ESS and the microturbine was optimized during the short-term operation of the proposed expansion plan. The five-year operation of the microturbine expansion horizon is shown in Figure10. The microturbine was operated during the peak-loading hours (8–10 am and 5–8 pm). The operation of the microturbine was insignificant in the year 2019 because the renewable sources were cheaper than the microturbine. The growth of the load has been maximized for the year 2023; therefore, the usage of microgrid should be increased to satisfy the energy demand.Figure 10
Operation of microturbine during a day of the planning horizon.


### 5.5. Performance Comparison

The performance of the proposed algorithm in the electric vehicle charging expansion problem has been presented in this section. The performance of the SAAT-APHA was compared with different heuristic strategies and computational approaches. The proposed SAAT-APHA was compared with three different algorithms such as the SAAT, PHA, and CPLEX. The experiment was conducted for different percentages of optimality gap (POG), and the corresponding values were recorded. Two different experiments such as (1) a small cell size,N = 50 (size of the problem), and replication number R = 10 and (2) a large cell size, N = 200, and R = 15, 25, and 40 were considered. During the first case, the POG and the CPU time were recorded for N = 50. The size and the resources used in the EVCS expansion are listed in Table 5. The final sets of results obtained by solving the EVCS station expansion model using the algorithm are specified in Section 3 shown in Table 6. The performance of the algorithm was tested using various cases (1–28) (Table 6).Table 6
Comparison between the SAAT-APHA and other algorithms for case-1 (N = 50 and R = 10).
CaseCPLEXSAATPHASAAT-APHAPOG (%)Time (s)POG (%)Time (s)POG (%)Time (s)POG (%)Time (s)10.65100.350.82108.210.5984.260.3752.3620.71115.560.91122.360.6495.100.4263.3730.82122.430.97134.300.76112.470.4883.2440.96140.511.07151.150.83128.230.5696.2851.02153.071.12179.470.92136.170.61102.2961.16171.121.22190.290.99148.280.70110.2071.23184.401.34199.371.09159.160.74118.3881.38198.421.45210.211.18172.300.79125.3191.44209.081.53225.201.21189.280.87132.25101.53223.261.62242.171.36197.380.99143.20111.71251.391.83262.291.48209.261.05153.10121.82288.171.95283.101.57221.071.13161.50131.96315.242.08296.321.68238.191.20169.38142.12346.322.22319.271.73252.521.25175.25152.31389.382.40327.101.80265.251.31184.4016Mem—2.54342.181.89278.131.38192.1517Mem—2.62359.201.98285.221.45198.5818Mem—2.73372.282.06297.191.50203.1319Mem—Mem—2.18307.241.56215.2020Mem—Mem—2.29318.301.60224.1821Mem—Mem—2.40323.191.67232.2822Mem—Mem—2.51334.261.71245.3223Mem—Mem—2.62347.131.77255.1924Mem—Mem—2.70359.301.82263.1725Mem—Mem—Mem—1.86275.1226Mem—Mem—Mem—1.91283.2427Mem—Mem—Mem—1.96291.3828Mem—Mem—Mem—2.01298.24Average1.39213.911.69240.251.60227.451.24180.27It was observed that CPLEX run out of memory in solving the problem and instances are (after 15 instances) indicated in Table6. The results obtained from the SAAT indicated that it was not solved after 18 instances, hence not suitable for large problems. Moreover, by introducing the SAAT framework, performance could be increased slightly, i.e., out of 28 problem instances, it could not solve 10 instances and reached the predefined termination criteria. When the PHA was introduced, there was some improvement in the results. The average optimality gap of the PHA algorithm was 1.60%, and when the SAAT-APHA algorithm was used, it reduced to 1.24%. Then, it solved 24 out of 28 problem instances. Finally, when the SAAT-APHA was introduced, the computational efficiency was improved. From Table 6, it is evident that the computational performance of the SAAT-APHA is superior when compared to that of the other two state-of-the-art algorithms. The SAAT-APHA algorithm solved all of the 28 instances within the predefined termination criteria. It was further observed that the SAAT-APHA algorithm saved 23.14% and 17.06% computation time when compared to the PHA and CPLEX algorithms, respectively.The results of the second case used a large cell size (N = 200), and R = 15, 25, and 40 are given in Table 7. The largest test instances from Table 6 are taken to study the performance of the proposed method. It was observed that the CPLEX, SAAT, and PHA solved 4, 6, and 7 cases, respectively, out of 9 cases by following the termination condition. The proposed SAAT-APHA algorithm solved all of the 9 instances. The obtained results showed that the SAAT-APHA algorithm saved 26.63% and 26.04% computational time compared to the SAAT and PHA, respectively.Table 7
Comparison between the SAAT-APHA and other algorithms for case-1 (N = 200 and R = 15, 25, and 40).
CaseRCPLEXSAATPHASAAT-APHAPOG (%)Time (s)POG (%)Time (s)POG (%)Time (s)POG (%)Time (s)10152.14315.51.16298.70.97267.30.57147.5252.98346.71.32324.31.25295.60.89165.2403.75389.21.75365.61.54312.11.14184.811154.69397.12.59342.11.83345.91.24198.5256.02421.72.62389.81.92368.31.57217.9407.65486.93.18412.32.15396.21.79230.612159.14519.33.55447.52.36421.01.93251.22510.87544.74.28497.42.76447.42.14274.54012.35592.24.37523.92.96472.62.21289.2131513.24632.84.41547.73.17495.22.44298.12514.62668.44.63579.23.32515.92.69319.74013.69694.95.28598.43.57538.32.86331.61415Mem-5.47621.73.89554.82.98352.825Mem—6.22657.44.23589.23.15379.440Mem—6.52698.14.70606.53.31397.11515Mem—8.74715.94.96649.73.53425.525Mem—9.16746.75.25686.13.79451.340Mem—10.42779.45.48718.33.91474.81615Mem—Mem—5.89759.74.12497.525Mem—Mem—6.24789.34.35514.940Mem—Mem—6.85820.54.51530.31715Mem—Mem—Mem—4.70548.125Mem—Mem—Mem—4.92562.440Mem—Mem—Mem—5.11587.61815Mem—Mem—Mem—5.24610.225Mem—Mem—Mem—5.38624.840Mem—Mem—Mem—5.52642.6Average8.43500.784.76530.343.59526.193.18389.19


### 5.6. Comparison with Other Methods

This subsection describes the next five-year demand forecast for Zhuhai city, with 600 EVs having been considered for comparison. The city has 58 charging points for the EVs. The estimated average charging demand for the five continuous years (2023–2027) is shown in Figure11. Firstly, the plan for expansion is based on how many charging stations there are in the city in 2023. Renewable energy sources have been incorporated into the existing charging stations, and a few new stations have been installed in a few locations in 2023. In order to keep up with the rapid growth of electric vehicles, the building of charging stations is sufficient. Also, peak regulation and frequency, as well as the extra discharge and charge periods of the EV batteries participating in V2G, are taken into account when planning for expansion. This is done so that the location and capacity with the lowest cost and most benefit can be found.Figure 11
Comparison of unit charging demand cost of the proposed methods with other state-of-the-art methods.The performance of the proposed SAAT-APHA has been studied in terms of charging station operation per vehicle and the inconvenience of the customer. A comparison has been performed with three other methods, such as RDR-EV [5], EV-RES [34], and SAAT. Five different datasets have been generated by considering the demand variability, including 850, 1200, 1050, 980, and 1225 EV customers. It is generated from Day 1 to Day 5. The data are sampled based on the trip probability, and each dataset has an interarrival time, hourly trip details, and departure time. The k-means clustering technique was used to estimate the position of the EV charging station [64]. The comparison result is shown in Table 8. The utilization of a charging station which contains five chargers for day 1 is shown in Figure 12.Table 8
Performance of the proposed SAAT-APHA and three other methods.
Number of vehiclesTest daysAlgorithmEV charging operationCustomer inconvenienceAverage waiting time∗ X(Std. dev) YAverage charging time∗ M(Std. dev) NM + NX + YTotal waiting time of the fleet (hours)Mean journey time (m)Mean waiting time (m)Rate of served customers (%)850Day 1RDR-EV [5]5.115.465.29.474.620.59.643.712.776.4EV-RES [34]4.313.459.517.276.717.78.237.814.186.1SAAT2.611.955.322.878.114.56.141.311.491.4SAAT-APHA0051.714.366.00038.49.696.21200Day 2RDR-EV [5]7.717.175.418.593.924.816.535.619.768.7EV-RES [34]5.214.367.715.683.319.515.131.717.871.6SAAT4.113.858.315.373.617.916.342.418.382.9SAAT-APHA1.69.152.511.664.110.70.746.815.494.81050Day 3RDR-EV [5]6.416.569.114.483.522.99.530.414.771.6EV-RES [34]4.713.363.513.376.818.09.138.514.172.8SAAT3.113.156.911.668.516.28.741.612.984.3SAAT-APHA1.78.552.210.262.410.21.438.611.895.8980Day 4RDR-EV [5]5.915.172.611.584.121.06.245.412.976.2EV-RES [34]3.213.962.311.273.517.15.338.312.185.4SAAT2.913.455.610.566.116.34.136.111.789.8SAAT-APHA1.88.451.49..460.810.20.935.210.195.91225Day 5RDR-EV [5]7.214.268.219.287.421.46.639.915.869.1EV-RES [34]5.914.664.617.381.920.54.442.514.272.4SAAT4.113.757.312.669.917.81.542.113.782.5SAAT-APHA2.010.153.19.762.812.10.834.811.993.7Figure 12
Utilization of five different chargers of a charging station for day 1.850 EVs take part in the charging operation. The SAAT and SAAT-APHA provide lower average waiting time compared to the EV-RES [34] and RDR-EV [5]. Similarly, the average waiting time and charging time of the SAAT and SAAT-APHA are lower (column X + Y). It is observed from Table 8 that the proposed SAAT-APHA provided 0 waiting time on day 1. Similarly, the performance of the proposed SAAT-APHA is better on other charging days compared to that of the RDR-EV [5], EV-RES [34], and SAAT methods. For day 1 with 850 EVs, the proposed SAAT-APHA method has a lower mean passenger waiting time (9.6 m) than the SAAT (11.4 m), EV-RES (14.1 m), and RDR-EV (12.7 m) methods. The service rate is increased by 4.8%, 10.1%, and 19.8% compared to the SAAT, EV-RES [34], and RDR-EV [5] methods. From the simulation results, the authors conclude that implementing the SAAT-APHA reduces the charging time of the EVs and the waiting time.


### 5.7. Validation

In this study, the Xiangzhou District of Zhuhai City has been taken to validate the proposed expansion plan (Figure13). The increasing ratio of the EV possession is 28.9%, and it progressively begins to normalise saturation beginning in 2026. The data of the International Data Corporation have been taken from reference [65], which together serves to validate the suggested methodology. In Figure 13, the yellow triangle represents the position and ability of the existing charging point for the city. The following factors were used during the simulated evaluation.Figure 13
Location and capacity expansion plan up to 2030.The number of the EVs charged by each charging station per unit time (β) is 2 hrs, the rated capacity of the EV batteries (Bcap) is 25 kW, and the cost of queuing per hour (Cq) is RMB15/hr. Power consumption per 100 kilometres (PC) is 15 kW; unit price of the charger (Pu) is 10 RMB; annual operating cost of the charging station is 10% of the total cost; the peak-time electricity price in the city (Pp) is 1.25 RMB/kW; and unit cost of urban travel (µ) is 12 RMB/hour.This study simulates the deployment of 500 EVs in Zhuhai’s Xiangzhou District in 2021. Figure14 predicts the average daily charging demand during different years of the expansion plan. In Figure 14, the average charging requirement for the Xiangzhou District of Zhuhai City is shown on the y-axis, and the year is shown on the x-axis.Figure 14
Average daily charging demand from 2021 to 2030.It can be deduced from Figure13 that there are 58 chargers present in the city. The annual service intensity of the EV charging stations is σ > 1 in 2025, meaning that the quantity of chargers hardly fulfils the charging requirements of the EVs. In 2025, initial charging point locations must serve as the foundation for growth prospects. Additional charging points should indeed be constructed between 2027 and 2030, following the growth in 2025. Charging station expansion for different years is shown in Figure 14. Therefore, building charging points is sufficient to keep up with the advancement of the EVs. In order to achieve the location and ability with the cheapest expense and the greatest advantage, peak-regulation is also incorporated into the growth preparation. Additionally, the battery aging cost brought on by the extra cost and drain moments of the EV batteries engaging in V2G is taken into consideration, as well as the compensatory of the EVs engaging in peak-regulation. Table 9 displays the simulation outcomes for the new extended area. The total social expense in the year preceding the growth was RMB 976.37 thousand, and the extensive overall social expense in the year following the growth was RMB 4635.50 thousand. The EV charging station will be able to meet the increased demand for charging over the next decadeTable 9
Simulation results of the expansion plan for new locations.
YearCapacityConstruction and operation cost per year∗Average waiting time queue cost per year∗Aging cost of battery per year∗Cost of time consumption per year∗Peak regulation benefits∗Yearly social cost of new station∗20254 generators1853.5018.619.217.531795.7320273 generators1521.30.74513.466.733.761037.3220304 generators1900.70.31718.368.997.291802.45Total social cost of the new expansion4635.50∗indicates that the values are in thousands


## 5.1. Input Parameter Setting

A network was divided into cells (|N| = 50), and each cell covered an area of one mile. The specific parameters were the cells that were obtained only if there was a road passing through it or else when the value for these cells was considered as zero. Thus, only the active cells were considered as a potential location for installing a charging station. The five-year (|K| = 5) planning horizon was considered and started from 2018 and will end in 2022. For short-term operational decisions, a period of 24 hours (|T| = 24) was chosen (6 am to 5 am) as a representative from each year of the planning horizon. We assumed that all the cost components were estimated based on the 2019 Euro rate and were adjusted depending upon inflation. A fast EVCS station (γnsk1) at cell “n” costs around 50,100 Euro [60], and the charging station with a battery swap station (γnsk2) costs around 501,000 Euro [61]. The EV charging was adopted using V-G technology. It was capable of charging four EVs at the same time. The hourly profile of renewable energy, including load, is presented in Table 3. The data used in Table 3 are taken from a prior study [62, 63].Table 3
Hourly profile of renewable sources with load.
HourSolar power (%)Wind power (%)Load power (%)Electricity price (Euro/kWh)610501010715551510825603010940724510106582651011857095151210085100151310070951514908780151580757515165565702017354580201810588520190657020200100752021085702022090657230755072406040510552052045205307010540651055070105


## 5.2. Impact of Vehicle Charging Percentage Variabilityctka on System Performance

Three different scenarios were created to show the impact of vehicle charging percentage variation on the system performance. In the first scenario, the EVCS model was solved using the input parameters (base case). The charging percentage variation wasε=10% (low variation) and ε=50% (high variation) for the second and third scenarios, respectively. The Monte Carlo method was used to generate different vehicle charging (ctka) scenarios between c˜tka1−ε,c˜tka1+ε where c˜tka represents the mean vehicle charging percentage scenario for each hour t∈T in year k∈K.The impact of vehicle charging percentage variability on system performance is shown in Figure3. Results show that the amount of power used to meet the demand for electricity from different power sources such as solar, grid, and V2G was increased when the level of vehicle charging percentage variability ctka was increased. Hourly operational decisions of a charging station located in the cell n∈N of a given year k∈K depended on variables, such as solar power availability, the flow of vehicles, and electricity prices. When solar power was not available (i.e., from 6.00 pm to 7.00 am), demand for electric power was met through the grid and V-G. During peak hours and when solar power was available (i.e., from 7.00 am to 6.00 pm), demand was fulfilled mainly through renewable energy and then through the grid and V-G. Figure 4 shows the impact of vehicle charging percentage variability on the battery-related decision when type-II charging stations were installed in the tested region. To manage the high power demand, the batteries were charged during the off-peak hours in the charging station and discharged during the peak hours which are shown in Figures 4(a) and 4(b), respectively. Since more batteries were charged during the off-peak hours, more batteries were kept in the charging stations. The number of batteries demanded at the cell and the number of full batteries are shown in Figures 4(c) and 4(d), respectively.Figure 3
Impact of different resources utilization for vehicle charging (ckA): (a) average demand of cell satisfied through grid power, E¯ntka; (b) average demand of cell satisfied through renewable power, R¯ntka; (c) average demand of cell satisfied by V-G power, y¯ntka.
(a)(b)(c)Figure 4
Impact of real-time demand on vehicle charging percentage variability (ckA): (a) average number of batteries charging at the cell, L¯ntkA; (b) average number of batteries discharging at the cell, B¯ntkA; (c) average number of batteries demanded in the cell, D¯ntkA; (d) average number of batteries fully charged batteries in the cell, Q¯ntkA.
(a)(b)(c)(d)


## 5.3. Impact ofdntk, rntk, and htn on System Performance

The proposed EVCS model depends on three different parameters: renewable energy available at cellrntk, availability of grid power at cell dntk, and V-G power, which in turn depends on the percentage discharging htn. Any change in the availability of the power will deviate from the necessary quality of the operation, and hence it should be measured and carefully estimated. To verify the impact of these parameters, four sets of experiments were conducted by varying their availability by ±25% and ±40% from the base case scenario, and they are shown in Figures 5–7. The performance of the system based on grid power availability dntk is shown in Figure 5. Renewable power and availability of V-G power were kept at their base values. When the availability of grid power was increased, the average utilization of grid power Entka also increases as shown in Figure 5(a). However, when the availability of grid power was decreased by 40%, 42.75% of supplementary stations are installed to meet the demand of the EV charging as shown in Figure 5(b).Figure 5
Impact of grid power on the system performance:(a) availability of grid powerdntk and (b) variability of grid power.
(a)(b)Figure 6
Impact of renewable power on the system performance: (a) availability of renewable powerrntk and (b) variability of renewable power.
(a)(b)Figure 7
Impact of V-G power on the system performance: (a) availability discharged power of vehiclehtn (b) variability of discharged power of vehicle.
(a)(b)In the case of renewable energy, when the availability was decreased by 40%, 18.96% of additional charging stations were installed to meet the power demanded. When comparing the impact of the unavailability of renewable power on system performance with that of impact due to the unavailability of grid power, renewable power is less sensitive than grid power unavailability. When the source was available, the average utilization of renewable energyrntka increased in a charging station and it is shown in Figure 6(a). On the other hand, when rntk was decreased, the requirement of recharging stations was also increased. The percentage of rntk on the system performance is illustrated in Figure 6(b). The performance of the availability of V-G power depends on the system performance (Figure 7). When the availability of V-G power was increased, the average utilization of V-G power was also increased, as is shown in Figure 7(a).An additional 14.70% of charging stations were installed for a 50% decrease inhtn, and it is illustrated in Figure 7(b). Results showed that system had less impact on a V-G energy source when compared to the unavailability of the grid and renewable power. This is since the grid was followed by renewable energy and was the main source of energy for the charging stations and the unavailability of these sources affected the system severely when compared to V-G power. Finally, it was concluded that long-term charging station location decisions and short-term hourly operational decisions depend on the availability of grid, renewable, and V-G energy.


## 5.4. Results of Charging Station on an Expansion Plan

The EVCS was considered as a flexible load on the microgrid by optimizing the charging process. In some cases, the interval charging station can act as a generating unit because of the V-G technology. To study the impact of the charging station on the expansion, the model was simulated without V-G technology, i.e., power was not flowed in to the microgrid (Table4) and there was an enhancement in the total cost of expansion by 28%. It shows that large-capacity resources are needed by the microgrid to compensate for load growth.Table 4
Expansion plan without V-G technology.
ResourcesAnnual expansion cost (Euro/year)Wind power (kW)22,210.53Solar power (kW)1350.25Microturbine (kW)29,742.48Capacity of energy storage (kWh)8245.87Power of energy storage (kW)935.53Total cost of expansion (Euro/year)62,484.66The resources with various capacities that were needed to cope with the load growth for the five-year planning horizon are listed in Table5. The profile of wind energy was larger than solar energy; therefore, the growth of wind energy was more than that of solar energy. Consequently, the microgrid cropped more energy through the connected wind turbines. It was noticed that 54.7% of microturbines were installed in the fifth year of the planning horizon for managing the load growth. Lastly, the capacity and power of the ESS were expanded in different years to shift the power based on the peak hour load. Figure 8 shows the power exchanged between the upstream to the microgrid during a day for the five-year planning horizon. The capacity between the upstream to the microgrid was 230 kW. As a result, the maximum traded power was 230 kW. It was noted that load growth is managed by the available resources and new installed resources. Because of the limited trading power, the load demand should be managed by installing new resources (solar, wind, ESS, and microturbine). To manage the load efficiently, the model optimized the newly installed resources. The operation of the ESS in the planning horizon during the five years is shown in Figure 9. The load was shifted from the higher price to the lower price for saving costs and to avoid peak-loading problems.Table 5
Percentage of resources expansion for the five-year planning horizon.
ResourcesYear 2019 (%)Year 2020 (%)Year 2021 (%)Year 2022 (%)Year 2023 (%)Wind power1008522.4——Solar power1015—21.6—Power of microturbine————54.7Capacity of energy storage10020.518.417.5—Power of energy storage—10.342.737.3—Figure 8
Power exchanged between upstream network and microgrid during a day of the five years planning horizon.Figure 9
Operation of the ESS during a day of the planning horizon.To minimize the cost, the operation of the ESS and the microturbine was optimized during the short-term operation of the proposed expansion plan. The five-year operation of the microturbine expansion horizon is shown in Figure10. The microturbine was operated during the peak-loading hours (8–10 am and 5–8 pm). The operation of the microturbine was insignificant in the year 2019 because the renewable sources were cheaper than the microturbine. The growth of the load has been maximized for the year 2023; therefore, the usage of microgrid should be increased to satisfy the energy demand.Figure 10
Operation of microturbine during a day of the planning horizon.


## 5.5. Performance Comparison

The performance of the proposed algorithm in the electric vehicle charging expansion problem has been presented in this section. The performance of the SAAT-APHA was compared with different heuristic strategies and computational approaches. The proposed SAAT-APHA was compared with three different algorithms such as the SAAT, PHA, and CPLEX. The experiment was conducted for different percentages of optimality gap (POG), and the corresponding values were recorded. Two different experiments such as (1) a small cell size,N = 50 (size of the problem), and replication number R = 10 and (2) a large cell size, N = 200, and R = 15, 25, and 40 were considered. During the first case, the POG and the CPU time were recorded for N = 50. The size and the resources used in the EVCS expansion are listed in Table 5. The final sets of results obtained by solving the EVCS station expansion model using the algorithm are specified in Section 3 shown in Table 6. The performance of the algorithm was tested using various cases (1–28) (Table 6).Table 6
Comparison between the SAAT-APHA and other algorithms for case-1 (N = 50 and R = 10).
CaseCPLEXSAATPHASAAT-APHAPOG (%)Time (s)POG (%)Time (s)POG (%)Time (s)POG (%)Time (s)10.65100.350.82108.210.5984.260.3752.3620.71115.560.91122.360.6495.100.4263.3730.82122.430.97134.300.76112.470.4883.2440.96140.511.07151.150.83128.230.5696.2851.02153.071.12179.470.92136.170.61102.2961.16171.121.22190.290.99148.280.70110.2071.23184.401.34199.371.09159.160.74118.3881.38198.421.45210.211.18172.300.79125.3191.44209.081.53225.201.21189.280.87132.25101.53223.261.62242.171.36197.380.99143.20111.71251.391.83262.291.48209.261.05153.10121.82288.171.95283.101.57221.071.13161.50131.96315.242.08296.321.68238.191.20169.38142.12346.322.22319.271.73252.521.25175.25152.31389.382.40327.101.80265.251.31184.4016Mem—2.54342.181.89278.131.38192.1517Mem—2.62359.201.98285.221.45198.5818Mem—2.73372.282.06297.191.50203.1319Mem—Mem—2.18307.241.56215.2020Mem—Mem—2.29318.301.60224.1821Mem—Mem—2.40323.191.67232.2822Mem—Mem—2.51334.261.71245.3223Mem—Mem—2.62347.131.77255.1924Mem—Mem—2.70359.301.82263.1725Mem—Mem—Mem—1.86275.1226Mem—Mem—Mem—1.91283.2427Mem—Mem—Mem—1.96291.3828Mem—Mem—Mem—2.01298.24Average1.39213.911.69240.251.60227.451.24180.27It was observed that CPLEX run out of memory in solving the problem and instances are (after 15 instances) indicated in Table6. The results obtained from the SAAT indicated that it was not solved after 18 instances, hence not suitable for large problems. Moreover, by introducing the SAAT framework, performance could be increased slightly, i.e., out of 28 problem instances, it could not solve 10 instances and reached the predefined termination criteria. When the PHA was introduced, there was some improvement in the results. The average optimality gap of the PHA algorithm was 1.60%, and when the SAAT-APHA algorithm was used, it reduced to 1.24%. Then, it solved 24 out of 28 problem instances. Finally, when the SAAT-APHA was introduced, the computational efficiency was improved. From Table 6, it is evident that the computational performance of the SAAT-APHA is superior when compared to that of the other two state-of-the-art algorithms. The SAAT-APHA algorithm solved all of the 28 instances within the predefined termination criteria. It was further observed that the SAAT-APHA algorithm saved 23.14% and 17.06% computation time when compared to the PHA and CPLEX algorithms, respectively.The results of the second case used a large cell size (N = 200), and R = 15, 25, and 40 are given in Table 7. The largest test instances from Table 6 are taken to study the performance of the proposed method. It was observed that the CPLEX, SAAT, and PHA solved 4, 6, and 7 cases, respectively, out of 9 cases by following the termination condition. The proposed SAAT-APHA algorithm solved all of the 9 instances. The obtained results showed that the SAAT-APHA algorithm saved 26.63% and 26.04% computational time compared to the SAAT and PHA, respectively.Table 7
Comparison between the SAAT-APHA and other algorithms for case-1 (N = 200 and R = 15, 25, and 40).
CaseRCPLEXSAATPHASAAT-APHAPOG (%)Time (s)POG (%)Time (s)POG (%)Time (s)POG (%)Time (s)10152.14315.51.16298.70.97267.30.57147.5252.98346.71.32324.31.25295.60.89165.2403.75389.21.75365.61.54312.11.14184.811154.69397.12.59342.11.83345.91.24198.5256.02421.72.62389.81.92368.31.57217.9407.65486.93.18412.32.15396.21.79230.612159.14519.33.55447.52.36421.01.93251.22510.87544.74.28497.42.76447.42.14274.54012.35592.24.37523.92.96472.62.21289.2131513.24632.84.41547.73.17495.22.44298.12514.62668.44.63579.23.32515.92.69319.74013.69694.95.28598.43.57538.32.86331.61415Mem-5.47621.73.89554.82.98352.825Mem—6.22657.44.23589.23.15379.440Mem—6.52698.14.70606.53.31397.11515Mem—8.74715.94.96649.73.53425.525Mem—9.16746.75.25686.13.79451.340Mem—10.42779.45.48718.33.91474.81615Mem—Mem—5.89759.74.12497.525Mem—Mem—6.24789.34.35514.940Mem—Mem—6.85820.54.51530.31715Mem—Mem—Mem—4.70548.125Mem—Mem—Mem—4.92562.440Mem—Mem—Mem—5.11587.61815Mem—Mem—Mem—5.24610.225Mem—Mem—Mem—5.38624.840Mem—Mem—Mem—5.52642.6Average8.43500.784.76530.343.59526.193.18389.19


## 5.6. Comparison with Other Methods

This subsection describes the next five-year demand forecast for Zhuhai city, with 600 EVs having been considered for comparison. The city has 58 charging points for the EVs. The estimated average charging demand for the five continuous years (2023–2027) is shown in Figure11. Firstly, the plan for expansion is based on how many charging stations there are in the city in 2023. Renewable energy sources have been incorporated into the existing charging stations, and a few new stations have been installed in a few locations in 2023. In order to keep up with the rapid growth of electric vehicles, the building of charging stations is sufficient. Also, peak regulation and frequency, as well as the extra discharge and charge periods of the EV batteries participating in V2G, are taken into account when planning for expansion. This is done so that the location and capacity with the lowest cost and most benefit can be found.Figure 11
Comparison of unit charging demand cost of the proposed methods with other state-of-the-art methods.The performance of the proposed SAAT-APHA has been studied in terms of charging station operation per vehicle and the inconvenience of the customer. A comparison has been performed with three other methods, such as RDR-EV [5], EV-RES [34], and SAAT. Five different datasets have been generated by considering the demand variability, including 850, 1200, 1050, 980, and 1225 EV customers. It is generated from Day 1 to Day 5. The data are sampled based on the trip probability, and each dataset has an interarrival time, hourly trip details, and departure time. The k-means clustering technique was used to estimate the position of the EV charging station [64]. The comparison result is shown in Table 8. The utilization of a charging station which contains five chargers for day 1 is shown in Figure 12.Table 8
Performance of the proposed SAAT-APHA and three other methods.
Number of vehiclesTest daysAlgorithmEV charging operationCustomer inconvenienceAverage waiting time∗ X(Std. dev) YAverage charging time∗ M(Std. dev) NM + NX + YTotal waiting time of the fleet (hours)Mean journey time (m)Mean waiting time (m)Rate of served customers (%)850Day 1RDR-EV [5]5.115.465.29.474.620.59.643.712.776.4EV-RES [34]4.313.459.517.276.717.78.237.814.186.1SAAT2.611.955.322.878.114.56.141.311.491.4SAAT-APHA0051.714.366.00038.49.696.21200Day 2RDR-EV [5]7.717.175.418.593.924.816.535.619.768.7EV-RES [34]5.214.367.715.683.319.515.131.717.871.6SAAT4.113.858.315.373.617.916.342.418.382.9SAAT-APHA1.69.152.511.664.110.70.746.815.494.81050Day 3RDR-EV [5]6.416.569.114.483.522.99.530.414.771.6EV-RES [34]4.713.363.513.376.818.09.138.514.172.8SAAT3.113.156.911.668.516.28.741.612.984.3SAAT-APHA1.78.552.210.262.410.21.438.611.895.8980Day 4RDR-EV [5]5.915.172.611.584.121.06.245.412.976.2EV-RES [34]3.213.962.311.273.517.15.338.312.185.4SAAT2.913.455.610.566.116.34.136.111.789.8SAAT-APHA1.88.451.49..460.810.20.935.210.195.91225Day 5RDR-EV [5]7.214.268.219.287.421.46.639.915.869.1EV-RES [34]5.914.664.617.381.920.54.442.514.272.4SAAT4.113.757.312.669.917.81.542.113.782.5SAAT-APHA2.010.153.19.762.812.10.834.811.993.7Figure 12
Utilization of five different chargers of a charging station for day 1.850 EVs take part in the charging operation. The SAAT and SAAT-APHA provide lower average waiting time compared to the EV-RES [34] and RDR-EV [5]. Similarly, the average waiting time and charging time of the SAAT and SAAT-APHA are lower (column X + Y). It is observed from Table 8 that the proposed SAAT-APHA provided 0 waiting time on day 1. Similarly, the performance of the proposed SAAT-APHA is better on other charging days compared to that of the RDR-EV [5], EV-RES [34], and SAAT methods. For day 1 with 850 EVs, the proposed SAAT-APHA method has a lower mean passenger waiting time (9.6 m) than the SAAT (11.4 m), EV-RES (14.1 m), and RDR-EV (12.7 m) methods. The service rate is increased by 4.8%, 10.1%, and 19.8% compared to the SAAT, EV-RES [34], and RDR-EV [5] methods. From the simulation results, the authors conclude that implementing the SAAT-APHA reduces the charging time of the EVs and the waiting time.


## 5.7. Validation

In this study, the Xiangzhou District of Zhuhai City has been taken to validate the proposed expansion plan (Figure13). The increasing ratio of the EV possession is 28.9%, and it progressively begins to normalise saturation beginning in 2026. The data of the International Data Corporation have been taken from reference [65], which together serves to validate the suggested methodology. In Figure 13, the yellow triangle represents the position and ability of the existing charging point for the city. The following factors were used during the simulated evaluation.Figure 13
Location and capacity expansion plan up to 2030.The number of the EVs charged by each charging station per unit time (β) is 2 hrs, the rated capacity of the EV batteries (Bcap) is 25 kW, and the cost of queuing per hour (Cq) is RMB15/hr. Power consumption per 100 kilometres (PC) is 15 kW; unit price of the charger (Pu) is 10 RMB; annual operating cost of the charging station is 10% of the total cost; the peak-time electricity price in the city (Pp) is 1.25 RMB/kW; and unit cost of urban travel (µ) is 12 RMB/hour.This study simulates the deployment of 500 EVs in Zhuhai’s Xiangzhou District in 2021. Figure14 predicts the average daily charging demand during different years of the expansion plan. In Figure 14, the average charging requirement for the Xiangzhou District of Zhuhai City is shown on the y-axis, and the year is shown on the x-axis.Figure 14
Average daily charging demand from 2021 to 2030.It can be deduced from Figure13 that there are 58 chargers present in the city. The annual service intensity of the EV charging stations is σ > 1 in 2025, meaning that the quantity of chargers hardly fulfils the charging requirements of the EVs. In 2025, initial charging point locations must serve as the foundation for growth prospects. Additional charging points should indeed be constructed between 2027 and 2030, following the growth in 2025. Charging station expansion for different years is shown in Figure 14. Therefore, building charging points is sufficient to keep up with the advancement of the EVs. In order to achieve the location and ability with the cheapest expense and the greatest advantage, peak-regulation is also incorporated into the growth preparation. Additionally, the battery aging cost brought on by the extra cost and drain moments of the EV batteries engaging in V2G is taken into consideration, as well as the compensatory of the EVs engaging in peak-regulation. Table 9 displays the simulation outcomes for the new extended area. The total social expense in the year preceding the growth was RMB 976.37 thousand, and the extensive overall social expense in the year following the growth was RMB 4635.50 thousand. The EV charging station will be able to meet the increased demand for charging over the next decadeTable 9
Simulation results of the expansion plan for new locations.
YearCapacityConstruction and operation cost per year∗Average waiting time queue cost per year∗Aging cost of battery per year∗Cost of time consumption per year∗Peak regulation benefits∗Yearly social cost of new station∗20254 generators1853.5018.619.217.531795.7320273 generators1521.30.74513.466.733.761037.3220304 generators1900.70.31718.368.997.291802.45Total social cost of the new expansion4635.50∗indicates that the values are in thousands


## 6. Conclusion

In this paper, long-term planning decisions and short-term hourly operational decisions were integrated to design an EVCS expansion problem. The proposed EVCS model is computationally challenging based on the cell size, hours, years, and different strategies set by the decision-makers. To reduce the computational complexity, the SAAT algorithm was combined with the APHA. Several algorithmic improvements, such as different variants of heuristics and local and global heuristics, were incorporated. As a result, the SAAT-APHA produced high-quality solutions in a short period of time to solve large-scale problems in real time. The impact of the uncertainty of vehicle charging percentages on the design of charging stations was revealed by computational experiments. The impact of the availability of different power sources, such as renewable energy, grid, and V-G power, on the system performance was analyzed. When a reduction of 40% in the availability of PG, renewable energy, and vehicle discharging percentage of V-G power were noticed, an additional 52.94%, 23.53%, and 14.70% of charging stations, respectively, occurred. Finally, the impact of the utilization of solar power on system performance was analyzed. It was observed that the use of renewable power easily managed the expansion plan. Therefore, the EV charging station efficiently handles difficult situations. The results and the model discussed in this paper will help decision-makers develop a sustainable transportation system in the future.



---

*Source: 4813750-2022-09-10.xml*