Approximate dynamic programming for multi-period taxi dispatching

Resource type
Felix Goetzinger, Anne Meyer, Martin Pouls
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 positions need to be taken into account. The target is to provide 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 real world data consisting of historical taxi trip records from Manhattan provided by the New York City Taxi and Limousine Commission. The instances contain over 500 taxis, 50 locations, and 450 time steps per day. In our experiments, we compare different value function approximations, parameter settings and instance sizes regarding the numbers of vehicles. 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 to heat maps. All in all, the optimization and decision support can be realized in real time for realistic taxi data instances.
Research focus
Logistics and Supply Chain Optimisation
Logistikoptimierung für die PTV Group
Download .bib
Download .bib
Published by
Martin Pouls