David Parker
Professor of Computer Science, University of Birmingham
[LPH21] Cheng Li, David Parker and Qi Hao. Optimal Online Dispatch For High-Capacity Shared Autonomous Mobility-on-Demand Systems. In Proc. IEEE International Conference on Robotics and Automation (ICRA'21), pages 779-785, IEEE. May 2021. [pdf] [bib]
Downloads:  pdf pdf (1.36 MB)  bib bib
Notes: The code for this paper is on GitHub: https://github.com/Leot6/AMoD2. The accompanying video is here: https://www.youtube.com/watch?v=zwD3mAn1qxE&t=2s.
Abstract. Shared autonomous mobility-on-demand systems hold great promise for improving the efficiency of urban transportation, but are challenging to implement due to the huge scheduling search space and highly dynamic nature of requests. This paper presents a novel optimal schedule pool (OSP) assignment approach to optimally dispatch high-capacity ride-sharing vehicles in real time, including: (1) an incremental search algorithm that can efficiently compute the exact lowest-cost schedule of a ride-sharing trip with a reduced search space; (2) an iterative online re-optimization strategy to dynamically alter the assignment policy for new incoming requests, in order to maximize the service rate. Experimental results based on New York City taxi data show that our proposed approach outperforms the state-of-the-art in terms of service rate and system scalability.