In many big cities all over the world taxis are an important means of travel. To assign incoming requests to taxis, the so called taxi dispatching, decisions have to be made fast, since there are over 200 requests coming in per minute, for instance in New York City. Not only because of this, but also with regards to maximizing the total expected profit, it is challenging to manage a taxi fleet. Automated decision support is needed to capture the stochastic and dynamic dimension of this problem.

In this work we model the Taxi Dispatching Problem as a dynamic program and present an approximate linear programming approach to solve it. We derive a deterministic linear program (LP) from the approximate LP and receive an upper bound on the exact value. The approximate LP, which is solved via column generation, yields a tighter upper bound. We start solving the approximate LP with a small subset of initial columns. New columns, that improve the solution, are determined and added to the program at each iteration.

We use New York City taxi data to evaluate the model. We focus on the comparison of the upper bounds and the convergence behavior of the objective value, considering the tailing-off effect of column generation.