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 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.