This paper proposes a state-of-the-art branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands (VRPSD). We adapt the model of Christiansen and Lysgaard [Christiansen, H. C., and Lysgaard, J. A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters 37 (2007), 773–781.] and formulate the VRPSD as a set partitioning model with additional constraints. Feasible routes are generated using a dynamic programming algorithm executed over a state-space graph. Our method combines 2-cycle elimination with ng-routes. In addition, our pricing problem is significantly accelerated by the introduction of a new aggregate dominance rule. To speed up the generation of negative reduced cost columns, we use a tabu search heuristic and a bidirectional labeling algorithm. We also add capacity and subset-row inequalities dynamically in order to strengthen the linear relaxation of the master problem. As extensive computational tests illustrate, our algorithm is very competitive with the one of [Christiansen, H. C., and Lysgaard, J. A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters 37 (2007), 773–781.]. We manage to solve 20 additional instances from a 40-instance set and we considerably improve the computing times for instances already closed.