Dynamic Inventory Relocation for a One-way Electric Car-Sharing System with Uncertain Demands

We introduce a stochastic inventory relocation problem for a one-way, station-based car-sharing system with electric vehicles (EV), in which customers' rental demands and rented vehicles' travel distances are uncertain and workers are hired to relocate vehicles between stations. To maximize the total expected profits that can be collected by the system, a worker must determine whether to relocate an EV, which vehicle to choose, and which station to move the EV to upon her arrival at a rental station. We formally model the problem as a Markov decision process (MDP). We investigate the existence of optimal policies for choosing vehicles to relocate. To overcome the computational challenges induced by the large state and action space, we propose an approximate dynamic programming approach based on an approximate value iteration (AVI) algorithm to learn the value of the post-decision states. We develop a state space aggregation scheme to improve the efficiency of the AVI algorithm, where we include both the temporal and spatial information on drivers and vehicles in the aggregated states. We demonstrate the capability of our modeling and solution approaches in making high quality decisions by comparing our dynamic policies with benchmark solutions. We also analyze the impact that different parameter settings have on the performance of our policies