Neural Approximate Dynamic Programming for On-Demand Ride-Pooling

On-demand ride-pooling (e.g., UberPool, LyftLine, Grab-Share) 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 ridepooling, each (possibly partially filled) vehicle must be assigned a group of passenger requests with multiple different origin and destination pairs in such a way that quality constraints are not violated. 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 feasible assignments in future time steps. However, considering the future effects of an assignment that already has to consider what combinations of passenger requests can be assigned to vehicles adds an extra layer of combinatorial complexity on top of 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 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.