In this research, we present a theoretical and computational framework for studying the vehicle routing problem with uncertain demands (VRPUD). We combine approaches in stochastic optimization and techniques in mixed integer programming to solve two main variants of the vehicle routing problem with uncertain demands. We first present a polyhedral study for deterministic heterogenous vehicle routing problems (HVRP) to develop a relatively efficient formulation such that its corresponding counterpart with uncertainty is tractable via mixed integer programming. Having assumed customers’ demand is uncertain, we apply three single-stage approaches within stochastic optimization to the HVRP with uncertain demands. The three-single stage approaches are chance constrained programming, Ben-Tal and Nemirovski, and Bertsimas and Sim robust optimization approaches. Then, we plug the corresponding formulation for each approach into a branch-and-cut method. Moreover, we propose a new framework within the branch-and-price framework to formulate the capacitated vehicle routing problem (CVRP) with uncertain demands. In addition to the three single-stage approaches, we apply a two-stage stochastic approach to the capacitated vehicle routing problem with uncertain demands. Our proposed framework enables us to model di↵erent types of uncertainty while the complexity of the resulting problem remains the same. Finally, we present extensive computational experiments for the deterministic HVRP, the HVRP with uncertain demands and the CVRP with uncertain demands. In the computational experiments we first investigate efficiency of several types of valid inequalities and lifting techniques for the deterministic HVRP. Then, using simulation and a scenario based technique we assess the performance, advantages and disadvantages of the aforementioned stochastic optimization approaches for the HVRP with uncertain demands and the CVRP with uncertain demands. We show that among single-stage approaches of stochastic optimization, those with control parameters outperform those without control parameters in terms of total expected cost. Also, we show that the higher protection level does not necessarily result in better solutions as higher protection levels may impose unnecessary extra costs. Moreover, as our computational experiments suggest, the two-stage models for the CVRP dominate the single-stage approaches for all protection level scenarios.