300,000 to 500,000 cab rides arise every day in New York. Conducted by roughly 30,000 taxi drivers and mostly allocated by taxi dispatchers. To allocate and to reposition the taxis, the future positions of the cabs and the expected value of these future positions needs to be considered. The target is to create an automated method, which provides decision support in real-time and incorporates stochastic information and expectations.

In this talk we define and solve the taxi dispatching problem as a stochastic dynamic resource allocation problem (SDRAP). Due to the large number of states, results, and actions we use an approximate dynamic programming approach (ADP). Our solution strategy is sampling-based and solves network flow problems as LP for each discrete point in time. Using the duals of the underlying LP solutions, we estimate concave value functions via reinforcement learning techniques within the simulation to predict future revenue and incorporate these functions into the model.

We perform evaluations on historical taxi trip records from Manhattan provided by the New York City Taxi and Limousine Commission. In our experiments, we compare different value function approximations, parameter settings and instance sizes. Compared to myopic policies our method leads to an increase of roughly 60% in revenue due to a higher utilization of cabs and roughly 90% less waiting cabs. In addition, we estimate well performing value functions and transfer them into heat maps. All in all, the optimization and decision support can be realized in real-time for realistic taxi data instances.