key: cord-0058868-mg3x9d2k
authors: Zaidi, Imene; Oulamara, Ammar; Idoumghar, Lhassane; Basset, Michel
title: Optimal Online Electric Vehicle Charging Scheduling in Unbalanced Three-Phase Power System
date: 2020-08-24
journal: Computational Science and Its Applications - ICCSA 2020
DOI: 10.1007/978-3-030-58799-4_7
sha: d63489193f6cb17220e582a476dbaafbb9e28d50
doc_id: 58868
cord_uid: mg3x9d2k

This paper studies the electric vehicle (EV) charging scheduling problem where EV arrive at random unknown instants during the day with different charging demands and departure times. We consider single-phase charging EV in a three-phase charging station designed such that each EV has its own parking space. The objective is to build a real-time schedule that minimizes the total tardiness subject to the technical constraints of the charging station. We consider preemptive as well as non-preemptive EV charging. A mixed-integer linear programming (MILP) model is formulated for the offline problem. To solve the online problem, we propose heuristics based on the priority rule. Further, a local search is implemented to improve the objective value of the preemptive EV charging. Simulation results show that the proposed solving approaches outperform the existing heuristics developed in the literature. Moreover, we show that total tardiness is significantly reduced when preemption is exploited.

The increasing environmental awareness led many governments to establish policies encouraging the adaptation of sustainable and clean energy [14] . Thus, electric vehicles (EV) are seen as promising green technology. In 2018, [6] reported that the worldwide number of EV has surpassed 5.1 million which is double the number of EV in the previous year. Nevertheless, the EV is still less adopted than the internal combustion engine vehicles mostly since battery charging is timeconsuming. On the other hand, a high amount of electrical energy drawn from the power grid is needed to meet EV batteries charging demands, especially for fast charging. An excessive electricity demand caused by EV charging will create an extra significant load affecting the power grid stability. Many researchers concluded that uncoordinated EV charging will result in undesirable peaks in the electrical consumption, increases in power losses and voltage deviation [2, 13] . Moreover, uncontrolled single-phase EV charging in a three-phase distribution network will cause a higher load imbalance between the phases and a significant increase in neutral current [7, 10, 12] . Therefore, optimally scheduling the EV charging demands is needed to mitigate these negative impacts and increase EV drivers' satisfaction. Several research studies have been conducted to tackle the EV charging scheduling problem. As an optimization problem, several objective functions were proposed from economical perspective, such as minimizing the electricity costs [19] as well as from technical perspectives such as minimizing the power losses [2, 8] and voltage deviation [8] in power grid. Ideally, an optimal charging schedule can achieve these objectives more efficiently if the information about future charging demands were available when the schedule is computed. However, the charging station only knows the demand for already arrived EV. Consequently, an online algorithm is needed to solve the real-time charging scheduling problem.

In this paper, we address the online EV charging scheduling presented in [4] . The proposed optimization methods aim to build an online optimal schedule that minimizes the total tardiness of the charging demands while maintaining the physical constraints of the three-phased charging station. Also, our work investigates the impact of relaxing the non-preemption constraint of charging operations.

The remainder of the paper is organized as follows: in Sect. 2, we briefly review the main works on electric vehicle charging problems; Sect. 3 describes the problem considered by detailing the charging station model and formulating the problem as MILP. In Sect. 4, our proposed optimization methods are presented. Section 5 summarizes the simulation results. Conclusion and future works are given in Sect. 6.

One of the major challenges in EV charging scheduling is the uncertainly in their charging patterns. In real-life settings, the number of future demands as well as the information about it is not available in advance. Therefore, multiple online and real-time optimization algorithms were established in the literature to address these issues. [17] proposed a dynamic resource allocation system to determine the charging schedule for EV in parking lots where the arrivals of EV can be random or with an appointment. The objective is to minimize the electricity cost bought by the parking service operator from the power grid. The schedule is calculated at the beginning of each 30 min after updating the EV arrival information and charging statues of arrived EV. [19] proposed a charging scheme on a real-time basis to manage the EV charging and incorporated demand response schemes in the parking station. The proposed charging scheduling scheme is designed for the operator of the parking station. It aims to minimize the electricity cost and maximize the number of EV charged simultaneously at each scheduling period through a maximization scheme. The problem is formulated as a 0-1 integer linear programming problem which was approximated via a modified convex relaxation method. A hierarchical control scheme for EV charging across multiple aggregators was proposed in [18] to minimize the electricity cost and system peak load. Each aggregator's charging curve is first solved at the distribution system operator (DSO) level, followed by the power allocation of each EV using a heuristic algorithm. [11] proposes an online adaptive EV charging scheduling framework for utility companies. The objective of the scheduling is to minimize the total electricity cost of EV charging demands subject to battery demand constraint and distribution grid constraints. A MILP is formulated to tackle this problem. The scheduling optimization is solved at each time slot when it detects new arrivals of EV. Furthermore, a three-phase DC MILP optimization strategy is developed since the first optimization can only be applied in single-line systems.

Our study is concerned with the EV charging scheduling problem in a charging station designed to be installed as a large public parking or a collective garage as it is described in [15] . This station is fed with a three-phase current power source. Thus, there are three conductors, each carries an alternating current of the same frequency and voltage amplitude from the source to the electrical outlets. These conductors are called lines and each line regroups a number of power outlets where EV can be plugged into for charging. This means that each connected EV is considered as a single-phase load. However, two constraints limit the number of outlets that can deliver power simultaneously. The first constraint is related to the maximum power that can be drawn from each line so that system overload can be avoided. The second constraint maintains the load balance between any two lines. In fact, in three phase power system, the load should be distributed equally between the three lines to minimize power losses and improve the system efficiency.

The design adopted for the charging station is based on master-slave architecture. Figure 1 illustrates the design of such architecture. Each slave commend the switching on or off of two power outlets. It also records the arrival time of EV and communicate it to its master. The masters has a user interface where the EV drivers enter their departure time and the desired energy demand. All these data are communicated to the central server where a scheduler of the EV charging demands is implemented.

To simplify the operating model of the charging station, we make the same assumption as in [4, 5] where each EV driver has his own parking place so he can plug his vehicle into the outlet at any time. He also provides the parking duration as well as the charging demand through the user interface. Therefore, there is no queue and the driver does not have to wait before plugging his EV. However, the EV does not necessarily start recharging immediately and once it does, he cannot unplug it from the power outlet before completing its charging according to the charging demand. It is also assumed that the charging rate is constant and it is the same for all the charging outlets.

By controlling the switching on and off of the power outlets, we aim to schedule the charging operations among all the EV plugged in such that the entire charging load in each line does not exceed its capacity. Besides, the maximum imbalanced load between each two lines must be maintained. Since the completion time of each charging operation can exceed the provided departure time, the objective function will be to minimize the total tardiness. The charging scheduling horizon H starts at 00:00 h for 24 h and is divided into regular intervals of τ which is equal to 6 min in our case. Each EV has its own parking space and arrives at the station at random instants. This means that the arrival time, charging time and departure time are prior unknown before the arrival of the EV. As a result, the schedule must be built iteratively. In literature, there are two main strategies to handle this uncertainty: solving the scheduling problem whenever a new EV is connected or at each time slot. We adopt the second strategy since the time slot we defined is relatively small and it prevents the system from collapsing when a lot of EV arrive in a very short period.

As an initial case study, we consider the non-preemptive scheduling as in [4, 5] , where the charging of an EV cannot be interrupted until it completes charging i.e the power outlet that was switched on to deliver power to the EV cannot be switched off before the completion of the charging. Thus, the scheduling problem will be to assign a starting time of charging for each arrived EV. Then, we investigate the case study where preemption is allowed. In this case, the charging of EV can be interrupted and another EV will be charged instead. The amount of energy for a preempted EV charging is not lost. When a preempted charging is afterward resumed, it only needs power for its remaining charging time. Such a recharging strategy is highly recommended in smart charging [9] .

Moreover, the open charge point protocol (OCPP) currently integrates these operations without human intervention [16] .

We first formulate the offline problem as a mixed-integer linear problem (MILP). The indices, parameters, and decision variables are described as follow:

Indexes and Sets. The number of lines L = 3. There are N power outlets in the three lines indexed as follow:

-n 3 outlets in line L 3 are indexed n 1 + n 2 + 1, . . . , n 1 + n 2 + n 3 = N . 

-Objective: minimize the total tardiness

Constraints 1 ensure that EV i charge to its desired charging time p i after its arrival time r i .

Constraints (2) calculate the tardiness of charging EV i.

Constraints (3) ensure the non-preemption of charging in case of nonpreemptive scheduling.

Constraints (4), (5) and (6) calculate the number of EV that are charging at the same time at time slot t in lines 1, 2 and 3 respectively.

Constraints (7) are related to the maximum power that can be drawn from each line.Ñ restricts the number of EV that can be charging simultaneously in each line. Since each outlet delivers power at the same constant rate, the power delivered by each line can be expressed by the number of active outlets.

Constraints (8) and (9) establish the maximum imbalance between any two lines such as the difference between the numbers of EV in any two lines does not exceed ΔÑ with Δ ∈ [0, 1].

Although the MILP model has been developed, finding the optimal schedule with an exact method cannot be done in polynomial time. In the simple case where we have only one line, the problem is equivalent to scheduling jobs on parallel machine P |r i | i T i following the α|β|γ notation [3] which is NP-Hard. Furthermore, the problem of EV charging scheduling is a dynamic and real-time optimization problem that requires an online high-speed optimization method. Hence, we propose a heuristic to solve the preemptive charging scheduling problem. The heuristic is based on the prtt (Priority Rule for Total Tardiness criterion) dispatching rule used in [1] . To solve the preemptive problem, the same dispatching rule is used. Additionally, we try to improve results by applying a local search procedure. (7), (8) and (9); for each EV i in the first N' EV in I prtt do Set the starting time of the EV to t if it doesn't beak the constraints (7), (8 and (9) for the next time slots ie. |N t j + 1 − N t k | ≤ ΔN for t from t to t + p i , k = 1, 2, 3k = j if the EV i is assigned, update N t j for the next time slots t starting from t to t + p i ; Calculate the tardiness of the assigned job

if the assignment breaks a previous balance constraint redo the time slot t; end end end return T i

Heuristics based on priority dispatching rules have been widely used in the literature to find near-optimal solutions for NP-Hard scheduling problems since they are simple methods and requires less computation time than sophisticated meta-heuristics. This makes them adequate for real-time and dynamic problems. We adapt the prtt rule proposed in [1] to the EV scheduling problem presented in previous section. The prtt of a charging operation i at time t is defined by:

The charging operations are afterward scheduled at each step in ascending order of their prtt values. Since the schedule is built at each time slot considering only the ready EV (i.e r i ≤ t) without information on the future arrivals, the term max(r i , t) will always be equal to t. As a result a prtt of EV i is calculated as following:

Once an EV starts charging, no interruption is allowed until completion time.

Thus, the objective is to assign a starting time st i for each EV without breaking the constraints (7), (8) and (9). The pseudo-code of the non preemptive charging scheduling is shown in Algorithm 1. At each time slot, for each line, the prtt of ready and not assigned EV are calculated using the equation (11) and they are ordered in increasing order. Then, we calculate N the number of EV that can be added to the schedule at time t in line j without breaking the constraints (7), (8) and (9). The value of N can be obtained by:

The starting time of the first N EV that won't break the constraints (7), (8) and (9) in the next time slots is assigned to t. We improve the assignments of EV at the end of each time slot in case that an assignment of job breaks a previous imbalance constraint. This happens when the assignment of an EV i in line j to a starting time t verify that the assignment of another EV i in line k won't break the imbalance constraints (8) and (9) at time t.

In this case, we redo the scheduling for the current time slot t to assign this EV.

Allowing preemption in scheduling problems is a commonly used relaxation to make the problem easier to solve. Especially in our case where the schedule is built iteratively which makes the decisions of charging some EV at a given time unchangeable even if another EV with higher priority to charge arrives. A high priority EV charging has a smaller prtt value at a given time. Furthermore, preemptive charging is allowed with the new generation of power outlets that use OCPP protocol in which charging service operators can orchestrate the charging of EV.

Heuristic. Unlike the non-preemptive scheduling heuristic proposed, we schedule the charging of the arrived EV at the current time slot only. No charging schedule is built for the next time slots. We calculate the prtt of already and unfinished charging operations at the beginning of each time slot. Then, we schedule the charging operations with smaller prtt values that verify the constraints (7), (8) and (9) for this time slot only. We modify the prtt function to take into account only the remaining charging time of an EV instead of the whole charging time. The pseudo-code of the preemptive charging scheduling is shown in Algorithm 2. (7), (8) and (9) At each time slot t, a partial schedule is built using the prtt based heuristic. At this time, we schedule the arrived EV in the time horizon H allowing preemption. Then, a hill-climbing strategy is used to improve the partial schedule. Although this procedure can improve the current partial schedule at the considered time t, it doesn't necessarily improve the whole final schedule. Given that we are in a real-time setting, we can only change the scheduling of EV at the next time slots. Changes cannot be made for previous time slots t such t < t.

The fundamental part of any local search method is the neighborhood structure. A neighbor is generated by moving a charging operation from a time slot to another time slot. We consider moves that only can improve the current partial schedule. Since the problem is constrained, we have to maintain the feasibility of the schedule each time we need to move a charging operation.

For the description of the neighbor generation moves, we call a time slot t a "source" if we can remove a charging operation from it without breaking the balance constraint (8) and (9) . While a time slot t is called a "target" if adding a charging operation at t doesn't exceed its capacity N and doesn't break constraints (8) and (9) .

Shift right: a neighbor in shift right is generated by moving a random a charging operation of an EV i in a selected line j from a random source time slot t 1 to a random target time t 2 , t 2 > t 1 . Since we consider only moves that can improve a partial schedule, t 2 should not be greater than its departure time t 2 ≤ d i . We guide the search by shifting the charging operations that have a high prtt first so it can be replaced by other charging operations with lower prtt.

Shift left: a neighbor in shift left is generated by moving a charging operation of an EV i in a selected line j from a random source time slot t 1 to a random target time t 2 < t 1 such that t 2 ≥ r i . A variant of shift left is implemented considering the tardy EV (T j > 0). Thus, we shift left the charging operation at its completion time slot.

Shift right on three lines: a neighbor in shift right on 3 lines is generated by moving three random charging operations i 1 , i 2 , i 3 from each line j = 1, 2, 3 from a random time slot t 1 to a random time t 2 with t 2 > t 1 and N t2 j +1 ≤ N . By moving a charging operation per line, we make sure that the balance constraints (8) and (9) are maintained.

Shift left on three lines: a neighbor in shift left on 3 lines is generated by moving three random charging operations i 1 , i 2 , i 3 of each line j = 1, 2, 3 at a random time slot t 1 to a random time t 2 with t 2 < t 1 , N t2 j + 1 ≤ N and t 2 ≤ min(r i1 , r i2 , r i3 ).

A local search algorithm starts by initializing an empty solution. A solution S is a feasible partial schedule that describes the set of charging operation scheduled in any line at each time slot t ∈ H. Then, at each time slot t, for each line j, a partial solution S is built by scheduling preemptively the charging operation of arrived EV according to their prtt values in the time slots t such t ≥ t. A shift right move is considered when we have a charging operation of an EV i that has a lower prtt value than an already scheduled charging operation at the time slot t . After scheduling the charging operations in each line, we start exploring the neighborhood of the solution S. A neighbor solution S is generated using one of the moves described before. S will replace S if the total tardiness of S is less or equal of the total tardiness of S. Since we are in real-time setting, the stopping criterion will be either a given limited time that doesn't exceed τ the length of a time slot or that we cannot generate new solutions using one of the moves. In this section, we evaluate the performance of the proposed methods. We consider the benchmarks proposed in [4] . There are a total number of 180 power outlets in the charging station in which 60 outlets are connected to each line. The arrival, charging demands and departure times are generated following normal distributions with different means and deviations that model the EV charging patterns. Three different scenarios are considered where 60 instances are generated for each scenario. In each instance, 180 EV arrive at the station on a time horizon of 24 h. There are two types of instances according to how the EV are distributed between the three lines. In the first type instances, the EV are distributed uniformly: 60 EV arrive at each line along the day. In the second type instances, 60%, 30% and 10% of EV arrive at the fist, second and third line respectively. This makes the imbalance constraints harder to solve. The instances of the first scenario are generated to represent a normal weekday. The instances of the second scenario are obtained by increasing the arrival rate of EV in a short period of time with different charging and departure times. This makes the charging demands exceed the charging station capacity for these periods. In the third scenario, the instances are generated as in the second scenario but with tighter departure times which makes it the hardest scenario to solve. Note that the algorithms are implemented in Python 3.7, and run on a CPU Intel Core i5-7440HQ (4 CPUs) operating at 2.8 GHz and 8 GB RAM. Table 1 , Table 2 and Table 3 shows the comparison of results obtained for scenarios 1, 2 and 3 respectively with those obtained in [5] by the heuristic "EV". We refer to the proposed heuristic for non-preemptive charging scheduling by "prtt", by "prtt pmtn" for preemptive one and by "HC pmtn" for the hillclimbing preemptive scheduling. We have 30 instances for each group (Scenario, type). For charging station parameters,Ñ varies between 20, 30 and 40 and Δ varies between 0.2, 0.4, 0.6 and 0.8. The Tardiness is calculated for each instance and then summed up for each group. Then, the decrease (or increase) in the total tardiness of the proposed methods compared to the total tardiness in [5] is calculated as a percentage. The percentage will be a negative number if there was a decrease in total tardiness and positive otherwise.

For the first scenario, the prtt outperforms the heuristic EV in 10 groups out of 24 groups whereas it outperforms the heuristic EV in 12 groups out of 24 for the second scenario and in 18 groups out of 24 in the third scenario. This shows that our heuristic has better objective values scheduling EV that arrive almost at the same time with tighter departure times.

For all scenarios, the prtt pmtn and the HC pmtn always outperform the heuristic EV since scheduling the charging preemptively will allow EV with high priorities that have tighter departure times and smaller charging times to charge instead. Thus, Relaxing the preemption constraints is not redundant and it will have great advantage in minimizing the total tardiness. Comparing the results between the two types of instances, we notice that the decreases in total tardiness in type 1 instances is more important than in type 2 instances. For prtt pmtn, The total tardiness was averagely lower by 36.61% in type 1 instances while it was averagely lower by 7.76% in type 2 instances. For HC pmtn, The total tardiness was averagely lower by 44.70% in type 1 instances while it was averagely lower by 7.83% in type 2 instances. About the comparison between the prtt pmtn and the HC pmtn, the tardiness of HC pmtn is better in 39 groups and worse in 33. We can notice that the local search is better in type one instances. Especially in the first and second scenarios and slightly worse in the third scenario. This is because charging operations in the third scenario have tighter departure times so it is harder to find moves that improve the whole schedule total tardiness. However, the overall total tardiness was averagely reduced by 26.26% using HC pmtn whereas it was reduced by 22.2% using prtt pmtn. 

In this paper, we proposed heuristics and a local search procedure to solve the online charging scheduling problem while maintaining the balance in the three phases system. We first formulate the offline problem as MILP model. To solve the problem in a real-time setting, we proposed a new heuristic based on prtt dispatching rule. Simulation results show that our heuristic outperforms other heuristics for most instances. Moreover, the computation time is relatively negligible which is suitable for real-time scheduling. Also, the effectiveness of preemptive scheduling in reducing the total tardiness is shown through the experimental results.

Future works may involve more realistic objectives as maximizing the delivered charging power between the EV arrival and departure times and minimizing the charging electricity bills paid by the charging station.

Some new efficient methods to solve the n/1/ri/ Ti scheduling problem

The impact of charging plug-in hybrid electric vehicles on a residential distribution grid

Optimization and approximation in deterministic sequencing and scheduling: a survey

Dynamic scheduling of electric vehicle charging under limited power and phase balance constraints

Electric vehicle charging under power and balance constraints as dynamic scheduling

IEA: Global EV Outlook 2019: scaling up the transition to electric mobility

Method to assess the powerqualityimpact of plug-in electric vehicles

Centralized charging strategy and scheduling algorithm for electric vehicles under a battery swapping scenario

Estimating the benefits of electric vehicle smart charging at non-residential locations: a data-driven approach

A review of the harmonic and unbalance effects in electrical distribution networks due to EV charging

Adaptive electric vehicle charging coordination on distribution network

Distribution transformer loading in unbalanced three-phase residential networks with random charging of plug-in electric vehicles

Assessment of the impact of plug-in electric vehicles on distribution networks

How policy measures succeeded to promote electric mobility -worldwide review and outlook

Sistema inteligente de recarga de vehículos eléctricos: diseño y operación

Deployment of secure EV charging system using open charge point protocol

Dynamic resource allocation for parking lot electric vehicle recharging using heuristic fuzzy particle swarm optimization algorithm

Coordination of PEVS charging across multiple aggregators

A real-time charging scheme for demand response in electric vehicle parking station