Charging Station Location and Fleet Sizing for Shared Autonomous Electric Vehicles using Benders’ Decomposition

The emergence of shared autonomous electric vehicle fleets, which are coordinated to serve passenger travel demand, is expected to yield substantial societal and environmental benefits. The operations of shared autonomous electric vehicle systems requires the coordination of recharge trips and rebalancing trips in between passenger trips. Thus, the design of the charging infrastructure is key to the efficiency of the system. We address the charging station location problem for shared autonomous electric vehicle systems. We present a novel strategic planning approach for charging station location and shared autonomous electric vehicle fleet sizing building upon the minimum-drift-plus-penalty dispatching policy for shared autonomous electric vehicles that is proven to achieve maximum throughput under stochastic demand. The throughput that can be achieved is a function of charging station locations and fleet sizing decisions, which we strategically optimize here. We exploit the structure of the problem to derive several classes of valid inequalities that aim to strengthen the formulation. We develop Benders’ decomposition approaches to enhance the tractability of the solution methods. We conduct numerical experiments on three publicly available transportation networks to investigate the computational performance of four algorithmic configurations. We also conduct sensitivity analyses on problem data including demand, vehicle battery range, fleet cost and the maximum number of chargers available. Our findings show that the derived valid inequalities have a significant impact on reducing computational runtime. Furthermore, we observe that embedding on-the-fly valid inequalities in a Benders’ decomposition algorithm can help in improving efficiency.