In this thesis we investigate the investment planning problem for the petroleum supply chain under demand uncertainty. We formulate and solve a two-stage stochastic programming model that seeks to accurately represent the particular features that are inherent to the investment planning for the petroleum logistics infrastructure. The incorporation of uncertainty in this case inevitably increases the complexity of the problem, which becomes quickly intractable as the number of scenarios grows. We circumvent this drawback by relying on Sample Average Approximation (SAA) to control the number of scenarios required to reach a prespecified level of tolerance regarding solution quality. We also focus on efficiently solving the stochastic programming problem, exploiting its particular structure by means of a scenario-wise decomposition. Following this idea, we propose two novel approaches that focus on decomposing the problem in a way that it could be efficiently solved. The first algorithm is based on stochastic Benders decomposition, which we further improve by using new acceleration techniques proposed in this study. The second is a novel algorithm based on Lagrangean decomposition that was designed to deal with the case where we have integer variables in the second-stage problem. The novel feature in this algorithm is related with the hybrid strategy for updating the Lagrange multipliers, which combines subgradient, cutting-planes and trust region ideas. In both cases, we have assessed the proposed approaches considering a large-scale realworld instances of the problem. Results suggests that they attain superior performance.