A node-charge graph-based online carshare rebalancing policy with capacitated electric charging

Viability of electric car-sharing operations depends on rebalancing algorithms. Earlier methods in the literature suggest a trend toward non-myopic algorithms using queueing principles. We propose a new model formulation based on a static node-charge graph structure into a p-median relocation problem with minimum cost flow conservation and path-based charging station capacities. The model is NP-complete, so a heuristic is proposed that ensures feasible intermediate solutions that can be solved for an online system. Assessment of the algorithm in computational tests suggest optimality gaps of 8-20% among the tested instances of up to 1000 nodes while achieving 20x computational time savings needed for online application. 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, 303 TAZs) and charging station location data (18 charging stations with 4 port capacities). Compared to the existing non-EV, no rebalancing data from BMW ReachNow, operating an EV fleet will obviously increase cost. Our proposed non-myopic rebalancing heuristic would reduce the cost increase compared to myopic rebalancing by 42%. Other managerial insights are further discussed.