  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 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,
303 traffic analysis zones (TAZs)) and charging station location data (18
charging stations with 4 port capacities). The proposed non-myopic rebalancing
heuristic reduces the cost increase compared to myopic rebalancing by 38%.
Other managerial insights are further discussed.

Data Structures and Algorithms;Computers and Society;Optimization and Control