Hierarchical value decomposition for effective on-demand ride pooling

• Main Authors: JIANG, Hao, VARAKANTHAM, Pradeep
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: Ride Pooling; Neural Approximate Dynamic Programming; Reinforcement Learning; Value Decomposition; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/7096; https://ink.library.smu.edu.sg/context/sis_research/article/8099/viewcontent/HIVES.pdf
• Institution: Singapore Management University

On-demand ride-pooling (e.g., UberPool, GrabShare) services focus on serving multiple different customer requests using each vehicle, i.e., an empty or partially filled vehicle can be assigned requests from different passengers with different origins and destinations. On the other hand, in Taxi on Demand (ToD) services (e.g., UberX), one vehicle is assigned to only one request at a time. On-demand ride pooling is not only beneficial to customers (lower cost), drivers (higher revenue per trip) and aggregation companies (higher revenue), but is also of crucial importance to the environment as it reduces the number of vehicles required on the roads. Since each vehicle has to be matched with a combination of customer requests, the matching problem in ride pooling is significantly more challenging. Due to this complexity, most existing solutions to ride-pooling problem are myopic in that they either ignore future impact of current matches or the impact of other taxis in the expected revenue earned by a taxi. In this paper, we build on an approximate dynamic programming framework to consider impact of other taxis on the value of a taxi (expected revenue earned until end of horizon) through a novel hierarchical value decomposition framework. On a real world city scale taxi data set, we show a significant improvement of up to 10.7% in requests served compared to existing best method for on-demand ride pooling.