Online Station Assignment for Electric Vehicle Battery Swapping
This paper investigates the online station assignment for (commercial) electric vehicles (EVs) that request battery swapping from a central operator, i.e., in the absence of future information a battery swapping service station has to be assigned instantly to each EV upon its request. Based on EVs' locations, the availability of fully-charged batteries at service stations in the system, as well as traffic conditions, the assignment aims to minimize cost to EVs and congestion at service stations. Inspired by a polynomial-time offline solution via a bipartite matching approach, we develop an efficient and implementable online station assignment algorithm that provably achieves the tight (optimal) competitive ratio under mild conditions. Monte Carlo experiments on a real transportation network by Baidu Maps show that our algorithm performs reasonably well on realistic inputs, even with a certain amount of estimation error in parameters.
© 2020 IEEE. Manuscript received November 13, 2018; revised March 11, 2020 and July 21, 2020; accepted October 14, 2020. Date of publication November 10, 2020; date of current version March 29, 2022. This work was supported by NSF under Grant CCF 1637598, Grant CPS ECCS 1739355, and Grant CPS ECCS 1932611. The Associate Editor for this article was B. De Schutter.
Accepted Version - 09254167.pdf