EXPRESS: Fleet Repositioning for Vehicle Sharing Systems: Asymptotic Optimality of the Balanced Myopic Policy

Abstract We investigate the fleet repositioning problem aimed at dynamically optimizing vehicle distributions to maximize long-run average social welfare in a vehicle-sharing system. We model the problem as a Markov decision process under the ex ante committed decision scheme, characterizing the balanced myopic policy as optimal for the average reward setting. This policy efficiently aligns vehicle supply with trip demand and mitigates the curse of dimensionality, enhancing computational efficiency significantly. Our analysis demonstrates that although the balanced myopic policy operates with less information, potentially leading to performance losses, the maximum performance gap relative to the ex post decision scheme asymptotically converges to zero as the system size increases. This finding underscores the asymptotic optimality of the balanced myopic policy, particularly in large systems, making it a robust and effective solution for fleet repositioning. Moreover, we extend our investigation to settings with seasonal demand, confirming that a generalized balanced myopic policy remains optimal. Through comprehensive numerical experiments and a counterfactual case study of a real-world vehicle-sharing system, we quantify the operational value of our approach. This study not only validates the balanced myopic policy against more information-intensive solutions but also illuminates effective heuristic design strategies for improving the efficiency of fleet repositioning in vehicle sharing systems.