Optimization under uncertainty has seen many applications in the industrial world. The objective of this paper is to study the stochastic dynamic vehicle allocation problem (SDVAP), which is faced by many trucking companies, container companies, rental car agencies and railroads. To maximize profits and to manage fleets of vehicles in both time and space, this paper has formulated a multistage stochastic programming based model for SDVAP. A Monte Carlo Sampling Based Algorithm has been proposed to solve SDVAP. A probabilistic statement regarding the quality of the solution from the Monte Carlo sampling method is also identified by introducing a lower bound and an upper bound of the obtained optimal solution. A five-stage experimental network was introduced for demonstration of this algorithm. The computational results indicated a solution of high quality when Monte Carlo sampling based algorithm is used for solving SDVAP, strongly suggesting that these algorithms can be used for real world applications for decision making under uncertainty.