A Structural Property of Charging Scheduling Policy for Shared Electric Vehicles with Wind Power Generation

In this work, we focus on the optimization of charging scheduling policy for shared electric vehicles (EVs) integrated with wind power generation. This problem is of significant importance nowadays because of the large adoption of EVs in modern societies and the increasing penetration of renewables. A particular challenge of the problem is the large action space, the size of which may increase exponentially with respect to the number of EVs in the system. This makes the problem difficult to solve in practice. A lot of efforts have been made to overcome the above difficulty. The previous study proposed least-laxity-longer-processing-time-first (LLLP) principle, a rule-based algorithm to schedule EVs' battery charging. The LLLP principle assigns higher priority to vehicles with less laxity and longer processing time. We extend the LLLP principle and further study the structural property of the charging scheduling problem. The main contributions in this work are as follows. First, we show that the LLLP applies to our problem and may be used to narrow down the action space while preserving the global optimality. Second, we provide a modified LLLP algorithm that may construct a policy in $O(NT)$ , where $N$ is the number of the EVs and $T$ is the number of time steps in the scheduling problem. Third, we use numerical experiments to show that the new algorithm performs better than other existing algorithms, including the least-laxity-shorter-processing-time-first (LLSP) principle, the earliest-deadline-first (EDF) principle, and the latest-deadline-first (LDF) principle. The new algorithm finds near-optimal policies (within 1% performance loss) and is at least 40 times faster than CPLEX. We hope that this work provides insight into the charging scheduling of shared EVs in general.