Loading [MathJax]/jax/output/SVG/jax.js
Research article Special Issues

Influence of environmental pollution and bacterial hyper-infectivity on dynamics of a waterborne pathogen model with free boundaries

  • In this paper, we mainly study the influence of environmental pollution and bacterial hyper-infectivity on the spreading of diseases by considering a waterborne pathogen model with free boundaries. At first, the global existence and uniqueness of the solution to this problem is proved. Then, we analyze its longtime behavior, which is determined by a spreading-vanishing dichotomy. Furthermore, we obtain the criteria for spreading and vanishing. Our results indicate that environmental pollution and bacterial hyper-infectivity can increase the chance of epidemic spreading.

    Citation: Meng Zhao, Jiancheng Liu, Yindi Zhang. Influence of environmental pollution and bacterial hyper-infectivity on dynamics of a waterborne pathogen model with free boundaries[J]. Networks and Heterogeneous Media, 2024, 19(3): 940-969. doi: 10.3934/nhm.2024042

    Related Papers:

    [1] Dalong Guo, Chi Zhou . Potential performance analysis and future trend prediction of electric vehicle with V2G/V2H/V2B capability. AIMS Energy, 2016, 4(2): 331-346. doi: 10.3934/energy.2016.2.331
    [2] Syed Sabir Hussain Rizvi, Krishna Teerth Chaturvedi, Mohan Lal Kolhe . A review on peak shaving techniques for smart grids. AIMS Energy, 2023, 11(4): 723-752. doi: 10.3934/energy.2023036
    [3] Mansoor Soomro, Zeeshan Ali Shaikh, Mazhar Baloch, Abdul Manan Shaikh, Sohaib Tahir Chauhdary . Development of wind and solar systems for power charging: An application of an electric vehicle to grid systems. AIMS Energy, 2024, 12(3): 664-685. doi: 10.3934/energy.2024031
    [4] HVV Priyadarshana, MA Kalhan Sandaru, KTMU Hemapala, WDAS Wijayapala . A review on Multi-Agent system based energy management systems for micro grids. AIMS Energy, 2019, 7(6): 924-943. doi: 10.3934/energy.2019.6.924
    [5] Tiansong Cui, Yanzhi Wang, Shahin Nazarian, Massoud Pedram . Profit maximization algorithms for utility companies in an oligopolistic energy market with dynamic prices and intelligent users. AIMS Energy, 2016, 4(1): 119-135. doi: 10.3934/energy.2016.1.119
    [6] Yuan Liu, Ruilong Deng, Hao Liang . Game-theoretic control of PHEV charging with power flow analysis. AIMS Energy, 2016, 4(2): 379-396. doi: 10.3934/energy.2016.2.379
    [7] Kangli Xiang, Keren Chen, Simin Chen, Wanqing Chen, Jinyu Chen . Model for sustainable carbon emission reduction energy development and smart grid technology strategy. AIMS Energy, 2024, 12(6): 1206-1224. doi: 10.3934/energy.2024055
    [8] Albert Albers, Aline Radimersky, Sascha Ott . Systematic definition of objectives for battery systems considering the interdependencies in electric vehicles. AIMS Energy, 2016, 4(5): 723-741. doi: 10.3934/energy.2016.5.723
    [9] Hassan Shirzeh, Fazel Naghdy, Philip Ciufo, Montserrat Ros . Stochastic energy balancing in substation energy management. AIMS Energy, 2015, 3(4): 810-837. doi: 10.3934/energy.2015.4.810
    [10] Anbazhagan Geetha, S. Usha, J. Santhakumar, Surender Reddy Salkuti . Forecasting of energy consumption rate and battery stress under real-world traffic conditions using ANN model with different learning algorithms. AIMS Energy, 2025, 13(1): 125-146. doi: 10.3934/energy.2025005
  • In this paper, we mainly study the influence of environmental pollution and bacterial hyper-infectivity on the spreading of diseases by considering a waterborne pathogen model with free boundaries. At first, the global existence and uniqueness of the solution to this problem is proved. Then, we analyze its longtime behavior, which is determined by a spreading-vanishing dichotomy. Furthermore, we obtain the criteria for spreading and vanishing. Our results indicate that environmental pollution and bacterial hyper-infectivity can increase the chance of epidemic spreading.



    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 (CO2) 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.

    Figure 1. Connection between charging machines and plugs.

    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 ri[1,T], the departure time di[1,T], and the required energy wi, where ri<diT. The charging period of each EV is denoted by Ti=[ri,di] and its length is given by |Ti|=diri+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., [ri,di] and wi). 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 wi. The scheduling of EVs at time t is represented by Xt={xti,j}, where 1iN, 1jC, and xti,j is given by

    xtij={1,iftheithEVisassignedtothejthchargingmachineattimet,0,otherwise.

    Then, the overall scheduling is denoted by X={X1,X2,,XT}. Similarly, the charging power at time slot t is represented by Pt={pti,j}, where pti,j is the charging power level of the jth machine for the ith EV at time t. Here, we assume that the pti,j is limited by a safe maximum charging power psafe, which is a system constant set by the operator in advance. The overall power allocation is denoted by P={P1,P2,,PT}. Note that we normalize the slot length such that the power allocation vector is also representing the energy charging vector. Now, let γ={γ1,γ2,,γN} denote the set of user satisfaction factors, at which each vehicle is serviced by the end of the schedule, where γi[γmin,1] for 1iN. Here, we assume that the minimum user satisfaction factor γ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 α>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)=αTt=1Cj=1Ni=1ptijxtij.

    The operation cost of the station includes two parts:

    • The power consumption cost is given by

    C2(X,γ)=ηCj=1Ni=1(wiγiwi)21{Tt=1xtij1},

    where β>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

    C2(X,γ)=ηCj=1Ni=1(wiγiwi)21{Tt=1xtij1},

    where η>0 is the penalty weighting parameter. The function C2(X,γ) is defined to be the residual sum of the squared discrepancy between the delivered and the desired values.

    We assume that α, β, and η 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,γ)=U(X,P)[C1(X,P)+C2(X,γ)].

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

    maximizeX,P,γF(X,P,γ) (1)
    subject toCj=1Ni=1ptijxtijpmax,t=1,,T; (1.1)
    γiwidit=riptijxtijwi,i=1,,N,j=1,,C; (1.2)
    Cj=1xtij1,i=1,,N,t=1,,T; (1.3)
    Ni=1xtij1,j=1,,C,t=1,,T; (1.4)
    xtij{0,1},i=1,,N,j=1,,C,t=1,,T; (1.5)
    0ptijpsafe,i=1,,N,j=1,,C,t=1,,T; (1.6)
    γminγi1,i=1,,N. (1.7)

    Here, (1.1) ensures that the total power allocation at each time slot does not exceed the power limit pmax; (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 pti,j, which is limited by a safe maximum charging power psafe 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 S is our certificate. A deterministic algorithm verifies whether each EV i{1,2,,N} is assigned to any charging machine j{1,2,,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 pmax 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:

    maximizeXCj=1Ni=1(αwiβw2i|Ti|2βwi|Ti|Nk=1,ki|Tik|wk|Tk|)xij (2)
    subject toCj=1Ni=1wi|Ti|xtijpmax,t=1,,T; (2.1)
    Cj=1xtij1,i=1,,N,t=1,,T; (2.2)
    Ni=1xtij1,j=1,,C,t=1,,T; (2.3)
    xtij{0,1},i=1,,N,j=1,,C,t=1,,T, (2.4)

    where xij=Tt=1xtij and |Tik| 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 γmin of the desired energy target. If not, the EVs with invalid γ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 ptij=wi|Ti| and γi=1 for all i{1,2,,N}, j{1,2,,C}, and t[ri,di]. 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 xtij{0,1} with a weaker constraint 0xtij1. 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 ˜xtij{0,1} by rounding the fractional solution xtij 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 0xtij1. It can be shown that the offline LP relaxation scheduling algorithm guarantees at least (e1)/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(Tmin{N,C}(2N+T+1)) time.

    Proof: The algorithm starts by solving the relaxed LP Problem (5). This part needs O(min{N,C}T(2N+T)) computation times. Here, min{N,C}T is the number of variables and (2N+T) 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(min{N,C}T) computation times. Finally, the total computational time of the offline LP relaxation scheduling algorithm is O(Tmin{N,C}(2N+T+1)).

    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., f1f2fN). 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(N(logN+C)) 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(NlogN) 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(NC) time. Therefore, the total computational time of the offline greedy scheduling algorithm is O(N(logN+C)).

    Table 1. Algorithm 1: Offline greedy scheduling algorithm.
    1. Let X be the overall EV schedule and S be the set of accepted EVs. Initialize X and S.
    2. Let pit=wi|Ti| and γi=1 for all i=1,,N, t=1,,T, where Ti is the charging period of EV i.
    3. Calculate the individual profit fi=αwiβw2i|Ti|2βwi|Ti|1kNki|Tik|wk|Tk| for all i=1,,N, t=1,,T, where |Tik| is the number of time slots when job i overlaps with job k.
    4. Sort users in a non-increasing order of their individual profits. If two or more EVs have the same individual profit, choose the one with the shortest charging time first.
    5. Run the following:
    FOR i:=1 TO N DO
    Let Hi={j:j is idle between time ri and dij{1,2,,C}}.
    IF |Hi|1 THEN
    zi=min{j:jHi}.
    Let xti=zi, for ritdi.
    ELSE
    Calculate |Gik|, the number of time slots when job i does not
    overlap with job k.
    IF |Gik|>0 for any k{1,2,,N} THEN
    Choose k=argmaxk{1,2,,N},ki|Gik|.
    Let xti=xtk, for tGik.
    ELSE
    Reject EV i.
    END IF
    END IF
    END FOR
    6. Output X and S.
     | Show Table
    DownLoad: CSV

    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 ˜X, the unified profit is given by

    F(P,γ)=Tt=1[αCj=1Ni=1ptijβ(Cj=1Ni=1ptij)2]ηCj=1Ni=1(wiγiwi)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}.

    Figure 2. Partition the set of all users into independent groups.

    Let M denote the number of independent groups. For 1mM, let Im be the set of EVs included in the mth group, and |Im| be the size of Im. The charging period of the mth group is denoted by Dm=[miniImri,maxiImdi] and its length is given by |Dm|=maxiImdiminiImri+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 mth group can be formulated as:

    maximizeP,γtDm[αiImptijβ(iImptij)2]ηiIm(wiγiwi)2 (3)
    subject toiImptijpmax,j=1,,C,m=1,,M,tDm; (3.1)
    γiwidit=riptijwi,iIm,j=1,,C,m=1,,M; (3.2)
    0ptijpsafe,iIm,j=1,,C,m=1,,M,tDm; (3.3)
    0γi1,iIm. (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 Wm=iImwi be the total energy demanded by the mth 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 Wm, which is shown in Figure 3. Let R1=α|Dm|2β and R2=12η{2min(|Im|psafe, pmax)(|Im|β+η|Dm|)α|Im|} for notation simplicity. Then, we observe the following operation regions:

    Figure 3. Impact of the energy demand on the unified profit of the system.

    • When Wm[0,R1), the profit increases as Wm 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 mth group.

    • When Wm[R1,R2], the profit starts decreasing but remains acceptable.

    • When Wm(R2,), 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 0Wm<R1, γi=1 and iImpijt=iImwi|Dm|.

    • If R1WmR2, γi=12βiImwiα|Dm|2wi(|Im|β+η|Dm|) and iImpijt=α|Im|+2ηiImwi2(|Im|β+η|Dm|).

    • If Wm>R2, γi=1iImwi|Dm|min(|Im|psafe, pmax)|Im|wi and iImpijt=min(|Im|psafe, pmax).

    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 γi from Theorem 2.4.

    • If 0Wm<R1, then γi=1.

    • If R1WmR2, then 12βmin(|Im|psafe, pmax)α2ηwiγi1.

    • If Wm>R2, then 0γi<12βmin(|Im|psafe, pmax)α2ηwi.

    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 iImpijt is constant over time for all tDm. From the KKT conditions given in the Appendix A, we observe that iImpijt=iImγiwi|Dm|, where γi[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 |Im|+(maxiImdiminiImri+1) equations and |Im|+iIm(diri) unknown variables. Since the arrival and departure times satisfy ri<di, 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 γ are obtained, the algorithm verifies if every EV satisfies the condition γiγmin. If not, the group of EVs with γi<γ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 Jn 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 Ln=[rn,maxkJndk]. Both Jn and Ln are updated at each arrival time based on the current charging information. The remaining energy requirement is also updated at each period Ln after the arrival of EV n, given by wLni=wivLni for all iJn, where vLni=rn1t=1ptij is the energy already delivered before rn.

    Our main goal is to maximize the total profit for the charging station during the period Ln 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 wLni. Similar to the offline section, the schedule of all EVs at time t is represented by the matrix Xt={xti,j}, where iJn, 1jC, and tLn.

    Then, the scheduling during the charging period Ln is denoted by XLn={Xt,tLn}. Similarly, the charging power at time slot t is represented by Pt={pti,j}, where pti,j is the charging power level of the jth machine for the ith EV at tLn. As such, the total power allocation is denoted by PLn={Pt,tLn}. Now, let γLn={γLn1,γLn2,,γLn|Jn|} denote the set of user satisfaction factors, at which each vehicle is guaranteed to be charged at the end of the period Ln, where γLni[0,1] for iJn. The overall online EV charging problem for a given charging period Ln is formulated as follows:

    maximizeγLn,XLn,PLntLn{αCj=1iJnptijxtijβ(Cj=1iJnptijxtij)2}ηCj=1iJn(wLniγLniwLni)21{tLnxtij1}, (4)
    subject toCj=1iJnptijxtijpmax,tLn; (4.1)
    γLniwLnidit=riptijxtijwLni,iJn,j=1,,C; (4.2)
    Cj=1xtij1,iJn,tLn; (4.3)
    iJnxtij1,j=1,,C,tLn; (4.4)
    xtij{0,1},iJn,j=1,,C,tLn; (4.5)
    0ptijPsafe,iJn,j=1,,C,tLn; (4.6)
    γminγLni1,iJn. (4.7)

    Here, (4.1) ensures that the total power allocation does not exceed the power limit pmax; (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 pti,j; 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 Ln. 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 γ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 Ln. Similar to the offline case, we introduce two algorithms: the online LP relaxation and greedy scheduling algorithms. We set ptij=wLni|Ti| and γLni=1. This problem can be formulated as:

    maximizeXLnCj=1iJn(αwLniβ(wLni)2|Ti|2βwLni|Ti|kJn,ki|Tik|wLnk|Tk|)xij (5)
    subject toCj=1iJnwLni|Ti|xtijpmax,tLn; (5.1)
    Cj=1xtij1,iJn,tLn; (5.2)
    iJnxtij1,j=1,,C,tLn; (5.3)
    xtij{0,1},iJn,j=1,,C,tLn. (5.4)

    where xij=tLnxtij and |Tik| is the number of timeslots in Ln 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 xtij{0,1} with a weaker constraint 0xtij1, for all tLn. The obtained optimal fractional solution to the relaxed LP problem is then rounded using the same rounding approach to obtain the desired integer solution ˜xtij{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 (e1)/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 Jn jobs and C machines at the arrival time rn, the online LP relaxation scheduling algorithm finds a feasible schedule in approximately O(NTmin{N,C}(2N+T+1)) time, where N=maxn|Jn|.

    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 fk of all EVs k<n already connected to stations and the individual profit fn of EV n. Then, the algorithm needs to immediately make the decision whether to accept or decline EV n. If fnfk for any EV k<n, the station stops charging EV k and schedule EV n to the relieved charging machine. Moreover, if fn<fk and dn>dk 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 Jn jobs and C machines at the arrival time rn, the online greedy scheduling algorithm finds a feasible schedule in O(N2(logN+C)) time, where N=maxn|Jn|.

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

    Table 2. Algorithm 2: Online greedy scheduling algorithm.
    FOR each EV n arriving at the station DO
    Let XLn be the total EV schedule and SLn be the set of accepted EVs in Ln.
    Initialize XLn and SLn.
    FOR t:=rn TO maxkJndk DO
    Let Hn={j:j is idle between time rn and dnj{1,2,,C}}.
    IF |Hn|1 THEN
    zn=min{j:jHn}.
    Let xtn=zn, for rntdn.
    ELSE
    Let ptn=wLnn|Tn| and γLnn=1, for all tLn.
    Calculate fn=αwLnnβ(wLnn)2|Tn|2βwLnn|Tn|k<n|Tnk|wLnk|Tk|, where fn is the
    individual profit and |Tnk| is the number of time slots in Ln when job
    n and job k overlap.
    IF fnfk THEN
    Choose k=argmaxk<nfnfk.
    Let xtn=xtk, for rntdn.
    ELSE IF fn<fk and |Gnk|>0 for any k<n THEN
    Choose k=argmaxk<n|Gnk|.
    Let xtn=xtk, for tGnk.
    ELSE
    Reject EV n.
    END IF
    END IF
    END FOR
    Output XLn and SLn.
    END FOR
     | Show Table
    DownLoad: CSV

    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:

    maximizePLn,γLntLn{αCj=1iJnptijβ(Cj=1iJnptij)2}ηCj=1iJn(wLniγLniwLni)2 (6)
    subject toCj=1iJnptijpmax,tLn; (6.1)
    γLniwLnidit=riptijwLni,iJn,j=1,,C; (6.2)
    0ptijpsafe,iJn,j=1,,C,tLn; (6.3)
    0γLni1,iJn,tLn. (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 iJn during the period Ln be defined as WLn=iJnwLni. Let RLn1=α|Ln|2β and RLn2=12η[2min(|Jn|psafe, pmax)(|Jn|β+η|Ln|)α|Jn|], where RLn1 and RLn2 are updated at every arrival time. We can provide the same operation regions as illustrated in Figure 3 for a given charging period Ln.

    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 tLn.

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

    • If 0WLn<RLn1, γiLn=1 and iJnptij=iJnwLni|Ln|.

    • If RLn1WLnRLn2, γiLn=12βiJnwLniα|Ln|2wLni(|Jn|β+η|Ln|) and iJnptij=α|Jn|+2ηiJnwLni2(|Jn|β+η|Ln|).

    • If WLn>RLn2, γiLn=1iJnwLni|Ln|min(|Jn|psafe, pmax)|Jn|wLni

    and iJnptij=min(|Jn|psafe, pmax).

    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 PLn and γLn, the algorithm verifies if all EVs satisfy the condition γLniγ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 σ-competitive if minJΥFon(J)Foff(J)σ, where J is an input instance with N jobs, Υ is the collection of instances, and Fon(J) and Foff(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 ri, with the same departure time d, user satisfaction factor γ=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 γ=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. GtC for all t[1,T])

    σαT2βWNαTβWN,

    (b) Congested (C) scenario (i.e. Gt>C for any t[1,T])

    σαWC(|S|CT+1)βW2[2|S|CT+|S|CC+2(|S|C)2T2(|S|C)+1]αW|S|βW2|S|2T,

    where Gt 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 Δ=30 minutes. The total demand of the system is limited to pmax=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 ri from [1,32] and di from [ri+4,ri+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 γmin is set to be 0, 0.5 or 0.7, respectively. Finally, we set α=4/kWh, β=0.10/(kWh)2, and η=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 γ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 N20.

    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.

    Figure 4. Average profit of the offline two-stage algorithms against the exhaustive search.

    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.

    Figure 5. Influence of the number of charging machines on the average profit of the 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.

    Table 3. Average computational time (sec).
    Number of EVs Exhaustive Search Two-stage LP Two-stage GS
    5 18.9932 1.3686 1.2771
    10 753.8080 1.9585 1.8642
    15 5140.2536 5.3386 2.4304
    20 567887.6684 6.6386 2.9947
     | Show Table
    DownLoad: CSV

    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 γ achieve a percentage of charging close to 72%. On the other hand, the two-stage LP and greedy algorithms without γ 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.

    Figure 6. Benefit of controlling the user satisfaction factor.

    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 γ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 γmin. The greedy fixed and uniform power allocation algorithms have very poor performance since they provide negative profits when N22 and N28, respectively.

    Figure 7. Average profit of the offline two-stage algorithms against other practical charging algorithms.

    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 γmin=0. Moreover, those algorithms outperform the conventional charging strategies when γmin=0.7, achieving about 93% and 89% of charging. This is obvious since our algorithms reject all the EVs with γ smaller than γmin. Thus, both algorithms provide satisfactory results in terms of the user satisfaction factor while providing a higher profit.

    Figure 8. Average user satisfaction factor of the offline two-stage algorithms against other practical charging algorithms.

    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 γ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.

    Figure 9. Average power consumption of the offline two-stage algorithms against other practical charging algorithms.

    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 γ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 γ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.

    Figure 10. Average profit of the online LP two-stage algorithm against its offline counterpart.
    Figure 11. Average profit of the online greedy two-stage algorithm against its offline counterpart.

    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 γmin=0 (vs. γmin=0.7). Notice that the user satisfaction factor increases as the value of γ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.

    Figure 12. Average user satisfaction factor of the online LP two-stage algorithm against its offline counterpart.
    Figure 13. Average user satisfaction factor of the online greedy two-stage algorithm against its offline counterpart.

    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.

    Figure 14. Average power consumption of the online LP two-stage algorithm against its offline counterpart.
    Figure 15. Average power consumption of the online greedy two-stage algorithm against its offline counterpart.

    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 γmin is 0 (vs. 0.7). Notice that, for any value of γ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 γmin is 0 (vs. 0.7), respectively. Notice again that, for any value of γmin, the competitive ratios achieved is greater than the lower bounds presented in Theorem 2.8.

    Figure 16. Average competitive ratio for general cases under non-congested scenarios.
    Figure 17. Average competitive ratio for general cases under congested scenarios.

    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 γ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 γmin increases, while the user satisfaction factor increases as the value of γ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.




    [1] J. N. Eisenberg, M. Brookhart, G. Rice, M. Brown, J. Colford, Disease transmission models for public health decision making: Analysis of epidemic and endemic conditions caused by waterborne pathogens, Environ. Health Perspect., 110 (2002), 783–790. https://doi.org/10.1289/ehp.02110783 doi: 10.1289/ehp.02110783
    [2] C. Codeco, Endemic and epidemic dynamics of cholera: The role of the aquatic reservoir, BMC Infect. Dis., 1 (2001), 1–14. https://doi.org/10.1186/1471-2334-1-1 doi: 10.1186/1471-2334-1-1
    [3] J. H. Tien, D. J. D. Earn, Multiple transmission pathways and disease dynamics in a waterborne pathogen model, Bull. Math. Biol., 72 (2010), 1506–1533. https://doi.org/10.1007/s11538-010-9507-6 doi: 10.1007/s11538-010-9507-6
    [4] J. Zhou, Y. Yang, T. Zhang, Global dynamics of a reaction-diffusion waterborne pathogen model with general incidence rate, J. Math. Anal. Appl., 466 (2018), 835–859. https://doi.org/10.1016/j.jmaa.2018.06.029 doi: 10.1016/j.jmaa.2018.06.029
    [5] H. Song, Y. Zhang, Traveling waves for a diffusive SIR-B epidemic model with multiple transmission pathways, Electron. J. Qual. Theory Differ. Equations, 86 (2019), 1–19. https://doi.org/10.14232/ejqtde.2019.1.86 doi: 10.14232/ejqtde.2019.1.86
    [6] Y. Du, Z. Lin, Spreading-vanishing dichotomy in the diffusive logistic model with a free boundary, SIAM J. Math. Anal., 42 (2010), 377–405. https://doi.org/10.1137/090771089 doi: 10.1137/090771089
    [7] M. Zhao, Dynamics of a reaction-diffusion waterborne pathogen model with free boundaries, Nonlinear Anal. Real World Appl., 77 (2024), 104043. https://doi.org/10.1016/j.nonrwa.2023.104043 doi: 10.1016/j.nonrwa.2023.104043
    [8] J. F. Cao, W. T. Li, J. Wang, F. Y. Yang, A free boundary problem of a diffusive SIRS model with nonlinear incidence, Z. Angew. Math. Phys., 68 (2017), 39. https://doi.org/10.1007/s00033-017-0786-8 doi: 10.1007/s00033-017-0786-8
    [9] Y. Hu, X. Hao, X. Song, Y. Du, A free boundary problem for spreading under shifting climate, J. Differ. Equations, 269 (2020), 5931–5958. https://doi.org/10.1016/j.jde.2020.04.024 doi: 10.1016/j.jde.2020.04.024
    [10] K.I. Kim, Z. Lin, Q. Zhang, An SIR epidemic model with free boundary, Nonlinear Anal. Real World Appl., 14 (2013), 1992–2001. https://doi.org/10.1016/j.nonrwa.2013.02.003 doi: 10.1016/j.nonrwa.2013.02.003
    [11] Y. Tang, B. Dai, Z. Li, Dynamics of a Lotka-Volterra weak competition model with time delays and free boundaries, Z. Angew. Math. Phys., 73 (2022), 143. https://doi.org/10.1007/s00033-022-01788-8 doi: 10.1007/s00033-022-01788-8
    [12] J. B. Wang, W. T. Li, F. D. Dong, S. X. Qiao, Recent developments on spatial propagation for diffusion equations in shifting environments, Discrete Contin. Dyn. Syst. Ser. B, 27 (2022), 5101–5127. https://doi.org/10.3934/dcdsb.2021266 doi: 10.3934/dcdsb.2021266
    [13] H. Zhang, L. Li, M. Wang, Free boundary problems for the local-nonlocal diffusive model with different moving parameters, Discrete Contin. Dyn. Syst. Ser. B, 28 (2023), 474–498. https://doi.org/10.3934/dcdsb.2022085 doi: 10.3934/dcdsb.2022085
    [14] K. D. Lafferty, R. D. Holt, How should environmental stress affect the population dynamics of disease, Ecol. Lett., 6 (2003), 654–664. https://doi.org/10.1046/j.1461-0248.2003.00480.x doi: 10.1046/j.1461-0248.2003.00480.x
    [15] W. Wang, Z. Feng, Influence of environmental pollution to a waterborne pathogen model: Global dynamics and asymptotic profiles, Commun. Nonlinear Sci. Numer. Simul., 99 (2021), 105821. https://doi.org/10.1016/j.cnsns.2021.105821 doi: 10.1016/j.cnsns.2021.105821
    [16] D. M. Hartley, J. G. Morris Jr, D. L. Smith, Hyperinfectivity: A critical element in the ability of V. cholerae to cause epidemics, PLoS Med., 3 (2006), 63–69. https://doi.org/10.1371/journal.pmed.0030007 doi: 10.1371/journal.pmed.0030007
    [17] J. Wang, X. Wu, Dynamics and profiles of a diffusive cholera model with bacterial hyperinfectivity and distinct dispersal rates, J. Dyn. Differ. Equations, 35 (2023), 1205–1241. https://doi.org/10.1007/s10884-021-09975-3 doi: 10.1007/s10884-021-09975-3
    [18] V. Capasso, G. Serio, A generalization of the Kermack-McKendrick deterministic epidemic model, Math. Biosci., 42 (1978), 43–61. https://doi.org/10.1016/0025-5564(78)90006-8 doi: 10.1016/0025-5564(78)90006-8
    [19] G. Dimarco, B. Perthame, G. Toscani, M. Zanella, Kinetic models for epidemic dynamics with social heterogeneity, J. Math. Biol., 83 (2021), 4. https://doi.org/10.1007/s00285-021-01630-1 doi: 10.1007/s00285-021-01630-1
    [20] G. Bunting, Y. Du, K. Krakowski, Spreading speed revisited: Analysis of a free boundary model, Networks Heterogen. Media, 7 (2012), 583–603. https://doi.org/10.3934/nhm.2012.7.583 doi: 10.3934/nhm.2012.7.583
    [21] S. Sharma, N. Kumari, Dynamics of a waterborne pathogen model under the influence of environmental pollution, Appl. Math. Comput., 346 (2019), 219–243. https://doi.org/10.1016/j.amc.2018.10.044 doi: 10.1016/j.amc.2018.10.044
    [22] P. Zhou, D. Xiao, The diffusive logistic model with a free boundary in heterogeneous environment, J. Differ. Equations, 256 (2014), 1927–1954. https://doi.org/10.1016/j.jde.2013.12.008 doi: 10.1016/j.jde.2013.12.008
    [23] L. Li, S. Liu, M. Wang, A viral propagation model with a nonlinear infection rate and free boundaries, Sci. China Math., 64 (2021), 1971–1992. https://doi.org/10.1007/s11425-020-1680-0 doi: 10.1007/s11425-020-1680-0
    [24] S. Liu, M. Wang, Existence and uniqueness of solution of free boundary problem with partially degenerate diffusion, Nonlinear Anal. Real World Appl., 54 (2020), 103097. https://doi.org/10.1016/j.nonrwa.2020.103097 doi: 10.1016/j.nonrwa.2020.103097
    [25] M. Wang, Existence and uniqueness of solutions of free boundary problems in heterogeneous environments, Discrete Contin. Dyn. Syst. Ser. B, 24 (2019), 415–421. https://doi.org/10.3934/dcdsb.2018179 doi: 10.3934/dcdsb.2018179
    [26] A. Friedman, Partial Differential Equations of Parabolic Type, Courier Dover Publications, Prentice-Hall, Englewood Cliffs, NJ, 1964.
    [27] O. A. Ladyzenskaja, V. A. Solonnikov, N. N. Uralceva, Linear and Quasilinear Equations of Parabolic Type, Academic Press, New York, 1968.
    [28] H. Huang, M. Wang, A nonlocal SIS epidemic problem with double free boundaries, Z. Angew. Math. Phys., 70 (2019), 109. https://doi.org/10.1007/s00033-019-1156-5 doi: 10.1007/s00033-019-1156-5
    [29] M. Wang, J. Zhao, A free boundary problem for the predator-prey model with double free boundaries, J. Dyn. Differ. Equations, 29 (2017), 957–979. https://doi.org/10.1007/s10884-015-9503-5 doi: 10.1007/s10884-015-9503-5
    [30] M. Wang, Q. Zhang, Dynamics for the diffusive Leslie-Gower model with double free boundaries, preprint, arXiv: 1710.09564.
    [31] M. Zhao, The longtime behavior of an SIR epidemic model with free boundaries, J. Nonlinear Model. Anal., 6 (2024), 476–484. https://doi.org/10.12150/jnma.2024.476 doi: 10.12150/jnma.2024.476
    [32] W. Wang, X. Q. Zhao, Basic reproduction numbers for reaction-diffusion epidemic models, SIAM J. Appl. Dyn. Syst., 11 (2012), 1652–1673. https://doi.org/10.1137/120872942 doi: 10.1137/120872942
    [33] L. Li, W. Ni, M. Wang, Dynamical properties of a new SIR epidemic model, Discrete Contin. Dyn. Syst. Ser. S, 17 (2024), 690–707. https://doi.org/10.3934/dcdss.2023076 doi: 10.3934/dcdss.2023076
    [34] R. Wang, Y. Du, Long-time dynamics of a diffusive epidemic model with free boundaries, Discrete Contin. Dyn. Syst. Ser. B, 26 (2021), 2201–2238. https://doi.org/10.3934/dcdsb.2020360 doi: 10.3934/dcdsb.2020360
    [35] I. Ahn, S. Beak, Z. Lin, The spreading fronts of an infective environment in a man-environment-man epidemic model, Appl. Math. Model., 40 (2016), 7082–7101. https://doi.org/10.1016/j.apm.2016.02.038 doi: 10.1016/j.apm.2016.02.038
  • This article has been cited by:

    1. Liu Pai, Tomonobu Senjyu, A Yearly Based Multiobjective Park-and-Ride Control Approach Simulation Using Photovoltaic and Battery Energy Storage Systems: Fuxin, China Case Study, 2022, 14, 2071-1050, 8655, 10.3390/su14148655
    2. Doaa Abubakr Hussien, Walid A. Omran, R. M. Sharkawy, 2023, Smart Charging of Electric Vehicles in Charging Stations, 979-8-3503-9952-3, 1, 10.1109/REEPE57272.2023.10086885
    3. Jangkyum Kim, Joohyung Lee, Sangdon Park, Jun Kyun Choi, Power Scheduling Scheme for a Charging Facility Considering the Satisfaction of Electric Vehicle Users, 2022, 10, 2169-3536, 25153, 10.1109/ACCESS.2022.3151355
    4. V Rajini, VS Nagarajan, Karunya Harikrishnan, Mohan Lal Kolhe, Electromagnetic design, sensitivity analysis, optimization and Multiphysics capability of rare-earth-free synchronous reluctance motor for electric trike vehicle, 2024, 12, 2333-8334, 1027, 10.3934/energy.2024049
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(934) PDF downloads(73) Cited by(0)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog