Neural approximate dynamic programming for on-demand ride-pooling

• Main Authors: SHAH, Sanket, LOWALEKAR, Meghna, VARAKANTHAM, Pradeep
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Approximate dynamic programming; Approximate value function; Assignment problems; Combinatorial complexity; Integer linear programs; Origin and destinations; Transportation problem; Numerical Analysis and Scientific Computing; Operations Research, Systems Engineering and Industrial Engineering; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/5992; https://ink.library.smu.edu.sg/context/sis_research/article/6995/viewcontent/5388_Article_Text_8613_1_10_20200511.pdf
• Institution: Singapore Management University

On-demand ride-pooling (e.g., UberPool, LyftLine, GrabShare) has recently become popular because of its ability to lower costs for passengers while simultaneously increasing revenue for drivers and aggregation companies (e.g., Uber). Unlike in Taxi on Demand (ToD) services – where a vehicle is assigned one passenger at a time – in on-demand ride-pooling, each vehicle must simultaneously serve multiple passengers with heterogeneous origin and destination pairs without violating any quality constraints. To ensure near real-time response, existing solutions to the real-time ride-pooling problem are myopic in that they optimise the objective (e.g., maximise the number of passengers served) for the current time step without considering the effect such an assignment could have on assignments in future time steps. However, considering the future effects of an assignment that also has to consider what combinations of passenger requests can be assigned to vehicles adds a layer of combinatorial complexity to the already challenging problem of considering future effects in the ToD case. A popular approach that addresses the limitations of myopic assignments in ToD problems is Approximate Dynamic Programming (ADP). Existing ADP methods for ToD can only handle Linear Program (LP) based assignments, however, as the value update relies on dual values from the LP. The assignment problem in ride pooling requires an Integer Linear Program (ILP) that has bad LP relaxations. Therefore, our key technical contribution is in providing a general ADP method that can learn from the ILP based assignment found in ride-pooling. Additionally, we handle the extra combinatorial complexity from combinations of passenger requests by using a Neural Network based approximate value function and show a connection to Deep Reinforcement Learning that allows us to learn this value-function with increased stability and sample-efficiency. We show that our approach easily outperforms leading approaches for on-demand ride-pooling on a real-world dataset by up to 16%, a significant improvement in city-scale transportation problems.