1. Introduction

Electric Vehicle (EV) is a promising solution to future green transportation needs due to its economic and environmental benefits, such as fuel economy, reduction of petroleum consumption, and reduction of environmental pollution ^[1,2]. According to the US Environmental Protection Agency ^[3], a typical EV can transform about $59\%$ to $62\%$ of the electrical energy to power, while conventional gasoline vehicles can only transform about $17\%$ to $21\%$ of the energy stored in gasoline to power. Moreover, it is well known that fossil fuel energy sources are becoming more and more scarce. EVs help us mitigate this problem by utilizing green energy sources via smart grids, such as wind power, solar energy, hydroelectric energy, ocean energy, etc. In addition, the adoption of EVs could help reduce the global emission of carbon dioxide ($\text{CO}_{2}$) in half by 2050 as predicted in ^[1], which will significantly mitigate the environmental pollution.

In this work, we study the charging problem for EVs. Currently, there are mainly three methods of charging EVs: battery swapping, residential^* charging, and public^† charging. Here, we focus on the public charging scenario, where the total power demand will cause an additional load on the power grid that might seriously affect the grid stability when each EV is charged at a fixed high charging speed and the number of EVs is large. Several studies have shown that the current power grid infrastructure might not be able to support a large number of EVs being charged simultaneously ^[5,6,7,8]. On the other hand, according to the International Energy Agency ^[1], the adoption of electric vehicles will increase exponentially from 2010 to 2050, achieving an annual global sale of 106 million EVs. The vehicle industry also predicts a global adoption of 20 million EVs by the end of 2020 ^[7], which will increase the power load to approximately 60~GW when all EVs are charged at the same time even at a slow charging speed (e.g., 3 kW/h ^[9]). Therefore, it is important to take into account the power overloading issues when designing the EV charging strategies.

^* Each household owns a private station to charge the owner's vehicle.

^† Each public facility owns multiple charging machines to serve a large number of EVs.

Two types of EV charging solutions with power control have been studied in past years based on the mode of charging station operation: offline EV charging (the station knows the present and future charging information, say, through a reservation system) and online EV charging (the station knows only the present charging information). Many studies have been conducted to analyze the EV charging problems in residential environments for both offline ^{[10,11,12,13]} and online ^{[14,15,16,17,18]} solutions. In contrast to residential charging, public charging can serve EV customers in more flexible places and provide faster charging services. The authors in ^[19,20] studied the offline EV charging problem in a public environment. Due to the difficulty of collecting charging information in advance in the public domain, several works have been conducted to study the online EV charging problem in public environments ^[21,22,23].

Note that all the works in ^[10,23] consider EV charging scenarios with a sufficient number of charging machines to satisfy the charging requests of all customers. However, as aforementioned, the number of EVs will increase drastically in the next few years, which shows the importance of developing scheduling strategies to accommodate more EVs and better utilize the charging station resources.

The general scheduling problem in multiple-machine scenarios has been studied during the past decades ^[24,25,26]. For the offline EV charging-scheduling problem, the authors in ^[27] presented a two-stage cost minimization framework that optimizes the power allocation, the energy price, and the EV scheduling. The presented framework minimizes the power losses and voltage deviations at the first stage and the cost of users at the second stage. In ^[28], an EV charging mechanism was proposed to optimize the EV scheduling in order to reduce the total charging time. They formulated this problem as an integer programming (IP) problem that is proved to be NP-complete. Two heuristic algorithms were proposed: the Earliest Start Time (EST) algorithm and the Earliest Finish Time (EFT) algorithm. Also, several approaches have been developed to study the online EV charging-scheduling problem ^[29,30,31]. The authors in ^[29,30] presented some online charging scheduling mechanisms to maximize the unified profit of the system in single-machine and multiple-machine scenarios. In ^[29,30], an online charging strategy was proposed to schedule EV charging among multiple charging machines and allocate power to the EVs in order to minimize the time-averaged electricity cost.

It is also worth noticing that the works in ^[10,31] aim to provide a full-charge service to their customers. However, under large-scale scenarios, if the station must fully charge each EV, the high power demand and charging facility requirements might negatively impact the profit of the operator. In this work, we introduce the concept of user satisfaction factor control. The main idea is to adjust the fulfilled percentage of the charging target for each user in order to strike a balance between the profit and the quality of service (QoS).

Our work focuses on maximizing a unified profit for EV charging, while providing a satisfactory service in both offline and online scenarios. Based on our results, we claim that the proposed EV charging strategies not only increase the station profit, but also address the issues of power overloading and charging station shortage.

The main contributions of this study are summarized as follows:

• A profit maximization framework for charging is proposed, which jointly schedules EVs, allocates power, and adjusts the user satisfaction factor, under peak power and charging facility constraints. It is shown that the profit maximization problem is NP-complete in both offline and online scenarios.

• An efficient two-stage charging strategy is proposed to efficiently solve the profit maximization problem for each charging scenario.

• The computational complexity is analyzed for both offline and online algorithms, where it shows that the greedy scheduling algorithm outperforms the linear programming (LP) relaxation scheduling algorithm in terms of computational time by slightly sacrificing the overall profit.

• A competitive analysis for the online two-stage charging algorithm is provided. The lower bound of competitive ratio is derived in terms of the unified profit for a special case.

• Simulation results show that the proposed offline and online two-stage LP and greedy strategies provide promising results with respect to the unified profit, the computational time, the user satisfaction factor, the power consumption, and the competitive ratio.

The rest of the paper is organized as follows. In Section 2.1, we describe the system model. In Section 2.2, we present the profit maximization framework under the offline charging setup and introduce the offline two-stage charging strategy. Similarly, we study the online charging setup and introduce an online two-stage charging strategy and analyze its properties in Section 2.3. In addition, we provide a competitive ratio analysis to analyze the proposed online two-stage charging algorithms. In Section 3, we present simulation results to illustrate the performance of the proposed offline and online two-stage charging strategies. Finally, we summarize the main results and contributions, and discuss some promising future research directions in Section 4.

---

2. Methodology

---

2.1. System model

Suppose that the EV charging operator owns $C$ charging machines that each operates in a time-slotted fashion. During the day, a total of $N$ vehicles arrive at the facility, and are accommodated in the station's parking lots, where each lot has a plug connectable to an arbitrary charging machine through a switching bar system, as shown in Figure 1.

We consider a finite time horizon (e.g. $24$ hours) that contains $T$ time slots. For each EV $i$, let the charging job be described by the arrival time $r_i\in[1, T]$, the departure time $d_i\in[1, T]$, and the required energy $w_i$, where $r_i < d_i\leq T$. The charging period of each EV is denoted by $T_i=[r_i, d_i]$ and its length is given by $\vert T_i\vert=d_i-r_i+1$.

---

2.2. Offline EV charging-scheduling problem

In the offline charging scenario, we assume the station is equipped with an web-based reservation system such that every EV owner can book both the parking lot and charging needs (i.e., $[r_i, d_i]$ and $w_i$). The station utilizes the above information to design the charging strategy to obtain the maximum profit.

In the offline EV charging-scheduling problem the goal is to maximize the unified overall profit for the charging station by jointly optimizing over the EV scheduling, the charging power, and the user satisfaction factor that is defined as the percentage of charging given the desired target energy $w_i$. The scheduling of EVs at time $t$ is represented by $X^t=\{x_{i, j}^t\}$, where $1\leq i\leq N$, $1\leq j\leq C$, and $x_{i, j}^t$ is given by

$x_{ij}^t = \left\{ {\begin{array}{*{20}{l}} {1, \;\;\;\;\;\;{\rm{if}}\;{\rm{the}}\;{i^{th}}\;{\rm{EV}}\;{\rm{is}}\;{\rm{assigned}}\;{\rm{to}}\;{\rm{the}}\;{j^{th}}\;{\rm{charging}}\;{\rm{machine}}\;{\rm{at}}\;{\rm{time}}\;t, }\\ {0, \;\;\;\;\;\;\;\;{\rm{otherwise}}{\rm{.}}} \end{array}} \right.$

Then, the overall scheduling is denoted by $X=\{X^1, X^2, \ldots, X^T\}$. Similarly, the charging power at time slot $t$ is represented by $P^t=\{p_{i, j}^t\}$, where $p_{i, j}^t$ is the charging power level of the $j^{th}$ machine for the $i^{th}$ EV at time $t$. Here, we assume that the $p_{i, j}^t$ is limited by a safe maximum charging power $p_{\textrm{safe}}$, which is a system constant set by the operator in advance. The overall power allocation is denoted by $P=\{P^1, P^2, \ldots, P^T\}$. Note that we normalize the slot length such that the power allocation vector is also representing the energy charging vector. Now, let $\gamma=\{\gamma_1, \gamma_2, \ldots, \gamma_N\}$ denote the set of user satisfaction factors, at which each vehicle is serviced by the end of the schedule, where $\gamma_i\in[\gamma_{\min}, 1]$ for $1\le i\le N$. Here, we assume that the minimum user satisfaction factor $\gamma_{\min}$ is also a system constant set by the operator in advance.

Next, we define the unified profit function for offline charging, which is formulated as the difference between a linear revenue function and a quadratic cost function in order to make the profit maximization problem economically plausible and computationally tractable ^[32]. Let $\alpha>0$ be the price per unit electrical energy (e.g., ＄/kWh) sold to the customers, and the revenue function is given as

$U(X, P)=\alpha\sum\limits_{t=1}^T\sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} p_{ij}^t x_{ij}^t.$

The operation cost of the station includes two parts:

• The power consumption cost is given by

$\text{$C_2(X, \gamma)$}=\eta\sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} \big(w_{i}-\gamma_{i}w_{i}\big)^2\mathbb{1}_{\left\{\sum\limits_{t=1}^{T}x_{ij}^t\geq 1\right\}},$

where $\beta>0$ is the purchase cost weighting parameter. Note that the quadratic dependence reflects the fact that the per unit cost of power consumption for the operator increases as the total demand increases, which is matching the differential pricing strategy in power market ^[33].

• The second part of operation cost is the satisfaction penalty, which is given by

$\text{$C_2(X, \gamma)$}=\eta\sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} \big(w_{i}-\gamma_{i}w_{i}\big)^2\mathbb{1}_{\left\{\sum\limits_{t=1}^{T}x_{ij}^t\geq 1\right\}},$

where $\eta>0$ is the penalty weighting parameter. The function $C_2(X, \gamma)$ is defined to be the residual sum of the squared discrepancy between the delivered and the desired values.

We assume that $\alpha$, $\beta$, and $\eta$ are constants over time and known by the system in advance. With the notations introduced above, the unified profit of the system is given by:

$F(X, P, \gamma)=\text{$U(X, P)$}-\left[\text{$C_1(X, P)$}+\text{$C_2(X, \gamma)$}\right].$

Thus, the overall offline EV charging-scheduling problem can be formulated as:

$\underset{X, P, \gamma}{\text{maximize}} F(X, P, \gamma)$

(1)

$\text{subject to} \sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} p_{ij}^t x_{ij}^t\leq p_{\max}, t=1, \ldots, T;$

(1.1)

$\gamma_{i}w_i \leq \sum\limits_{t=r_i}^{d_i} p_{ij}^t x_{ij}^t\leq w_i, i=1, \ldots, N, j=1, \ldots, C;$

(1.2)

$\sum\limits_{j=1}^{C}x_{ij}^t\leq 1, i=1, \ldots, N, t=1, \ldots, T;$

(1.3)

$\sum\limits_{i=1}^{N}x_{ij}^t\leq 1, j=1, \ldots, C, t=1, \ldots, T;$

(1.4)

$x_{ij}^t\in \{0, 1\}, i=1, \ldots, N, j=1, \ldots, C, t=1, \ldots, T;$

(1.5)

$0\leq p_{ij}^t\leq p_{\textrm{safe}}, i=1, \ldots, N, j=1, \ldots, C, t=1, \ldots, T;$

(1.6)

$\gamma_{\min}\leq\gamma_{i}\leq1, i=1, \ldots, N.$

(1.7)

Here, (1.1) ensures that the total power allocation at each time slot does not exceed the power limit $p_{\max}$; (1.2) guarantees that every EV will be charged at or above the percentage defined by the satisfaction factor; (1.3) and (1.4) indicate that every single machine can only charge one vehicle at a time and each EV can only be charged by one machine at a time; (1.5) defines the charging machine assignment indicator; (1.6) defines the feasible range for individual $p_{i, j}^t$, which is limited by a safe maximum charging power $p_{\textrm{safe}}$ for EVs; and (1.7) requires the user satisfaction factor to meet a minimum target.

Notice that Problem (1) is a mixed integer linear programming (MILP) problem due to the EV scheduling constraint (1.5). Theorem 2.1 below establishes the complexity of solving Problem (1) in an offline charging scenario.

Theorem 2.1. The EV charging problem (1) is NP-complete.

Proof: To prove a problem is NP-complete, we need to show it is both NP and NP-hard. First, we prove that Problem (1) is NP. Recall that a problem is considered to be NP if the verification process can be done in polynomial time. We assume that we are given some instances and $\it S$ is our certificate. A deterministic algorithm verifies whether each EV $i\in\{1, 2, \ldots, N\}$ is assigned to any charging machine $j\in\{1, 2, \ldots, C\}$. Then, it checks if the total number of vehicles being charged is less than or equal to $C$ and if the total power consumption is less than or equal to $p_{\max}$ at each time slot. Notice that the verification process can be completed in polynomial time $O (NC)$. Therefore, our problem is NP.

Next, consider the special case when the power is uniformly allocated and the user satisfaction factors are set to be equal to 1, which means all EVs must be fully charged. Problem (1) is then reformulated as:

$\underset{X}{\text{maximize}} \sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} \left(\alpha w_i-\beta \frac{w_i^2}{\vert T_i\vert}-2\beta \frac{w_i}{\vert T_i\vert}\sum\limits_{k=1, k\neq i}^{N}\frac{\vert T_{ik}\vert w_k}{\vert T_k\vert}\right)x_{ij}$

(2)

$\text{subject to} \sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} \frac{w_i}{\vert T_i\vert} x_{ij}^t\leq p_{\max}, t=1, \ldots, T;$

(2.1)

$\sum\limits_{j=1}^{C}x_{ij}^t\leq 1, i=1, \ldots, N, t=1, \ldots, T;$

(2.2)

$\sum\limits_{i=1}^{N}x_{ij}^t\leq 1, j=1, \ldots, C, t=1, \ldots, T;$

(2.3)

$x_{ij}^t\in\{0, 1\}, i=1, \ldots, N, j=1, \ldots, C, t=1, \ldots, T,$

(2.4)

where $x_{ij}=\sum\limits_{t=1}^{T}x_{ij}^t$ and $\vert T_{ik}\vert$ is the number of time slots when job $i$ and job $k$ overlap.

Then, we prove that Problem (2) is NP-hard. Notice that Problem (2) can be reduced from the problem of fixed time interval scheduling with parallel machines ^[34,35,36], or the resource allocation problem addressed in ^[37,38,39], which both have been largely studied and proven to be NP-hard. Thus, according to the reducibility principle, we can claim that Problem (2) is at least as "hard" as those problems, which implies it is also NP-hard.

Since Problem (1) contains the combinatorial optimization Problem (2) with fixed power allocation and user satisfaction factor, we can claim that Problem (1) is also NP-hard. Therefore, we conclude that Problem (1) is both NP and NP-hard, which proves its NP-completeness.

The optimal solution to NP-complete problems can be obtained by exhaustive search, but the computational cost is far too high. In Section 2.2.1, we propose an offline two-stage charging strategy to find an efficient suboptimal solution to Problem (1).

---

2.2.1. Offline two-stage charging strategy

As aforementioned, the station might not be able to serve all EVs that require service at each time slot due to the limited number of charging machines. Therefore, the station needs to first determine "whom" it will charge (i.e., a subset of vehicles with a maximum size $C$) at each time slot and then decide "how much" it should charge. Thus, our offline two-stage charging strategy is to first find a schedule for the EVs and then optimize the charging power and user satisfaction factors. Then, it verifies if each EV is charged with at least the minimum user satisfaction factor.

Specifically, the first stage, called Electric Vehicle Scheduling (EVS), is responsible for finding the feasible schedule for the EVs such that the unified profit is maximized given a fixed charging power solution and the desired user satisfaction factors. Based on such a schedule obtained in the first stage, the second stage, called Power and QoS Optimization (PQO), optimizes the power allocation and the user satisfaction factors under the peak power and charging level constraints. Then, the algorithm verifies if every EV is charged with at least $\gamma_{\min}$ of the desired energy target. If not, the EVs with invalid $\gamma_i$'s are rejected and the overall algorithm is re-executed until a feasible solution is found. The final charging solution will be obtained after these steps.

Electric Vehicle Scheduling (EVS)

The goal here is to find a feasible schedule of EVs, which maximizes the unified profit under a fixed set of power allocation and user satisfaction factors. We introduce two algorithms: the offline LP relaxation and greedy scheduling algorithms. Here, we set $p_{ij}^t=\frac{w_i}{\vert T_i\vert}$ and $\gamma_i=1$ for all $i\in\{1, 2, \ldots, N\}$, $j\in\{1, 2, \ldots, C\}$, and $t\in[r_i, d_i]$. This special problem can be formulated as Problem (2).

(a) Offline LP relaxation scheduling algorithm

In this algorithm, the idea is to relax the EV scheduling constraints (2.4) by replacing $x_{ij}^t\in\{0, 1\}$ with a weaker constraint $0\leq x_{ij}^t\leq 1$. The obtained optimal fractional solution to the relaxed LP problem is then rounded using a derandomization algorithm ^[40]. In this work, we obtain the desired integer solution $\widetilde{x}_{ij}^t\in\{0, 1\}$ by rounding the fractional solution $x_{ij}^t$ to the closest integer. This approximation algorithm runs in polynomial time and determines a feasible solution, which is close to the optimal solution. The LP relaxation scheduling problem can be formulated from Problem (2) by letting $0\leq x_{ij}^t\leq 1$. It can be shown that the offline LP relaxation scheduling algorithm guarantees at least $(e-1)/e$ of the optimal solution in the worst-case scenarios ^[41,42,43]. In the following theorem, we analyze the complexity of the proposed scheduling algorithm.

Theorem 2.2. Given a set of $N$ jobs and $C$ machines, the offline LP relaxation scheduling algorithm finds a feasible schedule in $O\left (T\cdot \min\{N, C\}\cdot \left (2N+T+1\right)\right)$ time.

Proof: The algorithm starts by solving the relaxed LP Problem (5). This part needs $O\left (\min\{N, C\}\cdot T\cdot \left (2N+T\right)\right)$ computation times. Here, $\min\{N, C\}\cdot T$ is the number of variables and $\left (2N+T\right)$ is the number of constraints. After the relaxed LP Problem (5) is solved, the algorithm needs to round the fractional solutions to obtain the desired integer solution. Here, the rounding process takes $O\left (\min\{N, C\}\cdot T\right)$ computation times. Finally, the total computational time of the offline LP relaxation scheduling algorithm is $O\left (T\cdot \min\{N, C\}\cdot \left (2N+T+1\right)\right)$.

As shown in Theorem 2.2, finding the exact EV schedule at each time slot to maximize the unified profit is a challenging task, specially in large-scale systems. In the next subsection, we address this problem by proposing an offline greedy scheduling algorithm that decides whether to schedule an EV based on its individual profit and charging time. We will show later that, in contrast to the LP relaxation approach, the computational time of the greedy scheduling algorithm does not increase rapidly with respect to the number of variables, at the cost of sacrificing certain optimality.

(b) Offline greedy scheduling algorithm

The offline greedy scheduling algorithm (see Algorithm 1) schedules the EVs to idle charging machines in a non-increasing order over their individual profits. The algorithm first calculates the individual profit of all users and sorts them into a non-increasing order (i.e., $f_1\geq f_2\geq\ldots\geq f_N$). If two or more EVs have the same individual profit, the algorithm chooses the one with the shortest charging time. Then each job is scheduled based on this order until all the charging machines are occupied. After that, the system has to make the decision whether to accept or decline some new charging requests. The station checks if part of the latest charging job can be processed and chooses the machine that provides the largest profit. If this is not possible, the requested charging job is declined. In ^[44,45], the authors proposed a similar algorithm based on individual profit maximization. Their approach schedules only the non-overlapping jobs with the highest individual profit. But our algorithm is able to schedule part of certain charging jobs, which improves the unified profit. The proposed greedy algorithm guarantees at least 1/2 of the optimal solution in the worst-case scenarios ^[44]. The following theorem derives the computational time of the offline greedy scheduling algorithm.

Theorem 2.3. Given a set of $N$ jobs and $C$ machines, the offline greedy scheduling algorithm finds a feasible schedule in $O\left (N (\log N+C\right))$ time.

Proof: The algorithm starts by calculating the individual profit of each user and then sorting them into a non-increasing order. The process of sorting the $N$ charging jobs takes $O\left (N\log N\right)$ time. Then, the algorithm schedules the sorted jobs one by one to the idle machines. Since the algorithm needs to check if the latest job can be scheduled to any machine, the process of selecting the machine takes $O\left (NC\right)$ time. Therefore, the total computational time of the offline greedy scheduling algorithm is $O\left (N (\log N+C\right))$.

Power and QoS Optimization (PQO)

The goal in this stage is to maximize the unified profit of the system based on the schedule obtained from EVS. Recall that given a schedule $\widetilde{X}$, the unified profit is given by

$F(P, \gamma)=\sum\limits_{t=1}^T\left[\alpha\sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} p_{ij}^t-\beta\left(\sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} p_{ij}^t\right)^{2}\right]-\eta\sum\limits_{j=1}^{C}\sum\limits_{i=1}^{N} \big(w_{i}-\gamma_{i}w_{i}\big)^2.$

Based on the knowledge of future charging requests, we can partition the schedule according to multiple independent groups of EVs based on their arrival and departure times. Here, the EVs from different independent groups are not overlapping in term of their charging times. Those EVs will be in one group if each EV in this group is overlapping with at least another EV in this group. For instance, as shown in Figure 2, we can partition the set of scheduled users $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ into three independent groups $\{1, 2, 3\}$, $\{4, 5, 6\}$, and $\{7, 8, 9\}$.

Let $M$ denote the number of independent groups. For $1\le m\le M$, let $I_m$ be the set of EVs included in the $m^{th}$ group, and $\vert I_m \vert$ be the size of $I_m$. The charging period of the $m^{th}$ group is denoted by $D_m=[\min_{i\in I_m}r_i, \max_{i\in I_m}d_i]$ and its length is given by $\vert D_m\vert=\max_{i\in I_m}d_i-\min_{i\in I_m}r_i+1.$

After grouping, the original problem is divided into multiple subproblems, which can be solved independently by the same technique. Thus, the unified profit for the station is given by the sum of the profits from each group $m$. The optimization problem to find the profit for the $m^{th}$ group can be formulated as:

$\underset{P, \gamma}{\text{maximize}} \sum\limits_{t\in D_m} \left[\alpha\sum_{i\in I_m} p_{ij}^t-\beta\left(\sum_{i\in I_m} p_{ij}^t\right)^{2}\right]-\eta\sum_{i\in I_m} \left(w_{i}-\gamma_{i}w_{i}\right)^{2}$

(3)

$\text{subject to} \sum_{i\in I_m} p_{ij}^t \leq p_{max}, j=1, \ldots, C, m=1, \ldots, M, t\in D_m;$

(3.1)

$\gamma_{i}w_i \leq \sum\limits_{t=r_i}^{d_i} p_{ij}^t \leq w_i, i\in I_m, j=1, \ldots, C, m=1, \ldots, M;$

(3.2)

$0\leq p_{ij}^t\leq p_{\textrm{safe}}, i\in I_m, j=1, \ldots, C, m=1, \ldots, M, t\in D_m;$

(3.3)

$0\leq\gamma_{i}\leq 1, i\in I_m.$

(3.4)

The above problem is a convex quadratic problem, and thus its optimal solutions can be obtained by solving the Karush-Kuhn-Tucker (KKT) conditions ^[46]. For better exposition, let $W_m=\sum\limits_{i\in I_m} w_i$ be the total energy demanded by the $m^{th}$ group of EVs.

Remark 2.1. In order to better understand the structure of the optimal solution for Problem (3), it is worth analyzing the relationship between the achievable profit and $W_m$, which is shown in Figure 3. Let $\text{$R_1$}=\frac{\alpha\vert D_m\vert}{2\beta}$ and $\text{$R_2$}=\frac{1}{2\eta}\left\{2\min\left (|I_m|p_{\textrm{safe}}, ~p_{max}\right)(\vert I_m\vert \beta +\eta \vert D_m\vert)-\alpha \vert I_m\vert \right\}$ for notation simplicity. Then, we observe the following operation regions:

• When $W_m\in[0, R_1)$, the profit increases as $W_m$ increases until its maximum is reached. This region can be viewed as the "low demand" region, where it is anticipated that the station can fully satisfy all EVs in the $m^{th}$ group.

• When $W_m\in[R_1, R_2]$, the profit starts decreasing but remains acceptable.

• When $W_m\in (R_2, \infty)$, the profit decreases fast until it reaches $0$. In this region, the energy demand is too high, which is beyond the capability of the charging station. It will be shown later that in this region, no EV can be fully charged.

In Theorem 2.4 below, we provide the optimal solution to the sum charging power and the user satisfaction factors for a given feasible schedule.

Theorem 2.4. The optimal solution to Problem (3) is given as follows:

• If $0\leq W_m < R_1$, $\gamma_{i}^*=1$ and $\sum_{i\in I_m} {p_{ij}^*}^t=\sum_{i\in I_m}\frac{w_i}{\vert D_m\vert}$.

• If $R_1\leq W_m\leq R_2$, $\gamma_{i}^*=1-\frac{2\beta\sum_{i\in I_m} w_i-\alpha \vert D_m\vert}{2w_i (\vert I_m\vert \beta+\eta \vert D_m\vert)}$ and $\sum_{i\in I_m} {p_{ij}^*}^t=\frac{\alpha \vert I_m\vert +2\eta\sum_{i\in I_m}w_i}{2(\vert I_m\vert \beta+\eta\vert D_m\vert)}.$

• If $W_m>R_2$, $\gamma_{i}^*=1-\frac{\sum_{i\in I_m}w_i-\vert D_m\vert \min\left (|I_m|p_{\textrm{safe}}, ~p_{max}\right)}{ \vert I_m\vert w_i}$ and $\sum_{i\in I_m} {p_{ij}^*}^t=\min\left (|I_m|p_{\textrm{safe}}, ~p_{max}\right).$

As aforementioned, this problem can be solved by standard convex optimization techniques. The detailed proof is presented in Appendix A.

Remark 2.2. We can obtain the following lower and upper bounds of $\gamma^*_i$ from Theorem 2.4.

• If $0\leq W_m < R_1$, then $\gamma^*_i=1$.

• If $R_1\leq W_m\leq R_2$, then $1-\frac{2\beta \min\left (|I_m|p_{\textrm{safe}}, ~p_{max}\right)-\alpha}{2\eta w_i}\leq\gamma^*_i\leq 1$.

• If $W_m>R_2$, then $0\leq\gamma^*_i < 1-\frac{2\beta \min\left (|I_m|p_{\textrm{safe}}, ~p_{max}\right)-\alpha}{2\eta w_i}$.

From the station owner's point of view, the station is able to compute the guaranteed range of user satisfaction factor based on the total energy demand.

Remark 2.3. The optimal sum power $\sum_{i\in I_m} {p_{ij}^*}^t$ is constant over time for all $t\in D_m$. From the KKT conditions given in the Appendix A, we observe that $\sum_{i\in I_m} {p_{ij}^*}^t=\sum_{i\in I_m} \frac{\gamma_{i}^{*}w_i}{\vert D_m\vert}$, where $\gamma_i^*\in[0, 1]$. Notice that the right-hand side of the above equation does not depend on $t$; therefore the sum power at each time slot is constant over time.

Remark 2.4. The optimal power allocation $P^*$ may not be unique. The system of equations to solve the power allocation consists of $\vert I_m\vert+(\max_{i\in I_m}d_i-\min_{i\in I_m}r_i+1)$ equations and $\vert I_m\vert+\sum_{i\in I_m} \left (d_i-r_i\right)$ unknown variables. Since the arrival and departure times satisfy $r_i < d_i$, we have more unknown variables than equations in most cases. This implies that our system of equations is underdetermined, and therefore the optimal power allocation $P^*$ may not be unique.

As aforementioned, after $P^*$ and $\gamma^*$ are obtained, the algorithm verifies if every EV satisfies the condition $\gamma_{i}^*\ge\gamma_{\min}$. If not, the group of EVs with $\gamma_{i}^* < \gamma_{\min}$ are rejected and the algorithm re-executes the first and second stages until either a feasible solution is found.

Next, we consider an online charging setup to address the issue when EVs' charging needs are not available in advance at public stations.

---

2.3. Online EV charging-scheduling problem

In contrast to the offline scenario, in the online charging scenario, the operator learns the charging information on the fly after the EVs are connected to the system. Therefore, the station can only maximize the instantaneous profit by optimizing the charging process based on the available information of the customers currently connected and just arrived. Due to the lack of information about future requests, the online charging strategies are forced to make real-time decisions that may later turn out to be suboptimal. Thus, it is clear that the online charging mechanisms will always perform worse than their offline counterparts, or at the best equal.

Specifically, we consider the scenario when the station only has knowledge about the past and present charging requests. Statistic information about future charging requests is not considered, and therefore the station can only optimize the charging process of the customers currently connected. We propose a deterministic and greedy online charging approach that jointly optimizes the EV scheduling, power allocation, and user satisfaction factors. Let $J_n$ be the set of EVs connected to system when the new EV $n$ arrives at the station, which includes EV $n$. The charging period is denoted by $L_n=[r_n, \max_{k\in J_n} d_k]$. Both $J_n$ and $L_n$ are updated at each arrival time based on the current charging information. The remaining energy requirement is also updated at each period $L_n$ after the arrival of EV $n$, given by $w_{i}^{L_n}=w_{i}-v_{i}^{L_n}$ for all $i\in J_n$, where $v_{i}^{L_n}=\sum\limits_{t=1}^{r_n-1}p_{ij}^{t}$ is the energy already delivered before $r_n$.

Our main goal is to maximize the total profit for the charging station during the period $L_n$ by jointly optimizing over the EV scheduling, the charging power, and the user satisfaction factor, which is now updated as the percentage of charging given the updated desired energy $w_i^{L_n}$. Similar to the offline section, the schedule of all EVs at time $t$ is represented by the matrix $X^t=\{x_{i, j}^t\}$, where $i\in J_n$, $1\leq j\leq C$, and $t\in L_n$.

Then, the scheduling during the charging period $L_n$ is denoted by $X^{L_n}=\{X^t, t\in L_n\}$. Similarly, the charging power at time slot $t$ is represented by $P^t=\{p_{i, j}^t\}$, where $p_{i, j}^t$ is the charging power level of the $j^{th}$ machine for the $i^{th}$ EV at $t\in L_n$. As such, the total power allocation is denoted by $P^{L_n}=\{P^t, t\in L_n\}$. Now, let $\gamma^{L_n}=\{\gamma_1^{L_n}, \gamma_2^{L_n}, \ldots, \gamma_{|J_n|}^{L_n}\}$ denote the set of user satisfaction factors, at which each vehicle is guaranteed to be charged at the end of the period $L_n$, where $\gamma_i^{L_n}\in[0, 1]$ for $i\in J_n$. The overall online EV charging problem for a given charging period $L_n$ is formulated as follows:

$\underset{\gamma^{L_n}, X^{L_n}, P^{L_n}}{\text{maximize}} \sum\limits_{t\in L_n}\left\{\alpha\sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} p_{ij}^t x_{ij}^t-\beta\left(\sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} p_{ij}^t x_{ij}^t\right)^{2}\right\}\nonumber\\ \;\;\;\;\;\;\;-\eta\sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} \left(w_{i}^{L_n}-\gamma_{i}^{L_n}w_{i}^{L_n}\right)^2 \mathbb{1}_{\left\{\sum\limits_{t\in L_n}x_{ij}^t\geq 1\right\}},$

(4)

$\text{subject to} \sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} p_{ij}^t x_{ij}^t\leq p_{\max}, t\in L_n;$

(4.1)

$\gamma_{i}^{L_n}w_{i}^{ L_n}\leq \sum\limits_{t=r_i}^{d_i} p_{ij}^t x_{ij}^t\leq w_{i}^{L_n}, i\in J_n, j=1, \ldots, C;$

(4.2)

$\sum\limits_{j=1}^{C}x_{ij}^t\leq 1, i\in J_n, t\in L_n;$

(4.3)

$\sum\limits_{i\in J_n}x_{ij}^t\leq 1, j=1, \ldots, C, t\in L_n;$

(4.4)

$x_{ij}^t\in \{0, 1\}, i\in J_n, j=1, \ldots, C, t\in L_n;$

(4.5)

$0\leq p_{ij}^t\leq P_{safe}, i\in J_n, j=1, \ldots, C, t\in L_n;$

(4.6)

$\gamma_{\min}\leq\gamma_{i}^{L_n}\leq1, i\in J_n.$

(4.7)

Here, (4.1) ensures that the total power allocation does not exceed the power limit $p_{max}$; (4.2) guarantees that every EV will be charged at or above the minimum user satisfaction factor provided by the station; (4.3) and (4.4) indicate that every single machine can only charge one vehicle at a time and each client can only be assigned to one machine; (4.5) defines the charging machine assignment; (4.6) defines the feasible range for $p_{i, j}^t$; and (4.7) requires the user satisfaction factor to meet a minimum target.

Notice that Problem (4) has the same structure as Problem (1), and it is also an NP-complete problem. Thus, we introduce an online two-stage charging strategy as a suboptimal solution to Problem (4). Our online two-stage charging strategy is to first find a schedule of EVs and then optimize the charging power and user satisfaction factors, each time a new EV arrives at the station.

---

2.3.1. Online two-stage charging strategy

In this scenario, the station also needs to first determine "whom" it will charge (i.e., a subset of vehicles with a maximum size $C$) and then decide "how much" it should charge at each time slot with the operation window $L_n$. In contrast to the offline case, the online EV charging strategy is executed whenever a new customer arrives at the charging facility. Specifically, every time a new EV arrives at the station, our online two-stage charging strategy first finds a schedule for the EVs currently connected to the system and then optimizes the charging power and user satisfaction factors. Afterwards, the algorithm verifies if every EV could be charged with at least $\gamma_{\min}$. If not, the new EV is rejected immediately and the previous charging strategy is resumed.

Electric Vehicle Scheduling (EVS)

The goal here is to find the feasible schedule of EVs that maximizes the instantaneous profit within $L_n$. Similar to the offline case, we introduce two algorithms: the online LP relaxation and greedy scheduling algorithms. We set $p_{ij}^t=\frac{w_i^{L_n}}{\vert T_i\vert}$ and $\gamma_i^{L_n}=1$. This problem can be formulated as:

$\underset{X^{L_n}}{\text{maximize}} \sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} \left(\alpha w_i^{L_n}-\beta \frac{\left(w_i^{L_n}\right)^2}{\vert T_i\vert}-2\beta \frac{w_i^{L_n}}{\vert T_i\vert}\sum\limits_{k\in J_n, k\neq i}\frac{\vert T_{ik}\vert w_k^{L_n}}{\vert T_k\vert}\right)x_{ij}$

(5)

$\text{subject to} \sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} \frac{w_{i}^{L_n}}{\vert T_i\vert} x_{ij}^t\leq p_{\max}, t\in L_n;$

(5.1)

$\sum\limits_{j=1}^{C}x_{ij}^t\leq 1, i\in J_n, t\in L_n;$

(5.2)

$\sum\limits_{i\in J_n}x_{ij}^t\leq 1, j=1, \ldots, C, t\in L_n;$

(5.3)

$x_{ij}^t\in\{0, 1\}, i\in J_n, j=1, \ldots, C, t\in L_n.$

(5.4)

where $x_{ij}=\sum\limits_{t\in L_n}x_{ij}^t$ and $\vert T_{ik}\vert$ is the number of timeslots in $L_n$ when job $i$ and job $k$ overlap.

(a) Online LP relaxation scheduling algorithm

Similar to the approach presented in the offline case, the idea is to replace $x_{ij}^t\in\{0, 1\}$ with a weaker constraint $0\leq x_{ij}^t\leq 1$, for all $t\in L_n$. The obtained optimal fractional solution to the relaxed LP problem is then rounded using the same rounding approach to obtain the desired integer solution $\widetilde{x}_{ij}^t\in\{0, 1\}$. This online LP relaxation scheduling algorithm is executed every time when a new EV arrives at the station. It can be shown that this algorithm also runs in polynomial time and guarantees at least $(e-1)/e$ of the optimal solution in the worst-case scenario. In the following theorem, we show the complexity of the online LP relaxation algorithm.

Theorem 2.5. Given a set of $J_n$ jobs and $C$ machines at the arrival time $r_n$, the online LP relaxation scheduling algorithm finds a feasible schedule in approximately $O\left (N\cdot T\cdot \min\{N, C\}\cdot \left (2N+T+1\right)\right)$ time, where $N=\max_{n} |J_n|$.

Proof: The proof is similar to that for Theorem 2.2, thus omitted.

Similar to the offline charging scenario, we also propose an online greedy scheduling algorithm to reduce the computational cost at the expense of decreasing certain optimality.

(b) Online greedy scheduling algorithm

The online greedy scheduling algorithm schedules the EVs to idle machines in a non-decreasing order over their arrivals. If two or more EVs arrive at the same time, the algorithm chooses the one with the shortest charging time. Once all machines are occupied, the algorithm needs to decide whether to accept or decline the new EV.

The online greedy scheduling algorithm (see Algorithm 2) first checks if there is any charging machine idle to schedule the new EV $n$. If not, the algorithm calculates the individual profit $f_k$ of all EVs $k < n$ already connected to stations and the individual profit $f_n$ of EV $n$. Then, the algorithm needs to immediately make the decision whether to accept or decline EV $n$. If $f_n\geq f_k$ for any EV $k < n$, the station stops charging EV $k$ and schedule EV $n$ to the relieved charging machine. Moreover, if $f_n < f_k$ and $d_n>d_k$ for any EV $k < n$, the station starts charging EV $n$ after EV $k$ is charged. Finally, if none of the above conditions are satisfied, the EV $n$ is declined immediately. The following theorem derives the computational time of the online greedy scheduling algorithm.

Theorem 2.6. Given a set of $J_n$ jobs and $C$ machines at the arrival time $r_n$, the online greedy scheduling algorithm finds a feasible schedule in $O\left (N^2\left (\log N+C\right)\right)$ time, where $N=\max_n |J_n|$.

Proof: Here, we proved this theorem using the same approach presented in Theorem 2.3, therefore it is omitted.

Power and QoS Optimization (PQO)

The goal in this step is to maximize the profit of the station operator based on the schedule obtained from the previous stage. The optimization problem to find the maximum instantaneous profit for the station can be formulated as:

$\underset{P^{L_n}, \gamma^{L_n}}{\text{maximize}} \sum\limits_{t\in L_n}\left\{\alpha\sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} p_{ij}^t-\beta\left(\sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} p_{ij}^t\right)^{2}\right\}-\eta\sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} \left(w_{i}^{L_n}-\gamma_{i}^{L_n}w_{i}^{L_n}\right)^2$

(6)

$\text{subject to} \sum\limits_{j=1}^{C}\sum\limits_{i\in J_n} p_{ij}^t\leq p_{\max}, t\in L_n;$

(6.1)

$\gamma_{i}^{L_n}w_{i}^{L_n}\leq \sum\limits_{t=r_i}^{d_i} p_{ij}^t\leq w_{i}^{L_n}, i\in J_n, j=1, \ldots, C;$

(6.2)

$0\leq p_{ij}^t\leq p_{\textrm{safe}}, i\in J_n, j=1, \ldots, C, t\in L_n;$

(6.3)

$0\leq\gamma_{i}^{L_n}\leq1, i\in J_n, t\in L_n.$

(6.4)

Similar to the offline case, the above problem is a convex quadratic problem, and thus its optimal solutions can be obtained by solving the KKT conditions. Let the total energy demanded by the EVs $i\in J_n$ during the period $L_n$ be defined as $W_{L_n}=\sum\limits_{i\in J_n} w_{i}^{L_n}$. Let $\text{$R_1^{L_n}$}=\frac{\alpha\vert L_n\vert}{2\beta}$ and $\text{$R_2^{L_n}$}=\frac{1}{2\eta}\left[2\min\left (|J_n|p_{\textrm{safe}}, ~p_{max}\right)(\vert J_n\vert \beta +\eta \vert L_n\vert)-\alpha \vert J_n\vert \right]$, where $R_1^{L_n}$ and $R_2^{L_n}$ are updated at every arrival time. We can provide the same operation regions as illustrated in Figure 3 for a given charging period $L_n$.

In Theorem 2.7, we provide the optimal solution to the sum of power and the user satisfaction factors for a given feasible schedule at $t\in L_n$.

Theorem 2.7. The optimal solution for Problem (8) is given as:

• If $0\leq W_{L_n} < R_1^{L_n}$, ${\gamma_{i}^*}^{L_n}=1$ and $\sum_{i\in J_n} {p_{ij}^t}^*=\sum_{i\in J_n}\frac{w_{i}^{L_n}}{\vert L_n\vert}$.

• If $R_1^{L_n}\leq W_{L_n}\leq R_2^{L_n}$, ${\gamma_{i}^*}^{L_n}=1-\frac{2\beta\sum_{i\in J_n} w_{i}^{L_n}-\alpha \vert L_n\vert}{2w_{i}^{L_n}\left (\vert J_n\vert \beta+\eta\vert L_n\vert\right)}$ and $\sum_{i\in J_n} {p_{ij}^t}^*=\frac{\alpha \vert J_n\vert +2\eta\sum_{i\in J_n}w_{i}^{L_n}}{2\left (\vert J_n\vert \beta+\eta\vert L_n\vert\right)}.$

• If $W_{L_n}>R_2^{L_n}$, ${\gamma_{i}^*}^{L_n}=1-\frac{\sum_{i\in J_n}w_{i}^{L_n}-\vert L_n\vert \min\left (|J_n|p_{\textrm{safe}}, ~p_{max}\right)}{ \vert J_n\vert w_{i}^{L_n}}$

and $\sum_{i\in J_n} {p_{ij}^t}^*=\min\left (|J_n|p_{\textrm{safe}}, ~p_{max}\right).$

As aforementioned, this problem can be solved by standard convex optimization techniques. Notice that the station learns all the information about the EVs currently connected to the station, and therefore its solution can be obtained using the same approach presented in Appendix A for the given period of time. Similar to the offline case, after we obtain the solution to $P^{*L_n}$ and $\gamma^{*L_n}$, the algorithm verifies if all EVs satisfy the condition $\gamma_{i}^{*L_n}\ge\gamma_{\min}$. If not, the new EV is rejected immediately. Here, the first and second stages are not re-executed.

In the next section, we apply the concept of competitive analysis to evaluate the proposed online two-stage charging strategy under non-congested and congested scenarios.

---

2.4. Competitive analysis

In this section, we apply the concept of competitive ratio to evaluate the proposed online algorithms against the offline counterparts and derive the closed-form expressions for a special scenario. For general cases, we will illustrate the competitive ratio performance by simulations. The main idea behind competitive analysis is to ensure that an online algorithm could guarantee an acceptable performance degradation compared to the offline algorithm. The concept of competitive ratio is defined below ^[47].

Definition 1. An online algorithm is $\sigma$-competitive if $\min_{J\in\Upsilon}\frac{F_{\textrm{on}}(J)}{F_{\textrm{off}}(J)}\geq\sigma$, where $J$ is an input instance with $N$ jobs, $\Upsilon$ is the collection of instances, and $F_{\textrm{on}}(J)$ and $F_{\textrm{off}}(J)$ are the unified profits obtained by the online and offline charging algorithms, respectively.

Here, as an special case, we derive the competitive ratio when each EV has a different arrival time $r_i$, with the same departure time $d$, user satisfaction factor $\gamma=1$, and energy requirement $W$. In the following theorem, we provide lower bounds of the competitive ratio in this special case under non-congested and congested scenarios.

Theorem 2.8. Given an arbitrary arrival time, a fixed departure time, the same user satisfaction factor $\gamma=1$, and the same energy requirement $W$, the lower bounds of the competitive ratio for non-congested and congested scenarios are given as follows:

(a) Non-congested (N-C) scenario (i.e. $G_t\leq C$ for all $t\in[1, T]$)

$\sigma\geq\frac{\alpha T-2\beta WN}{\alpha T-\beta WN},$

(b) Congested (C) scenario (i.e. $G_t>C$ for any $t\in[1, T]$)

$\sigma\geq\frac{\alpha WC\left(\frac{\vert S\vert-C}{T}+1\right)-\beta W^2\left[\frac{2|S|C}{T}+\frac{|S|-C}{C}+\frac{2(\vert S\vert-C)^2}{T-2(|S|-C)+1}\right]}{\alpha W \vert S\vert-\beta \frac{W^2\vert S\vert^2}{T}},$

where $G_t$ is the number of EVs being charged at time $t$ and $S$ is the set of all EVs scheduled.

The detailed proof of Theorem 2.8 is presented in Appendix B. The lower bounds of the competitive ratio under non-congested and congested scenarios in the mentioned special case are illustrated in the next section. The setup of parameters is given in the next section. The numerical evaluation of competitive ratio for general cases is given in the next section.

---

3. Numerical Results and Discussion

This section presents some simulation results to illustrate the performance of our offline and online two-stage charging algorithms. A numerical analysis has been conducted using the MATLAB-based optimization tool CVX ^[48] on a PC with Intel Core i7-4770, CPU speed 3.40 GHz, and 8 GB RAM.

We consider a public charging station with $C=10$ charging machines and $T=48$ time slots, each of which is of length $\Delta=30$ minutes. The total demand of the system is limited to $p_{\max}=30kW$. The number of EVs is $N=30$, and the amount energy (in $kWh$) for which the EV demands is a real number randomly drawn from ^[10,40]. All EVs have different arrival and departure times. We randomly pick $r_i$ from ^[1,32] and $d_i$ from $[r_i+4, r_i+16]$. The charging time is restricted to be at least $2$ hours since current fast charging stations take around 2-3 hours to fully charge an EV ^[8]. The minimum user satisfaction factor $\gamma_{\min}$ is set to be $0$, $0.5$ or $0.7$, respectively. Finally, we set $\alpha=4＄/kWh$, $\beta=0.10＄/(kWh)^2$, and $\eta=0.20＄/(kWh)^2$.

---

3.1. Offline two-stage charging algorithm

First, we illustrate the performance of our offline two-stage charging algorithms in terms of the average total profit, average computational time, average user satisfaction factor, and average power allocation, where the average results are taken over $100$ random realizations. In the following simulations, the number of charging machines is set as $C=10$ and a fixed $\gamma_{\min}$. We compare our algorithms with an exhaustive search charging algorithm and some conventional charging strategies.

In this subsection, we show the efficiency of our offline two-stage charging algorithms by comparing them against the exhaustive search algorithm. Because of its complexity, we consider the scenario when $N\le20$.

Figure 4 illustrates how the average profit of the station is affected by the number of vehicles $N$. For this specific case, both algorithms achieve about $85\%$ of the optimal solution obtained by the exhaustive search algorithm. We can also observe that both offline two-stage LP algorithms obtain its maximum profits when $N=20$. Such a critical number can also be viewed as the "service capacity" of the station. The profit will no longer increase due to a faster increasing operation cost, even when more EVs can be charged.

Then, we analyze the influence of the number of charging machines $C$ on the average profit. Figure 5 shows that when $N=15$, the offline exhaustive search and the offline two-stage LP algorithms need approximately $C=4$ machines to achieve their maximum profits. Meanwhile, the offline two-stage greedy algorithm needs about $C=10$ machines to achieve its maximum profit. In terms of the station's infrastructure, this information is useful when designing a large scale charging station.

In Table 3, we show the average computational time. Notice that both two-stage algorithms consume almost the same amount of computational time when $N < C$. After this point, the computational time of the offline two-stage LP algorithm increases at a higher rate. Table 3 shows that the exhaustive search algorithm consumes much more time and resources compared to the proposed strategies. Our offline two-stage algorithms utilize less system resources to find the solution at the cost of decreasing the optimality loss. However, as shown in Figure 4, both algorithms provide an acceptable profit compared to the optimal solution.

We then show the benefit of controlling the user satisfaction factor in Figure 6. When $N=30$, the two-stage LP and greedy algorithms with control of the user satisfaction factor $\gamma$ achieve a percentage of charging close to $72\%$. On the other hand, the two-stage LP and greedy algorithms without $\gamma$ control can only guarantee about $60\%$ and $55\%$ percentages of full charging, respectively. Therefore, as shown in the previous results, the control of user satisfaction factors improves both the profit and the QoS.

Next, we compare our proposed charging strategies with two other practical charging algorithms. The first one is a greedy searching algorithm with fixed power allocation where the power is delivered at a constant speed. To fully charge the vehicle, the customers have to stay connected until the expected charging time ends. The second benchmark model is a greedy search algorithm with uniform power allocation where the power is allocated uniformly based on the charging times and energy requirements. Both charging mechanisms utilize a First-In, First-Served (FIFS) scheduling policy where users are served in the order of their arrivals whenever a charging machine is idle. If all machines are occupied, the incoming EVs will be rejected. Due to the relatively small number of EVs nowadays and the simplicity of those algorithms, current public charging stations have implemented similar ideas to charge the EVs. For example, the EV charging company ChargePoint has implemented a FIFS waitlist feature to serve their customers ^[50]. In the following simulations, the number of charging machines is set as $C=10$ and $\gamma_{\min}$ is set to be $0$, $0.5$ or $0.7$, respectively.

In Figure 7, we show the average profit attained by different charging strategies. Notice that both offline two-stage algorithms outperform the benchmark charging approaches for any value of $\gamma_{\min}$. The greedy fixed and uniform power allocation algorithms have very poor performance since they provide negative profits when $N\ge22$ and $N\ge28$, respectively.

Furthermore, the average user satisfaction factor is shown in Figure 8, where the average is taken over both random realizations and different customers. We observe that both offline two-stage algorithms provide about $72\%$ of charging when $\gamma_{\min}=0$. Moreover, those algorithms outperform the conventional charging strategies when $\gamma_{\min}=0.7$, achieving about $93\%$ and $89\%$ of charging. This is obvious since our algorithms reject all the EVs with $\gamma$ smaller than $\gamma_{\min}$. Thus, both algorithms provide satisfactory results in terms of the user satisfaction factor while providing a higher profit.

We present the results related to the average power consumption in Figure 9, where the average is taken over both random realizations and time. Notice that, for any value of $\gamma_{\min}$, the proposed offline two-stage algorithms consume less power compared to the other practical approaches, specially the greedy uniform power allocation algorithm. This result is shown in Figure 7. As expected, the larger the power demand, the higher the consumption cost, which affects negatively the profit.

---

3.2. Online two-stage charging algorithm

This section presents some simulation results to illustrate the performance of our online two-stage charging algorithms in terms of the average total profit, average user satisfaction factor, and average power allocation, where the average results are also taken over $100$ random realizations. We also present some results with regard to the competitive ratio to show the efficiency of our online two-stage charging algorithms. In the following simulations, the number of charging machines is set as $C=10$ and $\gamma_{\min}$ is set to be $0$, $0.5$ or $0.7$, respectively.

In Figure 10 and Figure 11, we show the average profit for both offline and online charging scenarios. Notice that the offline two-stage algorithms provide a better profit as expected due to the knowledge of future charging requests. Also, we observe that the profit obtained by the online two-stage algorithms decreases as $\gamma_{\min}$ increases. We can consider this number as a critical point to decide which online strategy should be implemented in terms of system design and profit.

Furthermore, the average user satisfaction factor is shown in Figure 12 and Figure 13, where the average is taken over both random realizations and different customers. The online LP and greedy two-stage algorithms provide respectively about $60\%$ and $75\%$ (vs. $100\%$ and $85\%$) of charging when $\gamma_{\min}=0$ (vs. $\gamma_{\min}=0.7$). Notice that the user satisfaction factor increases as the value of $\gamma_{\min}$ increases, at the price of rejecting more customers. This information can be utilized to design an online strategy to achieve certain QoS requirement based on the expected number of arriving users.

We present the average power consumption in Figure 14 and Figure 15, where the average is taken over both random realizations and time. Notice that both online algorithms provide a lower power consumption compared with their offline counterparts. This is expected since the offline approach utilize the future charging information to uniformly allocate the total sum of power in order to reduce the power consumption cost.

Finally, we illustrate the competitive ratios for general cases. In Figure 16 and Figure 17, we show the competitive ratios achieved under non-congested and congested environments, respectively. In the non-congested case, the number of customers is small enough such that all EVs can be successfully scheduled and charged on the available machines. Here, both the online LP and greedy algorithms provide a competitive ratio of at least $88\%$ (vs. $80\%$) when $N=30$ and $\gamma_{\min}$ is $0$ (vs. $0.7$). Notice that, for any value of $\gamma_min$, the competitive ratios achieved is greater than the lower bound obtained in Theorem 2.8. Meanwhile, in the congested case, the number of customers is large and the number of EVs rejected increases. Here, the online LP and greedy algorithms provide a competitive ratio of at least $55\%$ and $25\%$ (vs. $40\%$ and $65\%$) when $N=30$ and $\gamma_{\min}$ is $0$ (vs. $0.7$), respectively. Notice again that, for any value of $\gamma_min$, the competitive ratios achieved is greater than the lower bounds presented in Theorem 2.8.

---

4. Conclusion

In this paper, we studied a profit maximization framework for electric vehicle charging under offline and online charging setups. Our algorithms achieve this goal by jointly optimizing EV scheduling, charging power, and user satisfaction factors for multiple EVs, where customers are guaranteed to be charged with at least $\gamma_{\min}$ of the desired energy target. We showed that the profit maximization problem is NP-complete for both cases, and proposed two-stage EV charging strategies to obtain some efficient suboptimal solutions. In the first stage, the station finds the best EV scheduling that maximizes the total profit by using either the LP relaxation or the greedy algorithm with fixed charging power and satisfaction factors. In the second stage, the station optimizes the power allocation and the user satisfaction factors to maximize the total profit of the station, where the forms of optimal solutions were derived. We also provided a competitive ratio analysis and considered a special scenario to obtain a close-form competitive ratio achieved by our online algorithms in non-congested and congested scenarios. Finally, simulation results were presented to evaluate our two-stage algorithms by comparing with other charging approaches, and showed that our strategies perform well with respect to the average total profit, average computational time, average user satisfaction factor, average power allocation, and competitive ratio. We noticed that for both offline and online cases the profit and the percentage of EVs serviced decrease as the value of $\gamma_{\min}$ increases, while the user satisfaction factor increases as the value of $\gamma_{\min}$ increases.

---

Acknowledgments

The work of S. Cui was supported in part by DoD with grant HDTRA1-13-1-0029, by grant NSFC-61328102/61629101, and by NSF with grants DMS-1622433, AST-1547436, ECCS-1508051/1659025, and CNS-1343155. The work of E. Collado was supported by the Panamanian Government through the SENACYT-IFARHU Scholarship Program.

---

Conflict of Interest

All authors declare no conflicts of interest in this paper.

---