Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles

We address a comprehensive ride-hailing system taking into account many of the decisions required to operate it in reality. The ride-hailing system is formed of a centrally managed fleet of autonomous electric vehicles which is creating a transformative new technology with significant cost savings. This problem involves a dispatch problem for assigning riders to cars, a surge pricing problem for deciding on the price per trip and a planning problem for deciding on the fleet size. We use approximate dynamic programming to develop high-quality operational dispatch strategies to determine which car is best for a particular trip, when a car should be recharged, when it should be re-positioned to a different zone which offers a higher density of trips and when it should be parked. These decisions have to be made in the presence of a highly dynamic call-in process, and assignments have to take into consideration the spatial and temporal patterns in trip demand which are captured using value functions. We prove that the value functions are monotone in the battery and time dimensions and use hierarchical aggregation to get better estimates of the value functions with a small number of observations. Then, surge pricing is discussed using an adaptive learning approach to decide on the price for each trip. Finally, we discuss the fleet size problem.