Abstract
A stochastic formulation of the dynamic vehicle allocation problem is proposed. Two solution algorithms are developed, the first being a direct extension of the deterministic formulation and the second using the space-time structure of the network to describe the impact of decisions made now on future profits. The latter algorithm is shown to be significantly faster.