Fleet Sizing and Relocation Strategies for Shared Autonomous Vehicles under Uncertainty: A Two-Stage Robust Optimization Approach

Shared autonomous vehicles systems (SAVS) are regarded as a promising mode of carsharing service with the potential for realization in the near future. However, the uncertainty in user demand complicates the system optimization decisions for SAVS, potentially interfering with the achievement of desired performance or objectives, and may even render decisions derived from deterministic solutions infeasible. Therefore, considering the uncertainty in demand, this study proposes a two-stage robust optimization approach to jointly optimize the fleet sizing and relocation strategies in a one-way SAVS. We use the budget polyhedral uncertainty set to describe the volatility, uncertainty, and correlation characteristics of user demand, and construct a two-stage robust optimization model to identify a compromise between the level of robustness and the economic viability of the solution. In the first stage, tactical decisions are made to determine autonomous vehicle (AV) fleet sizing and the initial vehicle distribution. In the second stage, operational decisions are made under scenarios of fluctuating user demand to optimize vehicle relocation strategies. To enhance the efficiency of model resolution, the original two-stage robust optimization model is decomposed into separable subproblems, which are transformed using duality theory and linearization. An effective solution is achieved through a precise algorithm utilizing column-and-constraint generation (C&CG). Numerical experiments are conducted on a small-scale network to validate the effectiveness of the model and algorithm. Furthermore, adjustments to the demand fluctuation scenarios are made to assess the impact of uncertain budget levels Γ on the total revenue of SAVS. This research provides AV sharing service operators with an optimal relocation scheduling strategy that balances robustness and economic efficiency.