Abstract Dantzig and Fulkerson and later Bellmore et al. have shown that certain vehicle (tanker) scheduling problems can be formulated as minimum cost flow problems on a network. In this paper, the results of Dantzig and Fulkerson are extended to the case where more than one type of vehicle can be used in the determination of an optimal fleet. (In tanker scheduling terminology; how many small, medium and large tankers would form an optical fleet.) It is seen how the problem can be formulated as a modified transportation problem where flow in some arcs is conditioned to there being flow on certain other arcs. These “conditional” transportation problems were solved directly as linear programs and showed the peculiarity of terminating all integer in spite of having a constraint matrix, which does not satisfy the well known sufficient conditions for urimodularity. We discuss the implementation of the model and its empirical results.