A Caltech Library Service

Online EV Scheduling Algorithms for Adaptive Charging Networks with Global Peak Constraints

Alinia, Bahram and Hajiesmaili, Mohammad H. and Lee, Zachary J. and Crespi, Noel and Mallada, Enrique (2022) Online EV Scheduling Algorithms for Adaptive Charging Networks with Global Peak Constraints. IEEE Transactions on Sustainable Computing, 7 (3). pp. 537-548. ISSN 2377-3782. doi:10.1109/tsusc.2020.2979854.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


This paper tackles online scheduling of electric vehicles (EVs) in an adaptive charging network (ACN) with local and global peak constraints. Given the aggregate charging demand of the EVs and the peak constraints of the ACN, it might be infeasible to fully charge all the EVs according to their charging demand. Two alternatives in such resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). The technical challenge is the need for online solution design since in practical scenarios the scheduler has no or limited information of future arrivals in a time-coupled underlying problem. For the fractional model, we devise both offline and online algorithms. We prove that the offline algorithm is optimal. Using competitive ratio as the performance measure, we prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is strongly NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. For offline setting, we devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases. Extensive trace-driven experimental results show that the performance of the proposed online algorithms is close to the offline optimum, and outperform the existing solutions.

Item Type:Article
Related URLs:
URLURL TypeDescription
Alinia, Bahram0000-0002-2974-6645
Lee, Zachary J.0000-0002-5358-2388
Crespi, Noel0000-0003-2962-192X
Mallada, Enrique0000-0003-1568-1833
Additional Information:The work of Mohammad H. Hajiesmaili was supported by NSF through grant CNS 1908298. The work of Zachary J. Lee was supported by the NSF Graduate Research Fellowship Program (Grant No. 1745301) and Resnick Sustainability Institute. Enrique Mallada is supported by ARO through contract W911NF-17-1-0092, US DoE EERE Award DE-EE0008006, and NSF through Grants CNS 1544771, EPCN 1711188, AMPS 1736448, and CAREER 1752362.
Group:Resnick Sustainability Institute
Funding AgencyGrant Number
NSF Graduate Research FellowshipDGE-1745301
Resnick Sustainability InstituteUNSPECIFIED
Army Research Office (ARO)W911NF-17-1-0092
Department of Energy (DOE)DE-EE0008006
Issue or Number:3
Record Number:CaltechAUTHORS:20220919-447854900
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117075
Deposited By: Melissa Ray
Deposited On:21 Sep 2022 22:32
Last Modified:21 Sep 2022 22:32

Repository Staff Only: item control page