We develop a dynamic fleet scheduling model that demonstrates how a carrier can improve fleet utilization. The fleet scheduling model presented by Lee et al. (Eur J Oper Res 218(1):261-269, 2012) minimizes (1) a carrier's fleet size and (2) the penalty associated with the alternative delivery times selected. The model is static since requests are collected over time and processed together. In this paper we present a stochastic, dynamic version of the fleet reduction model. As demand is revealed throughout an order horizon, decisions are made in stages by sampling anticipated demand to avoid recourse penalties in later stages. Based on computational experiments we find the following:1. Modeling stochasticity improves the quality of solutions relative to the analogous model that does not include stochasticity. Counter-intuitively, an order lead-time distribution in which most loads are requested early can negatively impact optimal solution costs.2. The stochastic model produces good results without requiring prohibitively large numbers of demand scenarios.3. Consignees that place orders early in the order horizon are more often assigned their requested delivery times than those who place orders late.