Common carrier operations, including truckload trucking, less- than-truckload trucking, rail and ocean container, are playing increasingly important roles in the manufacturing and production process. These carriers are, for the most part, being asked to provide an even higher quality of service for an even lower cost for shippers using their standard services. This pressure has been combined with a substantial increase in the size of the largest carriers, complicating the overall operation. A common mathematical foundation is developed which focuses on dynamic fleet management under forecasting uncertainties, which is formulated as a network with random arc capacities (representing market demands). A novel solution strategy is used, extending similar research developed for stochastic models of truckload operations. The core of the research is on the solution of stochastic, dynamic models arising in fleet management problems, and the development of approximation methods for stochastic programs that allow the solution of large, real-world problems. Extensive empirical testing in a simulation environment is planned.