Ordered Electric Vehicles Charging Scheduling Algorithm Based on Bidding in Residential Area

Abstract

With the rise of electric vehicles, the key of electric vehicle charging is how to charge them in residential areas and other closed environments. Addressing this problem is extremely important for avoiding adverse effects on the load and stability of the neighboring grids where multi-user centralized charging takes place. Therefore, we propose a charging dynamic scheduling algorithm based on user bidding. First, we determine the user charging priority according to bidding. Then, we design a resource allocation policy based on game theory, which could assign charge slots for users. Due to users leaving and urgent user needs, we found an alternate principle that can improve the flexibility slot utilization of charging. Simulation results show that the algorithm could meet the priority needs of users with higher charging prices and timely responses to requests. Meanwhile, this algorithm can ensure orderly electric vehicle charging, improve power utilization efficiency, and ease pressure on grid loads.

1. Introduction

In the future, the use of electric vehicles (EVs) in closed areas such as residential areas will be widespread; thus, it is very important to have an effective charging management method for EVs in the neighborhood [1]. The charging process of EVs is orderly controlled according to the characteristic of EVs and the travel law, which can not only reduce the adverse impact of the load of electric power on the stability of power grids caused by the concentrated disorder changing [2,3], but it can also improve the utilization efficiency of the peak power quality [4]. The research shows that the price guidance is an effective method to achieve orderly charge scheduling; the charging demand of the users can be met on the basis of minimizing the energy consumption through price adjustment [5,6,7].

Reference [8] puts forward a kind of charging of battery life strategy that realizes the rapid and flexible charging of batteries and adjusts the battery charged state (state of charge, SOC) according to the temperature and voltage characteristics of lithium iron phosphate batteries. Reference [9] presents a new technique for the smart charging of EVs, which uses a fuzzy logic to control and manage the EV charging process to maximize the electric utility and EV owner benefits. Reference [10] presents a multi-objective optimization algorithm-based coordinated EVs charging strategy, which considers both user-level and system-level benefits simultaneously. Reference [11] presents various strategies for coordinating the charging/discharging of PHEVs (Plug in Hybrid Electric Vehicles) in electric parking with V2G (Vehicle-to-Grid) capability and the aim of increasing parking profits. Reference [12] presents a method through which electric vehicles charge and discharge orderly, containing the unit running cost and effectiveness of power system operation by using the multi-objective optimization genetic algorithm. Reference [13] proposes a globally optimal scheduling scheme and a locally optimal scheduling scheme for EV charging and discharging.

Reference [14] presents a heuristic algorithm for time-sharing tariffs to solve the problem of electric vehicle access. The drawback of this approach is that the formulation of electricity prices lacks flexibility, and the algorithm is limited by the degree of user response. Reference [15] proposes an EV charging management strategy based on the dynamic priority, which takes the current load degree of the grid as the constraint and takes the relaxation time of EVs charging as the prerequisite of the priority to control the charging sequence of EVs. However, this method does not consider the price factors and cannot reflect the differences between users. Reference [16] presents a method for competing charging station resources based on user bids, which can delay the charging demand of the peak period of the grid to the off-peak time. However, the vehicle waiting and queuing problem are not taken into account when there are large numbers of charging vehicles. Reference [17] measures the charging characteristics of EVs in residential areas from many aspects, but the actual scheduling problem is not solved. Reference [18] presents a fast charging queue algorithm for EVs under freeway conditions, but it rarely considers the difference between the factor of user bids and demand urgency, and cannot provide differentiated services for users.

Based on the above analysis, we mainly study the problem of how to adopt the user bidding in the residential area to distinguish the users’ charging requirements and allocate the corresponding charging time slot. Meanwhile, the electric vehicle alternating strategy to enhance the charging flexibility and the utilization of time slots is needed when users leave halfway through the charging time slot or new charging requirements with higher bidding appear. Therefore, our contribution is to present a scheduling algorithm of ordered charging for residential EVs based on users bidding. User charging priority is developed according to the user bidding, and the corresponding charging time slots are allocated for users based on the idea of game competition. Meanwhile, the alternating strategy is designed with the consideration of the halfway leaving of users and new charging requirements with higher bidding during the charging time slot.

The rest of this paper is organized as follows. In Section 2, the charging scenario is described. In Section 3, the mathematical models and calculation methods are described. The algorithm implementation process is described in Section 4. Simulation results are analyzed in Section 5. Section 6 presents the conclusion.

2. Dynamic Charging in Residential Area Based on Queuing and Alternating

We study the charging scheduling strategy in a closed cell environment, as shown in Figure 1. There is a charging parking lot in the community. Each parking space is equipped with a vertical charging pile; the charging control system manages each charge spot. Due to the resource constraints of devices and load control requirements, when more than EVs need to charge centrally, orderly charging scheduling is needed. We present a scheduling algorithm of ordered charging residential electric vehicles to provide charging services in different degrees for different users with different bidding strategies.

The user parks the vehicle in the parking space; then, they connect the vehicle to the charging post and submit the demand based on the real-time electricity price. The requirements submitted by user $\mathrm{i}$ include the charging start time $C{T}_s$, departure time $C{T}_l$, real-time price in each hour during the charging process $E{P}_{it}$, the percentage of the expected electricity when leaving $P{T}_{li}$, and the SOC of EV $P{T}_{si}$. Most of the M electric cars can be charged in the charging stations at the same time.

The bidding charging process is divided into three phases: the prepare phase, the queuing phase, and the charging phase. Charging car users submit the charging demand parameters for the auction side; the charging control system, as the auctioneer, plays a coordination role between the charging demand and the power grid [19]. In the preparation phase, the user considers the factors of price and travel to submit charging needs. In the queuing phase, the control system divides the priority according to the submission parameters, and the highest bidder enters the charging phase. The unsuccessful users’ vehicles in the competition will be in the queuing phase and wait for the next time to re-compete. In the charging phase, one hour is taken as a cycle; a charging slot is allocated according to the priority and resource requirements. The allocation of the time slot resource should meet the different requirements of different users for resource performance [20], guarantee the effectiveness of each user’s price, and improve the utilization of grid resources [21]. This paper calculates and distributes the charging resource competition of multiple users according to the game-bidding model, solving the problem in which multiple charging users compete for limited charging resources.

In the residential environment, the arrival and departure of the user is random. Of course, there is also a need for a flexible recharging system for vehicles. For example, alternate vehicles do not have to wait until the next period when some vehicles leave halfway, alternate vehicles can immediately enter the charging phase; at this time, if the urgent users who have a charging demand arrive, the user does not need to wait. The control system scans the accessed vehicle multiple times during each charge cycle; the user priority will change when an alternating condition occurs. The way of replenishment can effectively improve the resource utilization of the charging station and satisfaction of the users.

3. Problem Modeling

3.1. Priority Determination

The priority group includes a high-priority group ${\theta }_1$ and an ordinary priority group ${\theta }_2$. The highest proportion of the high priority group is $\mathsf{\omega }(0<\mathsf{\omega }<1)$. Assuming that the price of electricity generated by user $i\left(i=1,2,3,\dots ,n\right)$ in the k-th time slot $C{T}_k$ is $E{P}_{ik}$, the initial state is as shown:

$${\theta }_1=\{\varnothing \},{\theta }_2=\left\{1,2,\dots ,\mathrm{n}-1,\mathrm{n}\right\}$$

(1)

After that, let the integer $\tau$ be satisfied:

$$1<\tau \le \lfloor \omega ·n\rfloor .$$

(2)

If

$${\mathrm{EP}}_{mk}\ge \forall E{P}_{ik},i\in {\theta }_2,$$

(3)

then

$$m\in {\theta }_1,m\notin {\theta }_2.$$

(4)

After that, we filter in ${\theta }_1$. In order to reduce the occurrence of short-term replenishment, the priority of EV users that wait to charge for a long time is increased, and the priority of the user who is about to leave at the next charging period is reduced. In ${\theta }_1$, if the expected departure time of user $i$ is satisfied.

$$C{T}_{k-1}<C{T}_l\le C{T}_k$$

(5)

Then, the priority of user $i$ is adjusted to the lowest priority in ${\theta }_1$. In the end, the order of elements in ${\theta }_1$ is the charging priority.

3.2. Replenishment Method

There are two cases of replenishment. The first is that there is a vehicle leaving in the middle of the charging cycle, and the charging resources are spare; the second is that the uncharged vehicle user has a high bid to compete for the charging resource. This type of user is called to subscribe users for the auction. To simplify the problem, assume that there is only one bidding user per replenishment cycle, and the bid should be higher than those of all the other users.

Assume a rechargeable scanning cycle $C{T}_d$ is 15 min. The charging control system scans at the $C{T}_d$ interval during each charging cycle, the scan parameters are the number of cars being charged $\mu$ and the bids of all users $E{P}_{ik}$.

If there is a bidding user, when $\mu <M$, we first calculate the number of spare charges $c=M-\mu$. Then, we select the bidding users and the highest bidding $c-1$ electric car in uncharged cars users $\left[i_1,i_2,\dots ,i_{c-1}\right]$ and replenish them to the charging stage. When $\mu =M$, the charging process of the lowest bidding car will be interrupted. Bidding replacement users and other charging users charge.

If there is no bidding user, when $\mu <M$, the number of free charges is $c=M-\mu$. Then, we select the top $c$ bidders in the uncharged cars $\left[i_1,i_2,\dots ,i_c\right]$, replenishing it as a charging car. When $\mu =M$, we continue the charging of the above-mentioned replenishment cycle.

3.3. Charging Resource Allocation

The allocation of the charging resources takes the time interval $d$ as the interval. The request submitted by the user is $E_{id}=\left[E{P}_{id},H{P}_{id}\right]$, where $E_{id}$ represents the charging requirement of user $i$ in $d$, $E{P}_{id}$ represents the bid of user $i$ in $d$, and $H{P}_{id}$ represents the desired charging time of user $i$ during the $d$ period. The value of $H{P}_{id}$ has the following conditions.

• If the user arrives before $d$ and the submitted departure time is not in $d$, $H{P}_{id}$ is 15 min.
• If the user arrives within $d$, $H{P}_{id}$ is the remaining time within $d$.
• If the user arrives before $d$ and the expected departure time is within $d$, $H{P}_{id}$ is the difference between the user’s starting time $d$ and the expected departure time.

Let the total amount of available charging resources in $d$ be $SU{M}_d$, where $SU{M}_d$ represents the number of electric vehicles that can be charged at the same time. Let $P_{sdmin}$ be the minimum total power that the cell grid can withstand in $d$, and $P_{zdmin}$ is the maximum of the total power used for the other power consumption in $d$. $P_{qdmin}$ is the minimum value of the total power that can be used to charge the car in $d$, and $\beta$ is the available power factor.

$$P_{qdmin}=P_{sdmin}·\beta -P_{zdmax}$$

(6)

Let $P_c$ be the charging power of electric vehicles, in this article, $P_c=7kW$. Then,

$$SU{M}_d=\{\begin{array}{c}\frac{P_{qdmin}}{P_c},\frac{P_{qdmin}}{P_c}\le M\\ M,\frac{P_{qdmin}}{P_c}>M\end{array}.$$

(7)

For all users in the priority queue ${\theta }_1=\left\{i_1,i_2,,\dots ,i_{\theta },\right\}$, the charging requirements for each user are $E_{id}=\left[E{P}_{id},H{P}_{id}\right]$, and then the distribution mode is as shown.

$$U_i\left(E{P}_{id},H{P}_{id}\right)=\{\begin{array}{c}H{P}_{id},{\displaystyle {\displaystyle \sum }_{i=1}^{\theta }}H{P}_{id}\le SU{M}_d·C{T}_d\\ {\gamma }_{id}·SU{M}_{id}·C{T}_d,{\displaystyle {\displaystyle \sum }_{i=1}^{\theta }}H{P}_{id}>SU{M}_d·C{T}_d\end{array}$$

(8)

where

$${\gamma }_{id}=\frac{E{P}_{id}}{{{\displaystyle \sum }}_{i=1}^{n}E{P}_{id}}.$$

(9)

3.4. Charging Demand Response and User Cost

The demand response degree reflects the user’s satisfaction with a queuing situation during the charging process. Meanwhile, the system also needs to monitor the charging status of each user in real time, define the demand response parameters, and describe the implementation of the user’s charging requirements. It should be noted that lower bid users are more likely to be divided into a low-priority group due to the algorithm taking the user bid as the starting point, resulting in multiple charging cycles that cannot be charged. As a result, users can only raise bids to get charging slots.

The demand response $R_{ti}$ of user $i$ after a charge is calculated as shown in Equation (10):

$$R_{ti}=\frac{t_{ci}}{t_{si}}$$

(10)

where $t_{ci}$ is the sum of the charged time of user $i$ before the calculation, and $t_{si}$ represents the charging time requirement for user $i$ to participate in the auction during the calculation.

Another parameter to measure user satisfaction is user-charging cost. The charging cost of users consists of two parts: charging cost and service cost. The charging cost $F_{Ci}$ means that the user $i$ uses his own bid as the electricity bill for the hour during the charging time and calculates the sum of the electricity bills spent in each charging period by the charging time allocated by the system. The calculation formula of $F_{Ci}$ is as shown in Formula (11).

$$F_{Ci}={\displaystyle \sum }_{k=0}^{24}E{P}_{ik}·T_{ik}$$

(11)

Among them, $E{P}_{it}$ represents the bid of the user for each charging period throughout the day. $T_{it}$ represents the charging time of user $i$ during each charging period.

Service cost refers to the cost of charging resources and system services occupied by users in the process of a charging parking lot. The service cost $E{P}_{it}$ is related to the user residence time. The formula for calculating $F_{Si}$ is shown in Formula (12).

$$F_{Si}=\eta ·T_{Fi}$$

(12)

Among them, $\eta$ denotes the unit price of service charge and $T_{Fi}$ denotes the total residence time of user $i$.

The formula for calculating the total charge cost $F_i$ of user $i$ is shown in Formula (13).

$$F_i=F_{Ci}+F_{Si}$$

(13)

4. Priority-Based Dynamic Charging Queuing Recursive Compensation Algorithm

This paper proposes an auction-based adaptive charging scheduling algorithm for residential electric vehicles. The algorithm performs updates before the start of each charging cycle. During the execution of the algorithm, three parts should be noted.

4.1. Priority Group Partition

Firstly, all users submitting bids in this charging cycle are selected. According to the selection ratio u, users are divided into a high-priority group and ordinary priority group. At the same time, the time conditions of high priority users are detected, and if they are about to leave in this cycle, their priority will be reduced.

4.2. Judging Whether the Recursive Complement Condition Is Satisfied

Replenishment conditions are divided into two categories. The first category is whether there is a bidding user; if it appears, the bidding user is allowed to enter the charging state in real time and interrupt the charging status of the lowest bidding user among the previously charged users. The second category is whether to reach the replenishment scan time; each charge cycle contains three replenishment scan times. If the recurring scan time is reached, the priority group needs to be re-prioritized.

4.3. Charging Time Slot Calculation and Allocation

After the priority is determined, the charging slot allocation is performed. The total charging time is obtained by calculating the weight based on the user’s bid. The charging post completes charging.

The algorithm is summarized as follows in Algorithm 1.

Algorithm 1. Priority-based dynamic charging queuing recursive compensation algorithm.

Step1: Import parameters and initialize the algorithm; Step2: Based on the given Formulas (1)–(5), the high-priority group and the ordinary priority group are determined; Step3: According to the two conditions, the bidding supplier can be judged. Condition 1: There are vehicles leaving in the middle of the charging cycle, and the charging resources are free. Conditions 2: The users of unloaded vehicles bid high to compete for charging resources; Step4: It is judged whether there is a bidding user; the number of spare charging slots is calculated, and the bidding user is replenished to the charging stage according to different conditions; Step5: Calculate the total amount of available charging resources. The allocation method is calculated according to Formula (8) for all users in the priority queue according to the charging requirements of each user.

The algorithm flow chart is shown in Figure 2.

5. Simulation Results

5.1. User Charging Demand Allocation

The simulation uses a rechargeable battery with a capacity of 35 kWh. The power of the users is constant at each charge, and the proportion of users in the high-priority group is 0.5. To simplify the problem, let the maximum number of simultaneous charging stations be three, the user charging requirements are counted; these are shown in

Table 1. User charge vehicle demand information. SOC: state of charge.

Users	Charging Starting Time	Departure Time	SOC	Percentage of Expected Battery Energy When Leaving
1	20:00	The next day 6:00	35%	100%
2	17:00	The next day 8:00	45%	100%
3	18:15	The next day 7:30	25%	100%
4	19:00	The next day 8:00	20%	100%
5	20:20	The next day 7:00	40%	100%
6	24:00	The next day 9:00	50%	100%

.

The user’s bid for each charging period is shown in Figure 3. The allocation results of the charging resources at 19:00–20:00 are shown in Figure 4. User 2, User 3, and User 4 have a higher bid, which is a high-priority group of users. During the charging period, there is no alternating in the scanning cycle; therefore, in the charging period, the total charge time of User 2 is 35 min, the total charge time of User 3 is 41 min, and the total charge time of User 4 is 43 min. The priority is divided according to the bid of three users, and the charging resources are allocated in turn.

The allocation result of the charge resource at 20:00–21:00 is shown in Figure 5. User 2, User 3, and User 4 are assigned to the status of high-priority user when the first pay cycle is scanned. Since the charging User 5 arrives at 20:20 and bids the highest price among all the users, the charging user is replaced with User 3, User 4, and User 5. In the end, the total charging time of User 2 is 12 min, the total charging time of User 3 is 41 min, the total charging time of User 4 is 35 min, and the total charging time of User 5 is 29 min.

5.2. Demand Response Degree

The user’s charging time distribution is shown in Figure 6. When the number of users is more, the high-bid users will be given priority, and the demand for low-bid users will delay the response.

As there are more charging users at night, the competition is fierce, so the demand response for each user at 21:00 to 2:00 the next day is calculated, which is shown in Figure 7.

Figure 7 shows the analysis. The bids of User 4, User 5, and User 6 are higher, and their demand response speed is faster. User 2 and User 3 have a higher charge completion before the night comes. The bid of User 1 is lower, and User 1 is not eligible for charging between 12:00 and 0:00.

5.3. User Charging Cost

The total charging cost of users is shown in

Table 2. Charging cost of each charging user.

Users	The Charging Cost/Yuan	The Service Cost/Yuan	The Total Cost/Yuan
1	3.58	0.98	4.56
2	3.30	0.38	3.68
3	5.12	0.64	5.76
4	4.69	0.98	5.67
5	4.36	0.53	4.89
6	2.90	0.40	3.3

. Let $\eta$ = 0.12/hour.

As shown in Table 2, if the user wishes to bid successfully at the peak of the charging period, it is necessary to raise the bid, and the charging cost must be high. Meanwhile, due to the large number of users participating in the competition, the charging time is often compressed by other vehicles, which lead to higher service costs. While charging at the low trough, the bid can be maintained at a low level, and the charging time and service costs will be reduced accordingly. Therefore, selecting to charge at the low trough can reduce costs and improve customer service quality.

6. Conclusions

The statistics show that the charging behaviors usually happen in a relatively concentrated time and the arrival and departure of users are random; therefore, researching the orderly charge of EVs in a cell can improve the service quality of users and the utilization of charging resources. In this paper, we propose an orderly charging scheduling algorithm for residential EVs based on user bidding. The algorithm determines the charging priority according to the user bid and scans periodically; user bids and the charging status of EVs are monitored in real time to adjust the priority. We use the serious game concept to allocate the charging time slot. Simulation results show that the algorithm can disperse the charging requirements of the user, prioritizing meeting the needs of high-bid users. Meanwhile, the algorithm improves the charging responsiveness and the utilization rate of power grids.