A Node-Charge Graph-Based Online Carshare Rebalancing Policy with Capacitated Electric Charging

Theodoros P. Pantelidis, Li Li, Tai Yu Ma, Joseph Y.J. Chow, Saif Eddin G. Jabari

Research output: Contribution to journalArticlepeer-review


Viability of electric car-sharing operations depends on rebalancing algorithms. Earlier methods in the literature suggest a trend toward nonmyopic algorithms using queueing principles. We propose a new rebalancing policy using cost function approximation. The cost function is modeled as a p-median relocation problem with minimum cost flow conservation and path-based charging station capacities on a static node-charge graph structure. The cost function is NP complete, so a heuristic is proposed that ensures feasible solutions that can be solved in an online system. The algorithm is validated in a case study of electric carshare in Brooklyn, New York, with demand data shared from BMW ReachNow operations in September 2017 (262 vehicle fleet, 231 pickups per day, and 303 traffic analysis zones) and charging station location data (18 charging stations with four-port capacities). The proposed nonmyopic rebalancing heuristic reduces the cost increase compared with myopic rebalancing by 38%. Other managerial insights are further discussed.

Original languageEnglish (US)
Pages (from-to)654-676
Number of pages23
JournalTransportation Science
Issue number3
StatePublished - May 2022


  • carshare
  • electric vehicles
  • facility location
  • optimal policy
  • rebalancing

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A Node-Charge Graph-Based Online Carshare Rebalancing Policy with Capacitated Electric Charging'. Together they form a unique fingerprint.

Cite this