A Caltech Library Service

Online Station Assignment for Electric Vehicle Battery Swapping

You, Pengcheng and Pang, John Z. F. and Low, Steven H. (2020) Online Station Assignment for Electric Vehicle Battery Swapping. IEEE Transactions on Intelligent Transportation Systems . ISSN 1524-9050. (In Press)

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
You, Pengcheng0000-0003-1532-8773
Pang, John Z. F.0000-0002-6485-7922
Low, Steven H.0000-0001-6476-3048
Additional Information:© 2020 IEEE. Manuscript received November 13, 2018; revised March 11, 2020 and July 21, 2020; accepted October 14, 2020. This work was supported by NSF under Grant CCF 1637598, Grant CPS ECCS 1739355, and Grant CPS ECCS 1932611.
Funding AgencyGrant Number
Subject Keywords:Electric vehicle, battery swapping, assignment, bipartite matching, online algorithm
Record Number:CaltechAUTHORS:20201209-153308228
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106994
Deposited By: George Porter
Deposited On:10 Dec 2020 15:41
Last Modified:10 Dec 2020 15:41

Repository Staff Only: item control page