# Multiobjective Optimization of Large-Scale EVs Charging Path Planning and Charging Pricing Strategy for Charging Station

Authors: Weicheng Hou; Qingsong Luo; Xiangdong Wu; Yimin Zhou; Gangquan Si
Journal: Complexity
 (2021)

---

## Abstract

With the increasing number of electric vehicles (EVs), the charging demand of EVs has brought many new research hotspots, i.e., charging path planning and charging pricing strategy of the charging stations. In this paper, an integrated framework is proposed for multiobjective EV path planning with varied charging pricing strategies, considering the driving distance, total time consumption, energy consumption, charging fee such factors, while the charging pricing strategy is designed based on the objectives of maximizing the total revenues of the charging stations and balancing the profits of the charging stations. First, the energy consumption model of EVs, the M/M/S queuing model of charging stations, and the charging model of charging piles are established. A novel charging path planning algorithm is proposed based on bidirectional Martins’ algorithm, which can assist EV users to select charging stations and plan charging paths. Then, a particle swarm optimization (PSO) algorithm is applied to solve the optimal solution of charging station pricing designation. Finally, the method proposed in the paper is simulated on the street map of Shenzhen to verify the efficacy of the multiobjective charging path planning for EVs and the feasibility of the charging pricing strategy.


---

## Body

## 1. Introduction

EVs can reduce the emissions of harmful substances generated by the use of traditional fossil energy sources, so it is one of the promising alternatives to deal with the future energy crisis and environmental pollution [1]. However, the EVs have the problem of longer battery charging time and shorter driving range than petrol vehicles, which could result in “charging anxiety” and “range anxiety” for the EV users [2, 3]. Therefore, how to use EVs wisely is a concern of EV users and researchers. Considering factors such as driving distance, driving duration, energy consumption, and charging fee, EV users would select a reasonable charging path to alleviate their “range anxiety” [4].EV charging path planning is a multiobjective problem. To ensure the shortest driving duration to the charging station and the least charging cost under the premise that the battery is not depleted, the charging decision of EV users can be modeled as an energy-aware shortest path problem (ESPP) on a traffic network diagram with a virtual arc [5]. Considering the total driving time and the total energy consumption of the EV, the problem is modeled as a bilevel formulation of the discrete multiclass equilibrium network design, where the upper level is solved using a GA and the lower level is a multiclass user equilibrium (UE) traffic assignment model [6]. The elevation factor is considered to calculate the energy consumption [7]. The charging time of each candidate charging station and the total travelling time to the destination are considered in the charging path planning [8]. Deep reinforcement learning (DRL) can be applied in the charging scheduling for EVs with the optimization objective to minimize the total cost of EV users, including charging time and charging fares, under the condition of charging availability and fluctuated electricity prices [9].The multiobjective decision-making problem has been studied extensively [10]. A practical ISE-IITOPSIS method is proposed to solve the multifeature identification problem [11]. The most direct and simple method of solving the multiobjective path is the weighted method, which aggregates multiple objectives into a single objective problem through assigning weight to each objective [12]. However, this method requires normalization of the parameters and fine-tuning weights. Classic algorithms, i.e., graph-based theory, can also be applied. For example, Yen’s algorithm is used to ensure that travelling time and delay time caused by traffic congestion are minimized [13]. Besides, the heuristic algorithms (i.e., the multiobjective intelligent evolutionary algorithm) are applied to solve the Pareto solution set of the shortest path under constraints. For example, a hybrid variable domain-search algorithm is proposed to solve the extended EV routing problem, via the EV battery swap station location routing with stochastic demands [14]. The classic algorithm can obtain an accurate Pareto solution. However, with the consideration of a city-level traffic network based on the huge amount of nodes and edges, heuristic algorithms are feasible to solve the optimal solution [15]. Martins’ algorithm [16] is a classic multiobjective shortest path algorithm based on the Dijkstra algorithm, but it has to search the entire network to get the optimal Pareto solution set. Therefore, an improved method based on Martins’ algorithm is proposed [17], including setting interruption conditions and bidirectional search (i.e., search from the end point and start point simultaneously). Simulation experiments demonstrate that the computational efficiency can be significantly improved in a large-scale transportation network.The pricing mechanism of EV charging stations should also be investigated. The commonly studied pricing strategies mainly include fixed electricity price [18], time-of-use (TOU) price [19], and real-time price (RTP) [20]. RTP is a method of dynamically adjusting electricity price via the relationship between the power system supply and demand [21]. In the power system, a fundamental model is proposed for continuous-time scheduling and marginal pricing of energy generation storage in day-ahead power systems’ operation [22]. In the home energy management system (HEMS), a new charging and discharging strategy for EVs with energy price control is proposed for the best benefits of EV owners. RTP can also be used in the pricing strategy of charging stations [23, 24].A multiobjective comprehensive stand-alone solution is proposed [25] to use TOU to intelligently regulate the charging/discharging activities of EVs, with the purpose of cutting peaks and filling valleys of loads and operating costs of power system reduction. Further, a charging pricing strategy based on regional division and time division is proposed, where the charging prices between different areas of the city are optimized to guide EV users to select to charge in the area with more charging stations. Then, from the perspective of consumer satisfaction, grid company profits, and grid load variation, a TOU optimization model for EVs is constructed [26]. On the contrary, a pricing scheme is proposed assigning a per-session price to each charging session to accommodate the energy cost, demand charge, and system congestion [27]. The current pricing strategies for the charging stations mainly focus on the fixed electricity price or TOU price, which may cause congestion in local charging stations and undesirable peak loads on the grid. The RTP can guide the charging behavior of EVs to avoid invalid charging infrastructure investment and to maximize the revenue of charging stations [28, 29].Studies demonstrate that the charging price can affect the results of EV charging path planning and the selection of charging stations. The charging path planning can be considered as a multiobjective problem with driving distance, charging time, energy consumption, and charging fee. In this paper, these four objectives are combined together to plan the charging path for EVs based on bidirectional Martins’ algorithm. The driving time, charging time, and queuing time of EVs are used to estimate the total time consumption, while energy consumption of EVs and the charging price of the charging station are used to estimate the charging fee. The charging decision-making of EV users is stimulated through large-scale EV charging path planning. Besides, the PSO algorithm along with the charging path planning is used to solve the optimal charging price of the charging station so that the profit of the charging station is maximized, while the standard deviation of the profit of each charging station is minimized. The proposed method includes precalculation, query, and selection of three stages. In the precalculation stage, the topology of the road network and the locations of the charging stations are static and known. In the query stage, the heuristic items are added to each objective, using precomputed data to estimate the cost to the charging station. The main contributions of the paper are summarized as follows:(1)
An improved multiobjective charging path planning algorithm based on bidirectional Martins’ algorithm is proposed to solve the EV charging path problem. The bidirectional Martins’ algorithm is improved with adding heuristic items to the dimensions of distance, time, and energy consumption to estimate the cost to the end point, as well as the pruning method to speed up the calculation.(2)
A charging selection-based adaptive pricing strategy is established to maximize the total revenues of the charging stations, while balancing the profit of each charging station. The results of large-scale EV charging path planning is used to simulate the selection of charging stations with different prices for EV users, and the PSO algorithm is applied to solve the optimal solution of the charging station charging price.(3)
A series of simulation experiments have been performed with the Shenzhen city street map, including different roads, to verify the effectiveness of the model.The remainder of the paper is organized as follows. In Section2, the energy consumption model, the charging model, and the queuing model are presented; afterwards, an integer nonlinear programming model of charging path planning is developed. In Section 3, a multiobjective charging path planning algorithm based on bidirectional Martins’ algorithm is proposed with heuristic and pruning techniques and driver’s preference to solve the path planning problem and recommend the charging path to EV users. In Section 4, a charging selection-based pricing strategy for charging stations is proposed to maximize their revenues and balance the revenue of each charging station. In Section 5, simulation experiments are performed to illustrate the application and effectiveness of the proposed method. Conclusion and future works are given in Section 6.


## 2. Problem Formulation

In this section, the four optimization objectives, i.e., driving distance, total time consumption (summation of driving time, waiting time, and charging time), energy consumption, and charging fee are formulated as a mathematical model.Certain assumptions are made in this paper. (1) EVs are fully charged when they are charged at the charging stations. (2) Energy consumption is a positive value, and the recuperation when braking or driving down a slope is neglected.Considering a directed road networkGN,A, N is the set of nodes, and A is the set of links, and the link from node i to node j is defined as i,j∈A. The charging stations in a graph are defined as CS=c1,c2,…,ck,…cK and CS⊂N where each charging station is denoted as node ck, and K is the number of the charging stations. The total time consumption of a charging path ς is tς=tdς+twck+tcck, where tdς represents the driving time, twck represents the waiting time at the specific charging station ck, and tcck represents the charging time at the ck charging station. Table 1 lists the related parameters in the models.Table 1
The involved parameters in the EV charging path planning.
VariablesSpecificationNSet of nodes of the road networkKNumber of the charging stationsdςEV driving distance of the planned pathςdijDriving distance from nodei to node j of the EVtcckCharging time at the charging stationckpckCharging price of the charging stationckE0The battery capacity of the EVxijA bool integer denoting whether the linki,j is on the planned charging pathLiThe nodei label denoting the cost from the origin node to node i and the previous node labelASet of links of the road networkckThekth charging stationtςTotal time consumption of the planned pathςvijAverage velocity of the linki,jtwckWaiting time at the charging stationckfeeςCharging fee of the planned pathς for the EVEremThe remaining battery energy when the EV arrives at the charging stationrckCharging revenue of theck charging stationPThe driver’s preference to select a charging path from a Pareto set of pathsCSSet of all charging stationsςA planned charging path for the EVeςEnergy consumption of the planned path for the EVtdi,jDriving time from nodei to node j of the EVeijEnergy consumption from nodei to node j of the EVSOCInitial SOC when EV makes a query for charging path planningηckThe charging efficiency of the charging piles at theck charging stationCi,jCost vector from the nodei to the node j when planning the path


## 3. Energy Model of the EV

According to [30], the energy consumption of an EV is mainly related to the travelling distance dij and the average speed vij=dij/tdi,j. The energy consumption eijvij,dij of the link i,j under the condition of average speed vij and distance dij can be written as(1)eijvij,dij=dijηmotor0.5ρCwvij2+μmgcosθ+mgsinθ+dijPaddvij,where the parameters ρ, C, w,μ, g, and Padd represent the density of the air, drag coefficient, cross-sectional area, rolling resistance coefficient, gravity acceleration, and average additional energy consumption, respectively. The energy consumption function eij is a convex function, while Figure 1 depicts the energy consumption curve with the parameters dij=1km, ηmotor=0.9, ρ=1.29kg/m3, C=0.35, w=2.3m2, μ=0.015, m=1600kg, g=9.81m/s2, and Padd=1.5kW.Figure 1
Energy consumption function of the EV.It is noted that the developed energy consumption model is simplified by neglecting certain factors such as energy recovery, while braking. However, this does not affect the effectiveness of the method discussed later in this paper.


### 3.1. Charging Model

The charging time is calculated by the charging power of the charging station and the current SOC of EVs when EVs arrive at the charging stations. Most studies assume that the charging output power of the charging stations is the same among the charging stations. In practice, the charging power provided by the stations is varied, which could affect the EV charging time.Assuming that the charging pile power of the charging stationck is Pcck, the charging time tc of fully charged is calculated as(2)tcck=E0−EremPcck⋅ηck,Erem=SOC⋅E0−Eroad,Eroad=∑i,j∈Aeij⋅xij,xij=1,if linki,jis on the path,0,else,where Eroad is the required energy for the EV travelling to the charging station. The charging pile power Pcck varies depending on the charging level of the charging station. Four levels of the charging stations can be defined based on the facilities in the current market, see in Table 2.Table 2
The current charging levels of the charging stations in the market.
Charging levelCharging powerStandard2–5 kWMidaccelerated5–16 kWAccelerated16–30 kWFast30–350 kW


### 3.2. Queuing Model

The state of the EV charging station can be represented with the Markov chain by incorporating the state information, as shown in Figure2 [31]. The arrival of the EV is considered as a Poisson process with an arrival rate of λ, and each charging pile is considered to serve with an exponential service rate μ. A multiserver queue with s identical servers is considered here.Figure 2
Markov chain of the EV charging station.According to the queuing theory, the balance of each state in the queue model can be solved. In each state, the leaving rate based on arrival is equal to the entering rate based on departure, i.e.,(3)λπ0=μπ1,λ+μπ1=λπ0+2μπ2,λ+2μπ2=λπ1+3μπ3,⋯λ+k−1μπk−1=λπk−2+kμπk,where πk denotes the probability that the number of charged EVs in the charging station is k. The left side of equation (3) is the leaving rate, and the entering rate is described on the right side. Based on the state transition diagram given in equation (3), the corresponding transition matrix is written as(4)M=−λλ00μ−λ+μλ0002μ−λ+2μλ00003μ−λ+3μλ00……………………sμ−λ+sμλ.The stationary condition related to the Markov chain model is given by(5)π¯∗M=0¯,where π¯=π0,π1,…,πN is the queue length distribution under the condition of the stationary state, and the subscript `N is the state number. The general recursive form of the stationary distribution (state k) is derived as(6)πk=1k!λμkπ0,ifk≤s,1sk−s1s!λμkπ0,ifk≥s,where s is the number of the charging piles. Therefore, the mean queue length is given by(7)Elen=∑k=sNk−sπk,and the mean waiting time in the queue is given by(8)Etw=Elenλ1−πN.


### 3.3. Constraint Conditions

The flow balance constraints are applied here. For the origin node, the outgoing flows of all links are one more than the incoming flow. For the destination node, the incoming flows of all links are one more than the outgoing flow. For other nodes, the incoming flow is equal to the outgoing flow. So, the details of the flow balance constraint are expressed as follows:(9)∑i,j∈Axij−∑j,i∈Axji=bi,for eachi∈N,where bi denotes the flow balance of the node i, classified into three types, the starting node i=1, ending node i=ck, and passing nodes i≠1,ck:(10)b1=1,bc=−1,bi=0,fori≠1,ck,where ck denotes one of the charging stations, i.e., ck∈CS. Considering the limitation of the battery capacity in EVs, the remaining driving distance is limited, expressed as(11)∑i,j∈Aeij⋅xij<SOC⋅E0.


### 3.4. Optimization Objectives

Given a charging pathς, with the target charging station ck, the queuing time, charging time, and charging fee can thus be estimated for this path. The total driving distance dς, time consumption tς, total energy consumption eς, and charging fee feeς of the planned charging path ς with the target charging station ck are written as(12)dς=∑i,j∈Adij⋅xij,tς=tcck+twck+∑i,j∈Atdi,j⋅xij,eς=∑i,j∈Aeij⋅xij,feeς=pcck⋅E0−Eremηci.Note thatdij>0, tdi,j=dij/vij>0, and eij>0. The optimized objective of the model is formulated as(13)mindς,eς,tς,feeς.The above multiobjective optimization is an integer nonlinear programming problem with the decision variables ofck and xij of each link i,j, which has a high temporal complexity. How to select the optimal paths is already an intrigue problem.


## 3.1. Charging Model

The charging time is calculated by the charging power of the charging station and the current SOC of EVs when EVs arrive at the charging stations. Most studies assume that the charging output power of the charging stations is the same among the charging stations. In practice, the charging power provided by the stations is varied, which could affect the EV charging time.Assuming that the charging pile power of the charging stationck is Pcck, the charging time tc of fully charged is calculated as(2)tcck=E0−EremPcck⋅ηck,Erem=SOC⋅E0−Eroad,Eroad=∑i,j∈Aeij⋅xij,xij=1,if linki,jis on the path,0,else,where Eroad is the required energy for the EV travelling to the charging station. The charging pile power Pcck varies depending on the charging level of the charging station. Four levels of the charging stations can be defined based on the facilities in the current market, see in Table 2.Table 2
The current charging levels of the charging stations in the market.
Charging levelCharging powerStandard2–5 kWMidaccelerated5–16 kWAccelerated16–30 kWFast30–350 kW


## 3.2. Queuing Model

The state of the EV charging station can be represented with the Markov chain by incorporating the state information, as shown in Figure2 [31]. The arrival of the EV is considered as a Poisson process with an arrival rate of λ, and each charging pile is considered to serve with an exponential service rate μ. A multiserver queue with s identical servers is considered here.Figure 2
Markov chain of the EV charging station.According to the queuing theory, the balance of each state in the queue model can be solved. In each state, the leaving rate based on arrival is equal to the entering rate based on departure, i.e.,(3)λπ0=μπ1,λ+μπ1=λπ0+2μπ2,λ+2μπ2=λπ1+3μπ3,⋯λ+k−1μπk−1=λπk−2+kμπk,where πk denotes the probability that the number of charged EVs in the charging station is k. The left side of equation (3) is the leaving rate, and the entering rate is described on the right side. Based on the state transition diagram given in equation (3), the corresponding transition matrix is written as(4)M=−λλ00μ−λ+μλ0002μ−λ+2μλ00003μ−λ+3μλ00……………………sμ−λ+sμλ.The stationary condition related to the Markov chain model is given by(5)π¯∗M=0¯,where π¯=π0,π1,…,πN is the queue length distribution under the condition of the stationary state, and the subscript `N is the state number. The general recursive form of the stationary distribution (state k) is derived as(6)πk=1k!λμkπ0,ifk≤s,1sk−s1s!λμkπ0,ifk≥s,where s is the number of the charging piles. Therefore, the mean queue length is given by(7)Elen=∑k=sNk−sπk,and the mean waiting time in the queue is given by(8)Etw=Elenλ1−πN.


## 3.3. Constraint Conditions

The flow balance constraints are applied here. For the origin node, the outgoing flows of all links are one more than the incoming flow. For the destination node, the incoming flows of all links are one more than the outgoing flow. For other nodes, the incoming flow is equal to the outgoing flow. So, the details of the flow balance constraint are expressed as follows:(9)∑i,j∈Axij−∑j,i∈Axji=bi,for eachi∈N,where bi denotes the flow balance of the node i, classified into three types, the starting node i=1, ending node i=ck, and passing nodes i≠1,ck:(10)b1=1,bc=−1,bi=0,fori≠1,ck,where ck denotes one of the charging stations, i.e., ck∈CS. Considering the limitation of the battery capacity in EVs, the remaining driving distance is limited, expressed as(11)∑i,j∈Aeij⋅xij<SOC⋅E0.


## 3.4. Optimization Objectives

Given a charging pathς, with the target charging station ck, the queuing time, charging time, and charging fee can thus be estimated for this path. The total driving distance dς, time consumption tς, total energy consumption eς, and charging fee feeς of the planned charging path ς with the target charging station ck are written as(12)dς=∑i,j∈Adij⋅xij,tς=tcck+twck+∑i,j∈Atdi,j⋅xij,eς=∑i,j∈Aeij⋅xij,feeς=pcck⋅E0−Eremηci.Note thatdij>0, tdi,j=dij/vij>0, and eij>0. The optimized objective of the model is formulated as(13)mindς,eς,tς,feeς.The above multiobjective optimization is an integer nonlinear programming problem with the decision variables ofck and xij of each link i,j, which has a high temporal complexity. How to select the optimal paths is already an intrigue problem.


## 4. Solution Algorithm

In this section, the basic Martins’ algorithm (MA) [16] and the bidirectional Martins’ algorithm (BMA) [17] are introduced first, and an improved EV heuristic bidirectional Martins’ algorithm (EHBMA) is designed to optimize the objectives described in equation (13).


### 4.1. The Basic Algorithm

In order to develop the algorithm, certain definitions are introduced first, where the cost vector of the linki,j is denoted as Ci,j=dij,tdi,j,eij, the node i label is denoted as Li=i,Co,i,previous_label, and o is the origin point of the path.Definition 1.
Given two cost vectors of linkCi,j and Cm,n, Ci,j dominates Cm,n if and only if dij≤dmn, tdi,j≤tdm,n, and eij≤eij and at least one inequality is strict.Definition 2.
Given two pathsςi and ςj containing a series of nodes ςi=o,i,…,m,ck and ςj=o,j,…,n,cl, with two target charging station ck and cl, ςi dominates ςj if and only if dςi≤dςj, tςi≤tςj, eςi≤eςj, and feeςi≤feeςj and at least one inequality is strict. A path ς is a nondominated path if and only if ς is an optimal path in at least one objective, and it is not dominated by any other paths.Definition 3.
Given two node labelsLi and Lj of node i and nodej, Li dominates Lj if and only if i=j and Coi dominates Coj.
In the original MA, new labelLnewi is added to the node i if and only if the label Lnewi is not dominated by other labels of the node i. Further, the bidirectional MA (BMA) can limit the search area by formulating a termination condition and searching the network bidirectionally. The pseudocodes of the MA and BMA are shown in Algorithms 1 and 2, respectively, where the target point is represented by t, and miniT represents the minimum value of each objective value of all labels in T, forming the vector min1T,min2T,…,minobjective_numT.Algorithm 1: Basic Martins’ algorithm.
Create a listTThe initial element in the listT is the label of the starting point o, o,0,0,0,NULLCreate the path setPATH_RESULT(1)
WhileT is not empty(2)
Get the minimum node label inT, Lnode(3)
For the adjacent node, new_node(4)
Calculate the label of the adjacent pointLnew_node(5)
IfLnew_node is not dominated by other node labels of new_node, and not dominated by labels in PATH_RESULT(6)
Then put Lnew_node into list T(7)
Ifnew_node=t(8)
Then get the previous nodes of new_node, and put the path nodes into PATH_RESULTAlgorithm 2: Bidirectional Martins’ algorithm.
Create a forward listT_FOR and a backward list T_BACKThe initial element inT_FOR is the label of the starting point o, o,0,0,0,NULL, and the initial element in T_BACK is the label of the end point t, t,0,0,0,NULLCreate the path setPATH_RESULTThe initial search direction is forwarddirection=0(1)
WhileminiT_FOR+miniT_BACK is not dominated by PATH_RESULT(2)
Ifdirection=0, Then get the minimum node label Lnode in T_FOR(3)
For the child adjacent node of node, new_node(4)
Calculate the node label of the adjacent point,L_FORnew_node(5)
IfL_FORnew_node is not dominated by other node labels of new_node, Then put L_FORnew_node into T_FOR(6)
Ifdirection=1, Then get the minimum node label Lnode in T_BACK(7)
For the parent adjacent node of node, new_node(8)
Calculate the node label of the adjacent point,L_BACKnew_node(9)
IfL_BACKnew_node is not dominated by other node labels of new_node, Then put L_BACKnew_node into T_BACK(10)
If the label of new_node is in the list of reverse direction, Then obtain the final path by return the previous node label in L_FOR and L_BACK, and add the path intoPATH_RESULT(11)
Change the direction to the opposite


### 4.2. Improved EV Heuristic Bidirectional Martins’ Algorithm (EHBMA)

Based on the BMA, considering the EV charging path planning scenario, the EHBMA is proposed in this paper, including three stages. In the 1st stage, the map data is preprocessed, and the shortest distance from each charging station to each node is calculated and stored. In the 2nd stage, considering that EV users hardly travel too far to charge in general situations, the three closest charging stations are preselected as alternatives according to the preprocessed map data, then the multiobjective path planning process is performed among the selected charging stations to achieve candidate paths. In the 3rd stage, the final charging path is selected according to EV user’s preference. Moreover, in order to speed up the path planning process, the heuristic method and pruning method are introduced in the EHBMA.


#### 4.2.1. Heuristic Method

To estimate the remaining distance, travelling time, and required energy consumption to the charging station, the heuristic items offdi, fti, and fei are added to the original label of node i. After adding the heuristic items, the nodes with calculated closer distance to the target charging station, shorter travelling time, and less energy consumption are visited first so that EVs can reach the target charging station faster with fewer nodes traversed than the original algorithm.The heuristic items of the forward search and backward search are different, assuming that thedirection=0 represents the forward search (i.e., from origin node o to the target charging station ck), and direction=1 represents the opposite direction. In the distance dimension,(14)fdi=SPLi,ck,direction=0,EuDisto,i,direction=1,where SPLi,ck is the shortest distance from the current node i to the charging station ck and EuDisto,i is the Euler distance from the origin node o to the current node i. In the time dimension, it has(15)fei=SPLi,ckv¯,direction=0,EuDisto,iv¯,direction=1,where v¯ denotes the past average driving speed of the EV. In the energy consumption dimension,(16)fei=SPLi,ck⋅e¯,direction=0,EuDisto,i⋅e¯,direction=1,where e¯ denotes the past average energy consumption of the EV. Therefore, the new node label of node i with heuristic items can be calculated as(17)L_HEUi=i,Co,i,Co,i+Hi,previous_label,direction=0,i,Ci,ck,Ci,ck+Hi,previous_label,direction=1,Hi=fdi,fti,fei.Definition 4.
L_HEUi dominates L_HEUj if and only if the two conditions hold, 1) i=j and 2) Co,i+Hi dominates Co,j+Hj if direction=0 or Ci,ck+Hi dominates Cj,ck+Hj if direction=1.


#### 4.2.2. Pruning Method

If the labelL_HEUi of node i is dominated by the labels of the existing path from the origin node to the target node or the estimated energy consumption fei of the node i is greater than the remaining power of the EV, the node i will not be traversed in the algorithm. By pruning the traversed node, algorithm efficiency can be further improved.


#### 4.2.3. The Driver’s Preference

A set of Pareto optimal solutions can be achieved after performing the proposed algorithm, and the most optimal path can be selected according to the driver’s behavior preferences, described as(18)P=α⋅dς+β⋅tς+γ⋅eς⋅μ⋅feeςλck,where α,β,γ,andμ denote the preference factors. By setting appropriate preference factors, the driver can be recommended the most suitable charging path. λck is a comprehensive metric of preference for the path to the charging station ck, which depends on the factors of the number of recreation areas and living facilities around the charging station ck. The higher the value, the more the inclination of the driver to select this charging station ck.In summary, the multiobjective charging path planning algorithm EHBMA is described with Algorithm3.Algorithm 3: The proposed EHBMA.
InitializationInitialize the average velocityvij of each road link i,j based on the traffic condition.Calculate the energy consumptioneij and driving time tdi,j of the road link i,j based on the energy consumption model and average velocity.Calculate the shortest distance from each charging station to each node on the map and save the result as a dictionarypreprocessing in which the keys are charging station nodes and the values are all other nodes on the map.Initialize the location of the EV,o.Charging Path PlanningSelect three charging stationscs_nearest closest to the current location o by query the data preprocessing.(1)
Forck∈cs_nearest(2)
Create a forward listT_FOR and a backward list T_BACK(3)
The initial elements inT_FOR and T_BACK are the label of the starting point o, o,0,0,0,0,0,0,NULL, and the label of the end point ck, ck,0,0,0,0,0,0,NULL(4)
Create the path setPATH_RESULT(5)
The initial search direction is forwarddirection=0(6)
WhileminiT_FOR+miniT_BACK is not dominated by the label in PATH_RESULT(7)
Ifdirection=0, Then get the minimum node label L_HEUnode in T_FOR(8)
For the child adjacent node of node, new_node(9)
Calculate the heuristic itemsHnew_node by query preprocessing(10)
Calculate the node label of the adjacent node,L_HEU_FORnew_node(11)
IfL_HEU_FORnew_node is not dominated by other node label of new_node, Then put L_HEU_FORnew_node into T_FOR(12)
Ifdirection=1, Then get the minimum node label L_HEUnode in T_BACK(13)
For the parent adjacent node of node, new_node(14)
Calculate the heuristic itemsHnew_node(15)
Calculate the node label of the adjacent node,L_HEU_BACKnew_node(16)
IfL_HEU_BACKnew_node is not dominated by other node label of new_node, Then put L_HEU_BACKnew_node into T_BACK(17)
If the label of new_node is in the list of reverse direction, Then get a path by return the previous node label in L_HEU_FOR andL_HEU_BACK, and add the path into PATH_RESULT(18)
Change direction to the opposite(19)
Pareto Path Selection(20)
Forς∈PATH_RESULT, its end point is a charging station ck,(21)
dς=∑i,j∈ςdij(22)
eς=∑i,j∈ζeij(23)
tς=tcck+twck+∑i,j∈ζtdi,j(24)
feeς=pcck⋅E0−Erem/ηck(25)
Calculate the driver preferenceP=α⋅dς+β⋅tς+γ⋅eς⋅μ⋅feeς/λck.(26)
Select charging path and charging station of the smallestP, which is the final planned path recommended to the EV users.


## 4.1. The Basic Algorithm

In order to develop the algorithm, certain definitions are introduced first, where the cost vector of the linki,j is denoted as Ci,j=dij,tdi,j,eij, the node i label is denoted as Li=i,Co,i,previous_label, and o is the origin point of the path.Definition 1.
Given two cost vectors of linkCi,j and Cm,n, Ci,j dominates Cm,n if and only if dij≤dmn, tdi,j≤tdm,n, and eij≤eij and at least one inequality is strict.Definition 2.
Given two pathsςi and ςj containing a series of nodes ςi=o,i,…,m,ck and ςj=o,j,…,n,cl, with two target charging station ck and cl, ςi dominates ςj if and only if dςi≤dςj, tςi≤tςj, eςi≤eςj, and feeςi≤feeςj and at least one inequality is strict. A path ς is a nondominated path if and only if ς is an optimal path in at least one objective, and it is not dominated by any other paths.Definition 3.
Given two node labelsLi and Lj of node i and nodej, Li dominates Lj if and only if i=j and Coi dominates Coj.
In the original MA, new labelLnewi is added to the node i if and only if the label Lnewi is not dominated by other labels of the node i. Further, the bidirectional MA (BMA) can limit the search area by formulating a termination condition and searching the network bidirectionally. The pseudocodes of the MA and BMA are shown in Algorithms 1 and 2, respectively, where the target point is represented by t, and miniT represents the minimum value of each objective value of all labels in T, forming the vector min1T,min2T,…,minobjective_numT.Algorithm 1: Basic Martins’ algorithm.
Create a listTThe initial element in the listT is the label of the starting point o, o,0,0,0,NULLCreate the path setPATH_RESULT(1)
WhileT is not empty(2)
Get the minimum node label inT, Lnode(3)
For the adjacent node, new_node(4)
Calculate the label of the adjacent pointLnew_node(5)
IfLnew_node is not dominated by other node labels of new_node, and not dominated by labels in PATH_RESULT(6)
Then put Lnew_node into list T(7)
Ifnew_node=t(8)
Then get the previous nodes of new_node, and put the path nodes into PATH_RESULTAlgorithm 2: Bidirectional Martins’ algorithm.
Create a forward listT_FOR and a backward list T_BACKThe initial element inT_FOR is the label of the starting point o, o,0,0,0,NULL, and the initial element in T_BACK is the label of the end point t, t,0,0,0,NULLCreate the path setPATH_RESULTThe initial search direction is forwarddirection=0(1)
WhileminiT_FOR+miniT_BACK is not dominated by PATH_RESULT(2)
Ifdirection=0, Then get the minimum node label Lnode in T_FOR(3)
For the child adjacent node of node, new_node(4)
Calculate the node label of the adjacent point,L_FORnew_node(5)
IfL_FORnew_node is not dominated by other node labels of new_node, Then put L_FORnew_node into T_FOR(6)
Ifdirection=1, Then get the minimum node label Lnode in T_BACK(7)
For the parent adjacent node of node, new_node(8)
Calculate the node label of the adjacent point,L_BACKnew_node(9)
IfL_BACKnew_node is not dominated by other node labels of new_node, Then put L_BACKnew_node into T_BACK(10)
If the label of new_node is in the list of reverse direction, Then obtain the final path by return the previous node label in L_FOR and L_BACK, and add the path intoPATH_RESULT(11)
Change the direction to the opposite


## 4.2. Improved EV Heuristic Bidirectional Martins’ Algorithm (EHBMA)

Based on the BMA, considering the EV charging path planning scenario, the EHBMA is proposed in this paper, including three stages. In the 1st stage, the map data is preprocessed, and the shortest distance from each charging station to each node is calculated and stored. In the 2nd stage, considering that EV users hardly travel too far to charge in general situations, the three closest charging stations are preselected as alternatives according to the preprocessed map data, then the multiobjective path planning process is performed among the selected charging stations to achieve candidate paths. In the 3rd stage, the final charging path is selected according to EV user’s preference. Moreover, in order to speed up the path planning process, the heuristic method and pruning method are introduced in the EHBMA.


### 4.2.1. Heuristic Method

To estimate the remaining distance, travelling time, and required energy consumption to the charging station, the heuristic items offdi, fti, and fei are added to the original label of node i. After adding the heuristic items, the nodes with calculated closer distance to the target charging station, shorter travelling time, and less energy consumption are visited first so that EVs can reach the target charging station faster with fewer nodes traversed than the original algorithm.The heuristic items of the forward search and backward search are different, assuming that thedirection=0 represents the forward search (i.e., from origin node o to the target charging station ck), and direction=1 represents the opposite direction. In the distance dimension,(14)fdi=SPLi,ck,direction=0,EuDisto,i,direction=1,where SPLi,ck is the shortest distance from the current node i to the charging station ck and EuDisto,i is the Euler distance from the origin node o to the current node i. In the time dimension, it has(15)fei=SPLi,ckv¯,direction=0,EuDisto,iv¯,direction=1,where v¯ denotes the past average driving speed of the EV. In the energy consumption dimension,(16)fei=SPLi,ck⋅e¯,direction=0,EuDisto,i⋅e¯,direction=1,where e¯ denotes the past average energy consumption of the EV. Therefore, the new node label of node i with heuristic items can be calculated as(17)L_HEUi=i,Co,i,Co,i+Hi,previous_label,direction=0,i,Ci,ck,Ci,ck+Hi,previous_label,direction=1,Hi=fdi,fti,fei.Definition 4.
L_HEUi dominates L_HEUj if and only if the two conditions hold, 1) i=j and 2) Co,i+Hi dominates Co,j+Hj if direction=0 or Ci,ck+Hi dominates Cj,ck+Hj if direction=1.


### 4.2.2. Pruning Method

If the labelL_HEUi of node i is dominated by the labels of the existing path from the origin node to the target node or the estimated energy consumption fei of the node i is greater than the remaining power of the EV, the node i will not be traversed in the algorithm. By pruning the traversed node, algorithm efficiency can be further improved.


### 4.2.3. The Driver’s Preference

A set of Pareto optimal solutions can be achieved after performing the proposed algorithm, and the most optimal path can be selected according to the driver’s behavior preferences, described as(18)P=α⋅dς+β⋅tς+γ⋅eς⋅μ⋅feeςλck,where α,β,γ,andμ denote the preference factors. By setting appropriate preference factors, the driver can be recommended the most suitable charging path. λck is a comprehensive metric of preference for the path to the charging station ck, which depends on the factors of the number of recreation areas and living facilities around the charging station ck. The higher the value, the more the inclination of the driver to select this charging station ck.In summary, the multiobjective charging path planning algorithm EHBMA is described with Algorithm3.Algorithm 3: The proposed EHBMA.
InitializationInitialize the average velocityvij of each road link i,j based on the traffic condition.Calculate the energy consumptioneij and driving time tdi,j of the road link i,j based on the energy consumption model and average velocity.Calculate the shortest distance from each charging station to each node on the map and save the result as a dictionarypreprocessing in which the keys are charging station nodes and the values are all other nodes on the map.Initialize the location of the EV,o.Charging Path PlanningSelect three charging stationscs_nearest closest to the current location o by query the data preprocessing.(1)
Forck∈cs_nearest(2)
Create a forward listT_FOR and a backward list T_BACK(3)
The initial elements inT_FOR and T_BACK are the label of the starting point o, o,0,0,0,0,0,0,NULL, and the label of the end point ck, ck,0,0,0,0,0,0,NULL(4)
Create the path setPATH_RESULT(5)
The initial search direction is forwarddirection=0(6)
WhileminiT_FOR+miniT_BACK is not dominated by the label in PATH_RESULT(7)
Ifdirection=0, Then get the minimum node label L_HEUnode in T_FOR(8)
For the child adjacent node of node, new_node(9)
Calculate the heuristic itemsHnew_node by query preprocessing(10)
Calculate the node label of the adjacent node,L_HEU_FORnew_node(11)
IfL_HEU_FORnew_node is not dominated by other node label of new_node, Then put L_HEU_FORnew_node into T_FOR(12)
Ifdirection=1, Then get the minimum node label L_HEUnode in T_BACK(13)
For the parent adjacent node of node, new_node(14)
Calculate the heuristic itemsHnew_node(15)
Calculate the node label of the adjacent node,L_HEU_BACKnew_node(16)
IfL_HEU_BACKnew_node is not dominated by other node label of new_node, Then put L_HEU_BACKnew_node into T_BACK(17)
If the label of new_node is in the list of reverse direction, Then get a path by return the previous node label in L_HEU_FOR andL_HEU_BACK, and add the path into PATH_RESULT(18)
Change direction to the opposite(19)
Pareto Path Selection(20)
Forς∈PATH_RESULT, its end point is a charging station ck,(21)
dς=∑i,j∈ςdij(22)
eς=∑i,j∈ζeij(23)
tς=tcck+twck+∑i,j∈ζtdi,j(24)
feeς=pcck⋅E0−Erem/ηck(25)
Calculate the driver preferenceP=α⋅dς+β⋅tς+γ⋅eς⋅μ⋅feeς/λck.(26)
Select charging path and charging station of the smallestP, which is the final planned path recommended to the EV users.


## 4.2.1. Heuristic Method

To estimate the remaining distance, travelling time, and required energy consumption to the charging station, the heuristic items offdi, fti, and fei are added to the original label of node i. After adding the heuristic items, the nodes with calculated closer distance to the target charging station, shorter travelling time, and less energy consumption are visited first so that EVs can reach the target charging station faster with fewer nodes traversed than the original algorithm.The heuristic items of the forward search and backward search are different, assuming that thedirection=0 represents the forward search (i.e., from origin node o to the target charging station ck), and direction=1 represents the opposite direction. In the distance dimension,(14)fdi=SPLi,ck,direction=0,EuDisto,i,direction=1,where SPLi,ck is the shortest distance from the current node i to the charging station ck and EuDisto,i is the Euler distance from the origin node o to the current node i. In the time dimension, it has(15)fei=SPLi,ckv¯,direction=0,EuDisto,iv¯,direction=1,where v¯ denotes the past average driving speed of the EV. In the energy consumption dimension,(16)fei=SPLi,ck⋅e¯,direction=0,EuDisto,i⋅e¯,direction=1,where e¯ denotes the past average energy consumption of the EV. Therefore, the new node label of node i with heuristic items can be calculated as(17)L_HEUi=i,Co,i,Co,i+Hi,previous_label,direction=0,i,Ci,ck,Ci,ck+Hi,previous_label,direction=1,Hi=fdi,fti,fei.Definition 4.
L_HEUi dominates L_HEUj if and only if the two conditions hold, 1) i=j and 2) Co,i+Hi dominates Co,j+Hj if direction=0 or Ci,ck+Hi dominates Cj,ck+Hj if direction=1.


## 4.2.2. Pruning Method

If the labelL_HEUi of node i is dominated by the labels of the existing path from the origin node to the target node or the estimated energy consumption fei of the node i is greater than the remaining power of the EV, the node i will not be traversed in the algorithm. By pruning the traversed node, algorithm efficiency can be further improved.


## 4.2.3. The Driver’s Preference

A set of Pareto optimal solutions can be achieved after performing the proposed algorithm, and the most optimal path can be selected according to the driver’s behavior preferences, described as(18)P=α⋅dς+β⋅tς+γ⋅eς⋅μ⋅feeςλck,where α,β,γ,andμ denote the preference factors. By setting appropriate preference factors, the driver can be recommended the most suitable charging path. λck is a comprehensive metric of preference for the path to the charging station ck, which depends on the factors of the number of recreation areas and living facilities around the charging station ck. The higher the value, the more the inclination of the driver to select this charging station ck.In summary, the multiobjective charging path planning algorithm EHBMA is described with Algorithm3.Algorithm 3: The proposed EHBMA.
InitializationInitialize the average velocityvij of each road link i,j based on the traffic condition.Calculate the energy consumptioneij and driving time tdi,j of the road link i,j based on the energy consumption model and average velocity.Calculate the shortest distance from each charging station to each node on the map and save the result as a dictionarypreprocessing in which the keys are charging station nodes and the values are all other nodes on the map.Initialize the location of the EV,o.Charging Path PlanningSelect three charging stationscs_nearest closest to the current location o by query the data preprocessing.(1)
Forck∈cs_nearest(2)
Create a forward listT_FOR and a backward list T_BACK(3)
The initial elements inT_FOR and T_BACK are the label of the starting point o, o,0,0,0,0,0,0,NULL, and the label of the end point ck, ck,0,0,0,0,0,0,NULL(4)
Create the path setPATH_RESULT(5)
The initial search direction is forwarddirection=0(6)
WhileminiT_FOR+miniT_BACK is not dominated by the label in PATH_RESULT(7)
Ifdirection=0, Then get the minimum node label L_HEUnode in T_FOR(8)
For the child adjacent node of node, new_node(9)
Calculate the heuristic itemsHnew_node by query preprocessing(10)
Calculate the node label of the adjacent node,L_HEU_FORnew_node(11)
IfL_HEU_FORnew_node is not dominated by other node label of new_node, Then put L_HEU_FORnew_node into T_FOR(12)
Ifdirection=1, Then get the minimum node label L_HEUnode in T_BACK(13)
For the parent adjacent node of node, new_node(14)
Calculate the heuristic itemsHnew_node(15)
Calculate the node label of the adjacent node,L_HEU_BACKnew_node(16)
IfL_HEU_BACKnew_node is not dominated by other node label of new_node, Then put L_HEU_BACKnew_node into T_BACK(17)
If the label of new_node is in the list of reverse direction, Then get a path by return the previous node label in L_HEU_FOR andL_HEU_BACK, and add the path into PATH_RESULT(18)
Change direction to the opposite(19)
Pareto Path Selection(20)
Forς∈PATH_RESULT, its end point is a charging station ck,(21)
dς=∑i,j∈ςdij(22)
eς=∑i,j∈ζeij(23)
tς=tcck+twck+∑i,j∈ζtdi,j(24)
feeς=pcck⋅E0−Erem/ηck(25)
Calculate the driver preferenceP=α⋅dς+β⋅tς+γ⋅eς⋅μ⋅feeς/λck.(26)
Select charging path and charging station of the smallestP, which is the final planned path recommended to the EV users.


## 5. Charging Selection-Based Adaptive Pricing Strategy (CSBAP)

In this section, the CSBAP is proposed to determine the charging price of the charging stations, so as to maximize the overall profits and balance the profits of each charging station. The details are explained as follows.For charging stationck, the revenue rck can be calculated as(19)rck=∑EVpcck⋅E0−Eremηck.The profits of the charging stations may be influenced by its location which could result in unbalanced profits’ distribution and unable to maximize the total profits, while appropriate prices’ setting can attract more EVs to balance the profits’ distribution. From the analysis of the previous section, the charging selection of EV users can be influenced by the charging price. Therefore, the CSBAP is proposed accordingly along with the proposed charging path planning algorithm EHBMA and PSO algorithm, in which the EHBMA is used to simulate the selection of charging stations with different prices for EV users, and the PSO is applied to adjust the charging prices adaptively. The pseudocodes of the PSO algorithm are shown in Algorithm4. Here, parti denotes the ith particle, pos denotes the decision variable vector, and the velocity V represents the changing rate of pos. The fitness function fitpos denotes the objective value to evaluate the equality of pos, pBest and gBest denote the best-known position of the single particle and the best-known position of the whole swarm, respectively, rand represents a random number in 0,1, ε denotes the minimum deviation of pos of the two iterations, and MAX denotes the maximum number of iterations.Algorithm 4: The PSO algorithm.
Initialization The particle swarm PSO is initialized with the population amount m. Position pos and velocity V of each particle parti are initialized randomly in the feasible interval. parti.pBest and gBest are initialized as fitparti.pos and maxifitparti.pos, respectively. The inertia factor ω and the acceleration constant C1C2 are initialized as constants.(1)
Whilemaxiparti.pos−parti.previous_pos>ε or iteration_count≤MAX(2)
For each particle parti∈PSO, update the position pos and the velocity V as follows,(3)
parti.V=ωparti.V+C1randparti.pBest−parti.pos+C2randgBestid−parti.posparti.pos=parti.pos+Vid(4)
Iffitparti.pos≥fitparti.previous_pos, Thenparti.pBest=fitparti.pos(5)
Iffitparti.pos≥fitgBest, ThengBest=fitparti.pos(6)
parti.previous_pos=parti.pos(7)
Output the optimal position gBest and optimized objective fitgBestWith the combined PSO algorithm and the proposed EHBMA, the pricing strategy for single charging station and multiple charging stations is designed separately. First, the relationship between the charging price and the revenue of a single charging station is studied. Assuming that the charging prices of all charging stations are fixed, except for the objective charging station, the fitness function can be defined asfit=rck, where rck denotes the revenue of the charging station ck. The position of the particle can be defined as the charging price pcck of the charging station ck to acquire the optimal charging price gBest for the charging station.The pricing strategy for multiple charging stations is further investigated. The fitness function is defined as the summation of the total revenues of all charging stations and the standard deviation of revenuesfit=∑ciCrck−ρ⋅stdr^ck, where stdr^ck denotes the standard deviation of the revenue of all charging stations and ρ denotes the coefficient to make the trade-off between two factors. The positions of the particles are defined as the charging price vector of all charging stations. The fitness function is designed to maximize the total profits of the charging stations, while balancing the profit of each charging station. The pricing system is adopted with the real-time charging path planning simulation.


## 6. Simulation Results

A road network dataset of Shenzhen city is used to verify the effectiveness of the model. The dataset is collected from the OpenStreetMap, which includes residential street, tertiary road, secondary road, primary road, trunk road, and motorway, while each road is composed of multiple location nodes with longitude and latitude of the WGS84 coordinate system. Moreover, the location of the charging stations, one-way or two-way characteristics, road length, and speed limitation are given in the dataset.The road networks in Shenzhen is shown in Figure3(a), and the speed limit of different road types are listed in Table 3, and the used road network is shown in Figure 3(b) with charging stations marked on the figures. The driving roads are selected to construct a simplified road network, which includes 658,213 nodes, 132,182 edges, and 22 public charging stations.Figure 3
Road network of Shenzhen (2019): (a) original road network; (b) the selected road network with charging stations.
(a)(b)Table 3
Speed limit of the roads.
Road typeSpeed limit (km/h)Residential road20Tertiary road30Secondary road50Primary road90Trunk road100Motorway road120The total amount of EVs in Shenzhen is about 272,687 (by 17th Oct, 2019). Since most of the EVs are charged at private charging stations, we randomly select 1000 EVs to simulate. The initial locations of EVs are randomly distributed at various nodes of the map, and the initial SOC is randomly set between 10% and 90%. It is assumed that EVs will generate charging demand when SOC≤20% and fully charged at the charging stations. The charging piles’ number of the charging stations is randomly initialized in the interval [10, 50].


### 6.1. Comparison between MA, BMA, and Our Proposed EHBMA

MA, BMA, and EHBMA are performed to select nodes to the charging station. The execution time and the traversed node label number of the three algorithms are shown in Table4. It is demonstrated that MA costs the longest time, and EHBMA costs the shortest time. The traversed nodes are marked with different colors in Figures 4–6, where the green points and the blue points represent the nodes which are searched forward and backward, respectively. It can be concluded that BMA traverses fewer nodes than MA, while the proposed EHBMA traverses least nodes than both of MA and BMA.Table 4
Performance comparison of MA, BMA, and EHBMA.
MABMAEHBMAComputation time (s)46.576.280.31Number of the traversed nodes41297133241552Figure 4
Charging path planning by MA.Figure 5
Charging path planning by BMA.Figure 6
Charging path planning by EHBMA.


### 6.2. Single EV Charging Path Planning Simulation

The simulation parameters are set as follows. The charging price is fixed as 1.75 RMB/kWh for all charging stations. The driver preference factors areα=0.6,β=1800,γ=703,andμ=0.02, and the initial locations are randomly selected on the map with initial SOC=20% and E0=70kWh.In Figure7, the red, blue, and green paths are the charging paths to the three preselected charging stations, No. 8, No. 13, and No. 12, respectively. The cost of the paths, as shown in Table 5, is used to calculate the driver’s preference, through which the driving distance, energy consumption, time consumption, and charging fee are considered with a trade-off. Then, the path with the smallest P value is selected, so the green path to charging station No. 12 is the final planned charging path.Figure 7
Charging path planning for single EV.Table 5
Cost of the paths to three charging stations.
Charging station numberDriving distance (km)Time consumption (h)Energy consumption (kWh)Charging fee (RMB)Driver preferenceP813416.5362.1462.17387.80351287.242125407.8772.0020.74585.3059370.2171316814.4982.2312.66188.65875376.958


### 6.3. Large-Scale EVs Charging Path Planning Simulation

In this experiment, 1000 EVs are randomly selected on the map. The simulation parameter settings are as follows. Charging price for all charging stations is set as a constant value, 1.75 RMB/kWh. The charging threshold of EVs is set to SOC = 20%. The battery capacityE0 is randomly initialized between 50kWh and 90kWh, and the driver preference factors are α=0.6,β=1800,γ=703,andμ=0.02.The results of the large-scale EVs’ path planning using EHBMA are shown in Figure8. The total revenues of all charging stations, revenue of each charging station, and EV charging amount of each charging station are listed in Tables 6–8, which demonstrate that the revenues and EV amount between different charging stations are not equal. Therefore, it is necessary to optimize the charging price to maximize the total revenue and balance the revenue of each charging station.Figure 8
Path planning for large-scale EV users.Table 6
Total revenues of charging stations based on large-scale EV path planning.
Total revenues of the charging station (RMB)Standard deviation of revenues for each charging station85878.6351312.150Table 7
Revenue of each charging station.
Number1234567891011Revenue (RMB)5074.944248.564885.474960.574721.401023.803137.471628.303502.232125.781019.49Number1213141516171819202122Revenue (RMB)3438.184818.884983.964698.364623.164821.923160.765060.514831.884310.154802.79Table 8
Charging EV amount of each charging station.
Number1234567891011EV amount5950575855123619412512Number1213141516171819202122EV amount4056585554563659565056


### 6.4. The Simulation of CSBAP

In this experiment, the population of the particle swarm in PSO is set asm=20, and the maximum number of iterations is set as MAX=100.Considering the pricing strategy for the single charging station, the No. 6 charging station is used as a case study. Table9 lists the revenue of the charging station No. 6 when the prices of charging stations are fixed as the same price and the charging price is adjusted by CSBAP. The results show that, after the charging price of the charging station No. 6 is adjusted by CSBAP, more revenue can be obtained than the fixed charging price strategy, since the lower price would attract more EVs to charge. Therefore, the effectiveness of our proposed CSBAP for a single charging station is validated.Table 9
Revenue of the charging station No. 6.
Pricing strategyCharging price (RMB/kWh)RevenueEV amountFixed charging price1.791863.0521CSBAP1.612049.0723As the charging pricing strategy for all charging stations, the simulation conditions are set as follows. The prices of the charging stations are limited to the interval [1.5–2.0] RMB/kWh.m=20, and MAX=100. The fitness function is defined as(20)fit=∑ciCrci−10⋅stdr^ci.Figure9 shows that the value of the fitness function gradually rises and eventually stabilizes with 100 iterations of the charging price. Figure 10 illustrates that, after the iterations of CSBAP, the total revenues of all charging stations gradually increase and eventually stabilize. The different color columns in Figure 10 represent the profits of different charging stations. Figure 11 demonstrates that, after the iterations of CSBAP, the revenue standard deviation of charging stations gradually decreases and eventually stabilizes, indicating that the revenues between charging stations are more balanced than those without optimization. Taking the charging price of one of the charging stations as an example, Figure 12 shows the iteration of the charging price of charging station No. 10, where the ordinates and the size of the circle represent the charging price and the revenue of the charging station, respectively, which illustrates that the charging price of charging station No. 10 decreases, while the revenues increase with the applied CSBAP.Figure 9
Fitness value iteration.Figure 10
Revenue iteration of charging stations.Figure 11
Standard deviation of revenues.Figure 12
Charging price of charging station No. 10.Figures13 and 14 are the planned charging paths of large-scale EVs before and after using CSBAP. Figures 15 and 16 are the charging prices without and with optimization of CSBAP, where the horizontal coordinates, the ordinates, and the size of the circles represent the number of the charging station, the charging price, and the revenue, respectively. It can be observed that the circles in Figure 16 are more similar in size than circles in Figure 15, which represents that revenues of the charging stations are more balanced with CSBAP without decreasing the total revenues of the charging stations. Figures 17 and 18 are the comparison of the amount of charging EVs at the charging stations without and with optimization of CSBAP, where the horizontal coordinates, the ordinates, and the size of the circles represent the number of the charging station, the charging price, and the charged EV amount in the charging stations, respectively. Figures 19 and 20 are the comparison results of the revenue of charging stations and EV amount between using fixed charging price (i.e., charging price is fixed as 1.75 RMB/kWh) and CSBAP. It is demonstrated from Figures 19 and 20 and Table 10 that, by using CSBAP, charging stations gain more revenues than using the fixed charging price, while the revenues and EV amount of charging stations are more balanced. According to the simulation results, the effectiveness of the proposed CSBAP for charging stations is verified.Figure 13
Planned path before optimization.Figure 14
Planned path after optimization.Figure 15
Charging price without optimization.Figure 16
Charging price with optimization.Figure 17
Charging price without optimization.Figure 18
Charging price with optimization.Figure 19
Comparison of revenue.Figure 20
Comparison of EV amount.Table 10
Comparison between fixed pricing strategy and CSBAP.
Fixed pricing strategyCSBAPRevenue (RMB)85869.2492312.38Standard deviation of revenue between charging stations1258.791020.03Standard deviation of EV amount between charging stations14.6410.73


## 6.1. Comparison between MA, BMA, and Our Proposed EHBMA

MA, BMA, and EHBMA are performed to select nodes to the charging station. The execution time and the traversed node label number of the three algorithms are shown in Table4. It is demonstrated that MA costs the longest time, and EHBMA costs the shortest time. The traversed nodes are marked with different colors in Figures 4–6, where the green points and the blue points represent the nodes which are searched forward and backward, respectively. It can be concluded that BMA traverses fewer nodes than MA, while the proposed EHBMA traverses least nodes than both of MA and BMA.Table 4
Performance comparison of MA, BMA, and EHBMA.
MABMAEHBMAComputation time (s)46.576.280.31Number of the traversed nodes41297133241552Figure 4
Charging path planning by MA.Figure 5
Charging path planning by BMA.Figure 6
Charging path planning by EHBMA.


## 6.2. Single EV Charging Path Planning Simulation

The simulation parameters are set as follows. The charging price is fixed as 1.75 RMB/kWh for all charging stations. The driver preference factors areα=0.6,β=1800,γ=703,andμ=0.02, and the initial locations are randomly selected on the map with initial SOC=20% and E0=70kWh.In Figure7, the red, blue, and green paths are the charging paths to the three preselected charging stations, No. 8, No. 13, and No. 12, respectively. The cost of the paths, as shown in Table 5, is used to calculate the driver’s preference, through which the driving distance, energy consumption, time consumption, and charging fee are considered with a trade-off. Then, the path with the smallest P value is selected, so the green path to charging station No. 12 is the final planned charging path.Figure 7
Charging path planning for single EV.Table 5
Cost of the paths to three charging stations.
Charging station numberDriving distance (km)Time consumption (h)Energy consumption (kWh)Charging fee (RMB)Driver preferenceP813416.5362.1462.17387.80351287.242125407.8772.0020.74585.3059370.2171316814.4982.2312.66188.65875376.958


## 6.3. Large-Scale EVs Charging Path Planning Simulation

In this experiment, 1000 EVs are randomly selected on the map. The simulation parameter settings are as follows. Charging price for all charging stations is set as a constant value, 1.75 RMB/kWh. The charging threshold of EVs is set to SOC = 20%. The battery capacityE0 is randomly initialized between 50kWh and 90kWh, and the driver preference factors are α=0.6,β=1800,γ=703,andμ=0.02.The results of the large-scale EVs’ path planning using EHBMA are shown in Figure8. The total revenues of all charging stations, revenue of each charging station, and EV charging amount of each charging station are listed in Tables 6–8, which demonstrate that the revenues and EV amount between different charging stations are not equal. Therefore, it is necessary to optimize the charging price to maximize the total revenue and balance the revenue of each charging station.Figure 8
Path planning for large-scale EV users.Table 6
Total revenues of charging stations based on large-scale EV path planning.
Total revenues of the charging station (RMB)Standard deviation of revenues for each charging station85878.6351312.150Table 7
Revenue of each charging station.
Number1234567891011Revenue (RMB)5074.944248.564885.474960.574721.401023.803137.471628.303502.232125.781019.49Number1213141516171819202122Revenue (RMB)3438.184818.884983.964698.364623.164821.923160.765060.514831.884310.154802.79Table 8
Charging EV amount of each charging station.
Number1234567891011EV amount5950575855123619412512Number1213141516171819202122EV amount4056585554563659565056


## 6.4. The Simulation of CSBAP

In this experiment, the population of the particle swarm in PSO is set asm=20, and the maximum number of iterations is set as MAX=100.Considering the pricing strategy for the single charging station, the No. 6 charging station is used as a case study. Table9 lists the revenue of the charging station No. 6 when the prices of charging stations are fixed as the same price and the charging price is adjusted by CSBAP. The results show that, after the charging price of the charging station No. 6 is adjusted by CSBAP, more revenue can be obtained than the fixed charging price strategy, since the lower price would attract more EVs to charge. Therefore, the effectiveness of our proposed CSBAP for a single charging station is validated.Table 9
Revenue of the charging station No. 6.
Pricing strategyCharging price (RMB/kWh)RevenueEV amountFixed charging price1.791863.0521CSBAP1.612049.0723As the charging pricing strategy for all charging stations, the simulation conditions are set as follows. The prices of the charging stations are limited to the interval [1.5–2.0] RMB/kWh.m=20, and MAX=100. The fitness function is defined as(20)fit=∑ciCrci−10⋅stdr^ci.Figure9 shows that the value of the fitness function gradually rises and eventually stabilizes with 100 iterations of the charging price. Figure 10 illustrates that, after the iterations of CSBAP, the total revenues of all charging stations gradually increase and eventually stabilize. The different color columns in Figure 10 represent the profits of different charging stations. Figure 11 demonstrates that, after the iterations of CSBAP, the revenue standard deviation of charging stations gradually decreases and eventually stabilizes, indicating that the revenues between charging stations are more balanced than those without optimization. Taking the charging price of one of the charging stations as an example, Figure 12 shows the iteration of the charging price of charging station No. 10, where the ordinates and the size of the circle represent the charging price and the revenue of the charging station, respectively, which illustrates that the charging price of charging station No. 10 decreases, while the revenues increase with the applied CSBAP.Figure 9
Fitness value iteration.Figure 10
Revenue iteration of charging stations.Figure 11
Standard deviation of revenues.Figure 12
Charging price of charging station No. 10.Figures13 and 14 are the planned charging paths of large-scale EVs before and after using CSBAP. Figures 15 and 16 are the charging prices without and with optimization of CSBAP, where the horizontal coordinates, the ordinates, and the size of the circles represent the number of the charging station, the charging price, and the revenue, respectively. It can be observed that the circles in Figure 16 are more similar in size than circles in Figure 15, which represents that revenues of the charging stations are more balanced with CSBAP without decreasing the total revenues of the charging stations. Figures 17 and 18 are the comparison of the amount of charging EVs at the charging stations without and with optimization of CSBAP, where the horizontal coordinates, the ordinates, and the size of the circles represent the number of the charging station, the charging price, and the charged EV amount in the charging stations, respectively. Figures 19 and 20 are the comparison results of the revenue of charging stations and EV amount between using fixed charging price (i.e., charging price is fixed as 1.75 RMB/kWh) and CSBAP. It is demonstrated from Figures 19 and 20 and Table 10 that, by using CSBAP, charging stations gain more revenues than using the fixed charging price, while the revenues and EV amount of charging stations are more balanced. According to the simulation results, the effectiveness of the proposed CSBAP for charging stations is verified.Figure 13
Planned path before optimization.Figure 14
Planned path after optimization.Figure 15
Charging price without optimization.Figure 16
Charging price with optimization.Figure 17
Charging price without optimization.Figure 18
Charging price with optimization.Figure 19
Comparison of revenue.Figure 20
Comparison of EV amount.Table 10
Comparison between fixed pricing strategy and CSBAP.
Fixed pricing strategyCSBAPRevenue (RMB)85869.2492312.38Standard deviation of revenue between charging stations1258.791020.03Standard deviation of EV amount between charging stations14.6410.73


## 7. Conclusion

In this paper, an integrated framework of combining the multiobjective charging path planning method is discussed for EVs and charging station pricing strategy for charging stations. A novel charging path planning algorithm EHBMA is proposed based on bidirectional Martins’ algorithm, considering driving distance, energy consumption, total time consumption, and charging fee. It is verified by simulation experiments that the proposed algorithm can provide more charging paths for EV users and assist EV users to select charging stations and charging path with the driver’s preferences. Furthermore, a novel charging pricing strategy CSBAP is proposed. It is also verified by simulation experiments that the revenues of charging stations can be effectively improved, while the revenues of the charging stations are balanced by using the proposed pricing strategy.In the future, we will study the travel patterns of EVs and how to create user portraits to improve the appropriateness of the recommended charging paths. The potential of combining the market transaction mechanism to determine the charging price of charging stations will be investigated. Moreover, more complex road conditions and driving conditions of EVs should be considered to obtain a more accurate charging path planning model.



---

*Source: 8868617-2021-02-25.xml*