Our paper on online EV scheduling for adaptive charging networks [1] has been accepted to IEEE Transactions on Sustainable Computing!
![[doi]](https://mallada.ece.jhu.edu/wp-content/plugins/papercite/img/external.png){kind=small}
B. Alinia, M. H. Hajiesmaili, Z. Lee, N. Crespi, and E. Mallada, “Online EV Scheduling Algorithms for Adaptive Charging Networks with Global Peak Constraints,” IEEE Transactions on Sustainable Computing, 2020. [Bibtex] [Abstract] [Download PDF]
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 critical challenge is the need for online solution design since in practical scenarios the scheduler has no information of future arrivals of EVs 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. 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.
@article{bhlcm2019tsusc,
abstract = {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 critical challenge is the need for online solution design since in practical scenarios the scheduler has no information of future arrivals of EVs 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. 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.},
author = {Alinia, Bahram and Hajiesmaili, Mohammad H. and Lee, Zachary and Crespi, Noel and Mallada, Enrique},
bdsk-url-3 = {https://doi.org/10.1109/TSUSC.2020.2979854},
doi = {10.1109/TSUSC.2020.2979854},
grants = {CAREER-1752362, CPS-1544771, ENERGISE-DE-EE0008006, AMPS-1736448, TRIPODS-1934979,EPCN-1711188,},
journal = {IEEE Transactions on Sustainable Computing},
month = {1},
title = {Online EV Scheduling Algorithms for Adaptive Charging Networks with Global Peak Constraints},
url = {https://mallada.ece.jhu.edu/pubs/2020-TSUSC-BHLCM.pdf},
year = {2020}
}