Skip to main content

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

Author(s): Al-Kanj, L; Nascimento, J; Powell, William B

To refer to this page use:
Abstract: 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.
Publication Date: 2020
Citation: Al-Kanj, L, Nascimento, J, Powell, WB. (2020). Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles. European Journal of Operational Research, 284 (1088 - 1106. doi:10.1016/j.ejor.2020.01.033
DOI: doi:10.1016/j.ejor.2020.01.033
Pages: 1088 - 1106
Type of Material: Journal Article
Journal/Proceeding Title: European Journal of Operational Research
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.