In dynamic fleet management, a company operates a fleet of vehicles to provide transportation services between given locations, while customers request trips randomly over time. Each vehicle can transport one customer at a time. The fleet operator may dispatch a loaded vehicle, i.e., service a request, or an empty vehicle, i.e., reposition it at a cost for possible future demand. The optimization problem at hand essentially consists in finding a dynamic dispatching strategy so as to maximize total expected profit. The problem has applications, for instance, in taxi routing and in full truckload services. It can be cast as Markov decision problem (MDP). The corresponding value function, however, is intractable due to a high-dimensional state space. The latter fact motivated previous works to tackle this MDP by approximating the value function, also known as approximate dynamic programming (ADP). We devise a new value function approximation for the dynamic fleet management MDP based on linear programming. That is, we employ an affine approximation scheme to derive a relaxation. The relaxed model is a large-scale LP that can be solved via column generation. As a result, we obtain an affine approximation of the original value function. To evaluate our approach, we use real-world taxi trips from the well-known New York City taxi data set. We present numerical results that are concerned with the computational efficiency of our approximation procedure and with the quality of dispatching policies which can be derived from this affine value function approximation.