Location of Electric Vehicle Charging Stations Based on Game Theory

Abstract

In order to solve the design problem of electric vehicle charging station distribution, based on the consideration of user and investor costs, this paper establishes a mixed integer model for charging station site selection based on game theory ideas. Among them, the user cost is determined by two indicators, namely, the cost of time for users to reach the charging station and the cost of time for users to wait in line, while the cost of the charging station is determined by the construction cost and the daily operation and maintenance cost. In the established model, the hierarchical analysis is used to minimize the combined cost of users and charging stations as the objective. In addition, an improved artificial bee colony algorithm is designed to solve the model. The improved algorithm adds a neighborhood search method and a feasible decoding scheme to the honey bee harvesting and tracking process, thus solving the problems of low search accuracy, poor convergence, and inability to directly calculate the mixed integer model of the original algorithm. Simulation results show that the improved artificial bee colony algorithm can effectively solve the mixed integer model and has higher search accuracy and convergence speed compared with the traditional method. By applying the algorithm to solve the siting model, the location and number of charging stations can be clearly planned, thus improving charging efficiency and reliability.

1. Introduction

Up to 2022, the total population of electric vehicles is 8.915 million, and the proportion of electric vehicles to their charging infrastructure in the electric vehicle industry is about 7:1. Currently, insufficient electric vehicle charging infrastructure and poor distribution are the primary factors limiting the industry growth of electric vehicles [1,2].

For this reason relevant scholars and experts have studied the siting of electric vehicle charging stations. In these studies, they applied multi-objective optimization theory to solve the problem of siting electric vehicle charging stations and considered the factors affecting the siting to build the model. Among them, the location of charging stations can be successfully determined by developing an overall cost minimization charging station location model that uses the average annual construction and operation cost of charging stations, the penalty cost of the distribution grid, and the charging cost of access to the grid as optimization metrics [3]. Considering factors such as land cost, charging station construction cost, electric conditions, and neighboring environments, a multi-objective site selection model is established, and the model is solved by an optimization algorithm to obtain the optimal charging station layout location [4]. It is worth mentioning that a multi-objective optimal siting model for minimizing the total social cost is proposed in the literature [5], which not only considers the construction and operation costs but also includes the effects of external costs (e.g., environmental pollution and traffic congestion) and user welfare. Then the model is solved by a genetic algorithm to obtain the optimal location. On the user side, a charging station hybrid integer planning model is designed with the objective of the maximization of number of charging station users, and the model is solved using a hybrid genetic algorithm [6]. An evaluation system that considers economic, society and environmental factors, as well as the characteristics of residential areas is used to select sites for electric vehicle charging stations and rank them using the fuzzy VIKOR method [7]. After analyzing the feedback relationship between user charging behavior and the charging station construction plan, and combining with the two-tier planning theory, a charging station position and capacities model considering grid cost expansion can be established [8]. In addition, also using the two-tier planning theory, a two-tier planning model for the location and capacity determination of electric vehicle charging stations can be constructed with socio-economic cost and carbon emission minimization as the decision objectives [9]. The model construction method adopted in the above literature is based on the point location theory. This theory can be separated into point localization theory and path de-command-based localization theory [10,11]. Among them, the point-based localization theory mainly includes the p-median problem [12,13], the p-center question [14,15], and the overlay question [16,17]. In addition, some location selection problems, such as site construction cost minimization [18,19], benefit maximization [20,21], user position-based location selection [22,23], and location selection with uncertainties [24,25], are also in the scope of point-based location theory.

Although the above siting model takes into account many factors, it lacks flexibility and comparability, and favors the use of traditional intelligent optimization algorithms in solving the model.

The commonly used intelligent optimization algorithms are: genetic algorithm, particle swarm optimization algorithm, artificial bee colony algorithm, game theory, etc. Among these, game theory algorithms can solve various types of mixed strategy problems. Genetic algorithm and particle swarm optimization algorithm have low scalability and lack diversity, compared with the artificial bee colony algorithm, which has higher diversity and can effectively solve multi-objective optimization problems.

In solving the site selection model, a method is proposed to solve the logistics center site selection model using an artificial bee colony algorithm. The method first establishes a mathematical model with rescue time satisfaction as the objective function, and then solves the model using the artificial bee colony algorithm to obtain an optimal site selection plan for the emergency logistics center [26]. For multi-objective optimization problems, the problem is transformed into a multi-objective optimization problem by building an appropriate mathematical model. In the solution process, the artificial bee colony algorithm is used to optimize multiple objective functions in parallel to obtain a set of optimal siting solutions [27]. To enhance the search accuracy and convergence speed of the artificial bee colony algorithm, adaptive dimensional update, global search, and chaotic search update strategies are introduced into the algorithm, and the algorithm is validated by constructing a multi-objective optimization model with minimum vehicle scheduling cost, time penalty cost, and risk cost [28]. By designing a variable neighborhood artificial bee colony algorithm, we introduce variable neighborhood search and design three neighborhood operators to ensure the diversity of algorithm solutions and enhance the local search capability [29]. In terms of improving species diversity, the principle of artificial bee colony optimization is combined with the idea of distributed computing in big data based on increasing the number of iterations of the algorithm to adjust the direction of finding nectar sources and the nearest distance to ensure the diversity of nectar sources after iteration [30]. In addition, the artificial bee colony algorithm can be combined with other population intelligence optimization algorithms, aiming to improve the search accuracy and convergence speed of the artificial bee colony algorithm [31,32]. In order to expand the application scope of the artificial bee colony algorithm, an update mechanism based on fitness and different decision variable selection was modified to enable it to calculate binary optimization problems [33]. In order to enable the artificial bee colony algorithm to calculate mixed integer models, the constructed model is encoded based on its characteristics [34,35].

In summary, this paper combines the improved artificial bee colony algorithm with the siting model in solving the charging station siting model. Firstly, the game theory method is used to construct a mixed integer model for site selection. Then, the hierarchical analysis method is used to consider the optimization factors in a hierarchical manner from a global perspective so as to improve the comparability and flexibility of the model. Finally, in order to enable the artificial bee colony algorithm to calculate the mixed integer model, the model is coded according to the characteristics of the constructed model in solving the model. In addition, the neighbor search method is added to the original bee picking and observation search phase. Differing from the above method, a feasible solution decoding method was designed based on the generation method of the algorithm population and the neighborhood search method, and added to the process of calculating the nectar amount of the honey source flowers.

2. Analytic Hierarchy Process

Analytic hierarchy process (AHP) is a combination of qualitative and quantitative methods [36]. The combination weight value is determined through this method in a certain scheme. The size of the combined weight value represents the relative importance of the scheme among all schemes. Their own conditions and surrounding environment are considered to determine the arrival rates of different charging stations. The differences in importance between different charging stations are distinguished using the analytic hierarchy process. The combined weight of the arrival rate at each charging station’s waiting point is determined. The detailed steps of analytic hierarchy process are as follows.

• The main factors affecting user arrival rate have been determined by consulting relevant information. The qualitative process is completed. On this basis, the quantitative process is completed to quantify the factors involved in the qualitative process by forming a decision-making team. The hierarchical analysis ladder structure of electric vehicle charging stations has been constructed. The target layer of this ladder structure is for electric vehicle users to charge the most at the charging station. The four standards of charging convenience, self-location, service capability, and surrounding environment are established in the guideline layer. The waiting points for electric vehicle charging stations and the locations of existing charging stations are considered as the most solution layer.
• The importance of each standard in the criterion layer is measured based on the target layer. Then, based on the criterion layer, measure the importance of each point in the solution layer. The judgment matrix is established by using a 1–9 level scaling method [37].
• The constructed $n$th order judgment matrix is processed through normalization. The maximum eigenvalue of the judgment matrix is ${\lambda }_{max}$. The maximum eigenvector corresponding to ${\lambda }_{max}$ is determined. The consistency index of the judgment matrix is calculated as Equations (1) and (2).

  $$CI=\frac{{\lambda }_{max}-n}{n-1}$$

  (1)

  $$CR=\frac{CI}{RI}$$

  (2)

  where RI represents the average random consistency index corresponding to $n$. If $CR<0.1$, the maximum eigenvector of the constructed $n$th order matrix is recorded. If $CR\ge 0.1$, the parameters in the judgment matrix should be modified. The order of the judgment matrix exceeds 11 in this article. Therefore, the high-order random consistency index values were determined using the method of Hong et al. [38].
• Using the eigenvectors of Target Layer–Criteria Layer and Criteria Layer–Scheme Layer, the combined weight value $q_i$ of each electric vehicle charging station and the constructed charging station is calculated in the scheme layer. If the combination weight value of the charging station is large, the arrival rate is high.

3. Charging Station Location Model Based on Game Theory

Based on the waiting time of electric vehicles, a time cost function for queuing is constructed. A charging station location model was established based on the optimization indicators of user time consumption cost, queue waiting time cost, charging station construction cost, and daily operation and maintenance cost.

3.1. Electric Vehicle Queue Waiting Time

The waiting time model for electric vehicles is one of the important models in queuing theory, which mainly describes the impact of electric vehicle user arrival rate, number of charging stations, and service capacity on waiting time. The time when electric vehicles arrive at the charging station is random, and whether they need to wait in line after arriving at the charging station is also random. In order to effectively describe the impact of charging station construction location on queuing behavior, the average waiting time of all users in the charging substation is taken. The average waiting time for each user in the charging station is shown in Equation (3).

$${\overline{t}}_j=\frac{{\left(N_j{\rho }_j\right)}^{N_j}{\rho }_j}{N_j!{(1-{\rho }_j)}^2{\lambda }_j}{P}_0$$

(3)

$$P_0={[{\sum }_{k=0}^{N_j-1}\frac{1}{k!}\left(\frac{{\lambda }_j}{\mu }\right)+\frac{1}{N_j!\left(1-{\rho }_j\right)}{\left(\frac{{\lambda }_j}{\mu }\right)}^{N_j}]}^{-1}$$

(4)

$${\rho }_j=\frac{{\lambda }_j}{\mu N_j}$$

(5)

Among these, ${\overline{t}}_j$ represents average waiting time of EV users at the waiting point $j$. ${\lambda }_j$ represents the arrival rate at waiting point $j$ of electric vehicle charging station. ${\lambda }_j=\frac{{\lambda }_{original}}{q_{original}}{q}_j$. ${\lambda }_{original}$ represents the arrival rate at original charging stations. $q_{original}$ indicates the combined weight corresponding to the arrival rate of the original charging station. $q_j$ represents the combined weight corresponding to the arrival rate of point $j$. $\mu$ represents the service rate of the charging station. ${\rho }_j$ represents the service intensity of the charging station within the waiting point $j$, ${\rho }_j<1$. $N_j$ represents the number of charging stations at waiting point $j$. $P_0$ represents the idle probability of the charging station.

If the arrival rate and service rate of electric vehicle charging stations remain unchanged, the more charging stations there are, the shorter the average waiting time. If the number of charging stations reaches a certain level, electric vehicle users can directly charge after entering the charging station without waiting in line. The relationship between user waiting time and the number of charging stations is shown in Figure 1.

3.2. Assumptions

To facilitate the quantified study, the assumptions below were made in the model process.

• The principle of proximity is that users prefer to go to charging stations closer to their own location.
• The demand point is an area with a constant area.
• The same performance and constant driving speed for all EVs.
• The service rate of all charging stations in the station is equal.
• Each waiting point is a queuing system with a constant daily arrival rate.
• Within the research area, the everyday requirements at the demand points are the similar and the demand relates only with the population.
• The arrival rate of electric vehicle users follows the Poisson distribution, and is only related to the conditions of the charging station itself and its surrounding environment.

3.3. Objective Function Construction and Constraint Conditions

The symbols are explained as follows.

$i$ represents the number of the demand point, $i\in n_i$.

$n_i$ represents the set of demand points.

$j$ represents the number of the waiting point, $j\in n_j$.

$n_j$ represents the set of waiting points.

$I$ represents the number of demand points.

$J$ represents the number of waiting points.

$P$ represents the number of charging stations.

$C_{ij}$ represents the unit time cost.

$p_i$ represents the demand per unit area at demand point $i$.

$S$ represents the floor area of the demand point.

$\partial$ represents the traffic impedance coefficient.

$d_{ij}$ represents the distance traveled.

$v$ represents the driving speed of an electric vehicle.

$C_{jm}$ represents the cost of unit queuing waiting time.

$O$ represents the fixed investment cost of the charging station.

$\beta$ represents the purchase cost of each charging station.

$n$ represents the depreciation period of the charging station.

$r_0$ represents the discount rate.

$N_j$ represents the number of charging stations.

$\alpha$ represents the conversion coefficient between the cost of building an electric vehicle charging station and the cost of daily operation and maintenance.

$x_{ij}$ is the 0-1 decision variable between the demand point and the point to be taken.

$x_j$ is the 0-1 decision variable for the point to be taken.

3.3.1. Objective Function One: Minimize User Costs

The user cost includes the time cost of the user to the waiting point and the time cost of queuing and waiting at the waiting point. The time consumed by electric vehicle users to the charging station determines the choice of waiting points. If the time and cost are high, and the user’s satisfaction with the waiting point of the charging station is low, the charging station should not be built at the waiting point. If the time and cost for users to reach the waiting point are low, their satisfaction with the waiting point of the charging station is high, and a charging station should be built at the waiting point. The time cost function for electric vehicle users to reach the charging station waiting point with distance as the independent variable is as follows.

$$C_1={\sum }_{j=1}^J{\sum }_{i=1}^I{C}_{ij}{p}_{i}S(d_{ij}\partial /v)x_{ij}{x}_j$$

(6)

Based on the queuing system, the time cost function for users to queue and wait in the charging station is established as follows.

$$C_2={\sum }_{j=1}^J{C}_{jm}{\overline{t}}_j{x}_j$$

(7)

The user cost minimization function is constructed as follows.

$${minF}_1=C_1+C_2$$

(8)

3.3.2. Objective Function Two: Minimizing the Cost of Charging Stations

The investment cost for charging stations by investors is mainly divided into two parts, one is the cost of building charging stations. The other part is the daily operating expenses of the charging station. Therefore, the cost of charging stations should include the construction cost $C_3$ and daily operation and maintenance cost $C_4$. Considering the land area to be purchased for the build of charging station, the cost of building materials required for the build of charging station, the cost of building roads, and the number of charging piles purchased within the charging station, the cost function for the construction of electric vehicle charging stations is constructed as follows.

$$C_3=\frac{1}{365}{\sum }_{j=1}^J(O+\beta N_j+\mu N_j^2)\frac{r_0{(1+r_0)}^n}{{(1+r_0)}^n-1}{x}_j$$

(9)

The daily operation and maintenance cost function of electric vehicle charging stations is constructed as follows, considering the payment of salaries for charging station employees and expenses for repairing substation equipment and charging piles.

$$C_4=\frac{1}{365}{\sum }_{j=1}^J\alpha (O+\beta N_j+\mu N_j^2)x_j$$

(10)

Based on the construction cost and daily operating cost, the charging station cost minimization function is constructed as follows.

$${minF}_2=C_3+C_4$$

(11)

If there are a large number of charging stations configured, the construction cost and daily operation cost of the charging station will be high. If the number of charging stations is small, the total cost of charging stations will be small. However, the cost of users queuing and waiting increases. The relationship between the cost of charging stations and the configuration scale of charging stations is shown in Figure 2.

The constraints are as follows.

Each electric vehicle demand point can only correspond to one electric vehicle charging station waiting point, as shown in Equation (12).

$${\sum }_{j=1}^J{x}_{ij}=1\hspace{1em}\forall i\in n_i,\forall j\in n_j$$

(12)

Build a station at waiting point $j$ to meet all electric vehicle charging needs, as shown in Equation (13).

$$x_{ij}\le x_j\hspace{1em}\forall i\in n_i,\forall j\in n_j$$

(13)

The EV charging station constructed accommodates the charging demand of all demand points, as shown in Equation (14).

$${\sum }_{j=1}^J{x}_{ij}{x}_j\ge 1\hspace{1em}\forall i\in n_i$$

(14)

$P$ electric vehicle charging stations are selected from the waiting points of $J$ electric vehicle charging stations, as shown in Equation (15).

$${\sum }_{j=1}^J{x}_j=P\hspace{1em}\forall j\in n_j$$

(15)

The arrival rate of waiting points for electric vehicle charging stations is limited, as shown in Equation (16). Due to the limit on the number of vehicles that charging stations can serve per day, the arrival rate of waiting points must not exceed the maximum number of services provided by electric vehicle charging stations.

$${\lambda }_j\le {\lambda }_{max}$$

(16)

The number of charging stations within the waiting point $j$ of the electric vehicle charging station is limited, as shown in Equation (17).

$${N_{min}\le N}_j\le N_{max}$$

(17)

The 0–1 decision variables are as follows.

$$x_{ij}\in \{0,1\}\hspace{1em}\forall i\in n_i,\forall j\in n_j$$

(18)

$$x_j\in \{0,1\}\hspace{1em}\forall j\in n_j$$

(19)

3.4. Mathematical Model Description

Equation (20) represents the minimum user cost. The time cost for electric vehicle users to reach the waiting point at the charging station and the time cost for users to queue and wait inside the charging station are minimized. Equation (21) indicates that the charging station has the lowest cost. The construction cost and daily operation and maintenance cost of electric vehicle charging stations are the smallest. The charging station location model based on game theory is as follows.

$${minF}_1=C_1+C_2$$

(20)

$${minF}_2=C_3+C_4$$

(21)

$${\sum }_{j=1}^J{x}_{ij}=1\hspace{1em}\forall i\in n_i,\forall j\in n_j$$

(22)

$$x_{ij}\le x_j\hspace{1em}\forall i\in n_i,\forall j\in n_j$$

(23)

$${\sum }_{j=1}^J{x}_{ij}{x}_j\ge 1\hspace{1em}\forall i\in n_i$$

(24)

$${\sum }_{j=1}^J{x}_j=P\hspace{1em}\forall j\in n_j$$

(25)

$${\lambda }_j\le {\lambda }_{max}$$

(26)

$${N_{min}\le N}_j\le N_{max}$$

(27)

$$x_{ij}\in \left\{0,1\right\}\hspace{1em}\forall i\in n_i,\forall j\in n_j$$

(28)

$$x_j\in \{0,1\}\hspace{1em}\forall j\in n_j$$

(29)

The charging station location model based on game theory belongs to the mixed integer model, which is transformed as follows by using the linear weighting method.

$$F={\omega }_1{F}_1^{\prime }+{\omega }_2{F}_2^{\prime }$$

(30)

${\omega }_1$ and ${\omega }_2$ are weights of coefficients for each objective, and meet ${{\omega }_1,\omega }_2\in (0,0.5]$. $max{F}_1$ and $min{F}_1$ are the maximum and minimum values that $F_1$ can achieve. $max{F}_2$ and $min{F}_2$ are the maximum and minimum values that $F_2$ can achieve. $F_1^{\prime }$ and $F_2^{\prime }$ are user cost weights and charging station cost weights, and their calculation method is as follows.

$$F_1^{\prime }=\frac{F_1-min{F}_1}{max{F}_1-min{F}_1}$$

(31)

$$F_2^{\prime }=\frac{F_2-min{F}_2}{max{F}_2-min{F}_2}$$

(32)

According to Equations (7), (9), and (10), the configuration scale of charging stations in charging stations varies, resulting in different waiting time costs, station construction costs, and daily operation and maintenance costs. Considering the positions of users and investors, and utilizing the relationship between time cost weight and charging station cost weight, determine the number of charging stations that need to be constructed for the charging station. The equation for calculating the weight of the time cost of queuing and waiting is as follows. According to Equations (7), (9), and (10), the configuration scale of charging stations varies, resulting in different waiting time costs, station construction costs, and daily operation and maintenance costs. According to the relationship between time cost weight and charging station cost weight, determine an amount of charging stations to be built. The equation for calculating the weight of the time cost of queuing and waiting is as follows.

$$C_2^{\prime }=\frac{C_2-min{C}_2}{max{C}_2-min{C}_2}$$

(33)

The cost weight indicator is constructed to determine the number of charging stations. The calculation method for cost weight indicators is the sum of the weight of the waiting time cost and the weight of the charging station cost. If the arrival rate of electric vehicle charging stations is constant, the number of charging stations constructed continues to increase, and the cost weight value gradually decreases. When the weight value of the charging station cost decreases to a certain peak, it gradually begins to increase. The peak value of cost weight corresponds to the number of charging stations constructed. The relationship between cost weight and the number of charging stations in the charging station is shown in Figure 3.

4. Model Solving and Artificial Bee Colony Algorithm Design

The artificial bee colony algorithm mainly consists of four basic processes, including honey source, bee picking, observing bees, and detecting bees. Collecting bees and observing bees describe the process of bees extracting honey sources, which is used to find the optimal solution. The investigation bee began to investigate the honey source after completing the mining of all the honey sources. Reconnaissance bees provide multiple search directions for bees to extract honey sources. The process of honey source extraction by bees is described by collecting and observing bees, whose role is to find the optimal solution. The investigation bee began to investigate the honey source after completing the mining of all the honey sources. Reconnaissance bees provide multiple search directions for extracting honey sources.

The artificial bee colony algorithm has the characteristics of fewer control parameters, easy implementation, and simple calculation. Compared with intelligent algorithms such as genetic algorithm and particle swarm optimization, artificial bee colony algorithm has more advantages in combinatorial optimization [39,40]. However, the artificial bee colony algorithm has low convergence speed and search accuracy problems when calculating large examples. A neighborhood search method was designed to address these problems by referencing the crossover mutation method of genetic algorithms. It is also added to the honey gathering and following process of the artificial bee colony algorithm to improve the convergence speed and search precision of the algorithm.

The population generation method and feasible solution search mechanism of the artificial bee colony algorithm make it unable to directly calculate mixed integer models. According to the population generation method and neighborhood search method of the artificial bee colony algorithm, a feasible solution decoding scheme is designed to calculate a mixed integer model. This scheme is added to the process of calculating the amount of nectar in the honey source flowers.

The honey source refers to the target function of the game theory based charging station location model. The honey source position represents the feasible solution of the objective function. The amount of nectar in the nectar source represents the applicability of feasible solutions. The specific process of the improved artificial bee colony algorithm is as follows.

Step 1 (initialize population): the initial population size is set to $N_s$. The number of bees collected is $N_e$. The number of observed bees is $N_u$, and $N_e=N_u$. The vector dimension of a single feasible solution is $D$. The maximum number of iterations is $MaxCycle$. The maximum number of searches for honey source is $Limit$. $X_i$ represents a location selection scheme for electric vehicle charging stations in traditional artificial bee colony algorithms. The initialization population ${(X}_1,X_2,\cdots ,X_{N_s})$ is composed of randomly generated $N_s$ feasible solutions $X_i$. $j$ is the component in feasible solution $X_i$. $X_{max}^j$ is the upper bound of the search space. $X_{min}^j$ is the lower bound of the search space. The generation method of a single feasible solution $X_i^j$ is as follows.

$$X_i^j=X_{min}^j+rand\left(\mathrm{0,1}\right)(X_{max}^j-X_{min}^j)$$

(34)

Step 2 (calculate the nectar amount of the honey source flowers): there is a random variable $rand(0,1)$ in Equation (34), making component $j$ a real number in $X_i$. This makes traditional artificial bee colony algorithms unable to directly generate integer feasible solutions. In order to evaluate whether the generated charging station location plan meets the requirements, it is necessary to decode the plan first. The decoding process is shown in Figure 4.

The number of components in feasible solution A is the same as the number of waiting points for electric vehicle charging stations. A set of real feasible solutions is composed of multiple real feasible solutions. Decode the real feasible solutions in the set of real feasible solutions one by one and convert them into integer type feasible solutions. The number of components in the converted integer feasible solution is the same as the number of electric vehicle charging stations that need to be constructed. The decoding equation for the feasible solution of real numbers is as follows.

$$\begin{gathered} \left[~,int\right]=sort\left(X_i\right) \\ decod{e}_{X_i}=int(1:P) \end{gathered}$$

(35)

The amount of nectar at the honey source location is calculated using Equation (30). If the value of $F$ is small, the greater the amount of nectar at that nectar source location. When the amount of nectar in the honey source reaches its maximum, the position of the honey source is the optimal solution of the objective function.

Step 3 (collecting bees): assuming that the honey source location of the bees in step n is $X\left(n\right)$, neighborhood search is performed near the $X\left(n\right)$ vector. $New\_X_i$ is the new location of the honey source where the bees are located after neighborhood search. The traditional artificial bee colony algorithm performs neighborhood search as follows.

$${New\_X}_i^j=X_i^j+rand(X_i^j-X_k^j)$$

(36)

On the basis of traditional artificial bee colony algorithm neighborhood search and referring to the cross mutation method of genetic algorithm, a neighborhood search method is designed as Equation (37). $v_{ij}$ is the feasible solution after neighborhood search. $cr$ is the judgment parameter. If $rand<cr$, neighborhood search is used.

$$v_{ij}=\left\{\begin{array}{cc}{X}_{Global}^j+\beta \left(X_{Global}^j-X_i^j\right)& ,rand<cr\\ {New\_X}_i^j& ,rand\ge cr\end{array}\right.$$

(37)

Step 4 (observation of bees): Collecting bees is selected by the observed bees with a certain probability. After the observation bee reaches the location of the honey source, it changes to collecting bees. According to Equations (36) and (37), neighborhood search is adopted. The probability calculation equation for observing bees following bees is as follows.

$$P_i=\frac{F_i}{\sum F_n}$$

(38)

where $F_i$ represents the amount of nectar from the nectar source at location $i$ of the bee, and $F_n$ represents the amount of nectar in the nectar source at the location $n$ of the bee.

Step 5 (reconnaissance bee): if the number of neighborhood searches is greater than the maximum number of searches, and no honey source location with a larger amount of nectar is found, it becomes a reconnaissance bee and obtains a new honey source location according to Equation (34).

5. Simulation

This simulation is based on the example of the Lixia District of Jinan City. By analyzing the different building types in the city, the areas that meet the characteristics are used as demand points. A total of 378 demand points were selected. Among them, 75 are work areas and commercial areas, 77 are residential areas, 54 are tourist areas, and 97 are parking lots. The district is divided into several cells of equal area, and the distance between the points to be picked up is considered. The location of the electric vehicle charging stations to be picked up is determined based on the distribution characteristics of the roads in the cells, the demand points, and the layout of the built electric vehicle charging stations. The number of electric vehicle charging stations to be taken is 155, as shown in Figure 5.

For the kernel density analysis of the Lixia district, the population density distribution is shown in the Figure 6.

The number range of waiting points for electric vehicle charging stations is 1 to 102. The numbering range of the original electric vehicle charging station is 103 to 148. Analyze and compare the importance of various indicators that affect the arrival rate of electric vehicle charging stations, and construct a judgment matrix from the criterion layer to the target layer as shown in

Table 1. Judgment matrix.

Influencing Factor	Convenience of Charging	Self-Position	Service Capability	Surrounding Environment	Weight
Convenience of charging	1	2	3	3	0.46
Self-position	1/2	1	1/2	1/2	0.13
Service capability	1/3	2	1	1/2	0.17
Surrounding environment	1/3	2	2	1	0.24

.

The random consistency parameter of the 148th order matrix was calculated to be 1.738 using the calculation method of the high-order random consistency index. The judgment matrix from the scheme layer to the criterion layer is constructed. The final combination weight is calculated as shown in Figure 7.

The variable parameters are set during the simulation process. The unit time cost for electric vehicle users is 12.9 yuan per hour. The demand point covers an area of 50. The driving speed of electric vehicles is 60 km/h. The traffic impedance coefficient is 1.6. The service rate is 2.7 vehicles per hour. The maximum number of charging stations is 56. The minimum number of charging stations is four. The unit waiting time cost for queuing is 10 yuan. The fixed investment cost for the charging station is 1 million yuan. The purchase cost of the charging station is 100,000 yuan per unit. The depreciation period of the charging station is 20 years. The discount rate is 0.08. The conversion coefficient between the construction cost of electric vehicle charging stations and the daily operation and maintenance cost is 0.1. Set the parameters of the artificial bee colony algorithm. The population size is 400. The number of bees collected is 200. The observed number of bees is 200. The maximum number of searches for honey source mining. The judgment coefficient is 0.6. The number of iterations is 400.

Different site selection options were analyzed for sensitivity to determine the number of charging stations to be built, as shown in Figure 8. As the number of construction continues to increase, the cost weight of charging stations continues to increase. The number ranges from 38 to 42, and for each additional charging station built, the weight increase is small. After the number increased from 42 to 43, the cost weight of charging stations increased significantly. In order to balance the relationship between charging station investors and electric vehicle users, it is determined that the number of charging stations in the charging station location scheme based on game theory is 42.

The drawing of charging station location scheme based on game theory is shown in Figure 9. The circle represents the demand point. The rhombus is the waiting point. The overlapping numbers indicate the numbers of the charging stations to be picked up. The lines indicate the connection line between the point to be picked up at the charging station and the demand point. The red box indicates the charging station construction point to be picked up, as well as the construction point with the least comprehensive consideration of cost.

The construction quantity of charging stations is shown in Figure 10, in which the lateral coordinate represents the charging station number and the longitudinal coordinate represents the number of charging posts. Figure 10 shows the number of charging stations built, within each construction point. Figure 9 and Figure 10 correspond to each other.

The search accuracy and convergence speed of the improved artificial bee colony algorithm for solving the proposed model were tested. The two artificial bee colony algorithms that did not include domain search and domain search were both independently run 20 times. The convergence speed, search accuracy, computational accuracy, and stability of artificial bee colony algorithms without incorporating domain search methods are the same as those of traditional artificial bee colony algorithms. The artificial bee colony algorithm that does not incorporate domain search methods is named artificial bee colony algorithm 1. The artificial bee colony algorithm that incorporates domain search methods is named artificial bee colony algorithm 2. The optimal solution, average solution, and standard deviation of the artificial bee colony algorithm are shown in

Table 2. Comparison of search accuracy and stability of artificial bee colony algorithm.

	Optimal Solution	Optimal Solution	Standard Deviation
Artificial Bee Colony Algorithm 1	0.0340	0.0343	$5.231\times {10}^{-4}$
Artificial Bee Colony Algorithm 2	0.0244	0.0246	$3.078\times {10}^{-4}$

. The improved artificial bee colony algorithm has improved its computational accuracy by 28.2%, search accuracy by 33.3%, and stability by 41.1%. The convergence curve of the artificial bee colony algorithm is shown in Figure 11. The two algorithms did not change the amount of nectar after the 380th and 351st generations, respectively. The two algorithms obtained the optimal solution in the 380th and 350th generations, respectively. After improvement, the convergence speed has been increased by 30 generations.

6. Conclusions

The optimization problem of charging station locations based on game theory is studied in this paper. The minimum user cost function is established based on the optimization indicators of time-consuming cost and queuing time cost. The minimum cost function for charging stations is established based on the optimization indicators of station construction cost and daily operating cost. The mixed integer model of charging station location based on game theory is established. The goal is to minimize the comprehensive cost of users and charging stations based on the analytic hierarchy process in the model. An improved artificial bee colony algorithm is designed to calculate the model. The problems of low search accuracy, poor convergence, and inability to directly calculate mixed integer models in artificial bee colony algorithms are solved through two aspects. One is the addition of a neighborhood search method in the honey gathering and following process of bees. On the other hand, a feasible decoding scheme was designed. The simulation results of charging station location based on game theory show that the proposed model can effectively determine the location of charging stations and the number of charging piles in charging stations. The improved artificial bee colony algorithm can directly calculate mixed integer models, and its stability, search accuracy, and convergence speed have been improved.