Real-time dispatch management of shared autonomous vehicles with on-demand and pre-booked requests

Autonomous vehicle technology is poised to revolutionize shared vehicle systems, offering the potential for increased efficiency and convenience. To better devise management strategies for shared autonomous vehicles, this paper addresses a real-time dispatch problem with hybrid requests, where on-demand (immediate) and pre-booked (reserved) trip requests coexist. The coexistence of these two types of request behaviors introduces considerable complexity to real-time dispatch due to the uncertainty in trip demand. We design an approximate dynamic programming (ADP) approach for making vehicle–trip assignments and vehicle relocation decisions. We first formulate the real-time vehicle dispatch problem as a dynamic program and decompose it into time-staged subproblems. To effectively handle the high-dimensional state space, we replace the value functions with tractable approximations and propose a piecewise-linear functional approximation method that captures the spatiotemporal value of vehicles. To calibrate the parameters in the approximations, we propose DualT and DualNext algorithms to provide precise dual information, thereby enhancing the accuracy of our approach. Furthermore, we propose a lookahead strategy that incorporates pre-booked request information into the ADP approach for improving real-time decision-making. We validate the effectiveness of the ADP approach through numerical experiments conducted using taxi data from Brooklyn, New York. The ADP approach outperforms benchmark policies in solution quality while maintaining computational efficiency, and the incorporation of the lookahead strategy significantly enhances the performance of the ADP approach, yielding substantial improvements. Numerical results demonstrate that integrating pre-booked requests into vehicle dispatch management can greatly enhance the system efficiency.