There are important interactions between decisions on sizing a vehicle fleet and decisions on utilizing that fleet. A model is formulated to optimize both sets of decisions simultaneously under dynamic and uncertain conditions. A network approximation to this model is presented and a solution procedure proposed. The convergence behavior of the solution procedure and the potential consequences of using simpler models to solve the fleet sizing and vehicle allocation problem are illustrated using several hypothetical problems. We conclude that this model is useful in identifying good strategies for the sizing of vehicle fleets and for the allocation of empty vehicles.