Design and planning of petroleum supply chains (PSC) present significant opportunity as financial crunches and variability in crude oil prices continue augmenting volatility among the petroleum product prices, costs, margins and demand. To deal with this challenge, we present a stochastic mixed integer linear program (MILP) that maximizes the expected net present value (ENPV) while simultaneously minimizing a risk measure the conditional value-at-risk (CVaR) under demand uncertainty. The bi-objective MILP model determines the design decisions relating to installation, sizing and operation of infra-structures, the fair price strategic cost and tariffs and tactical decisions concerning periodic depot and route product affectations and inventory levels. Pareto optimal solutions are obtained for the retrofit network design of the Portuguese PSC, wherein computational results are presented and identified opportunities for further research.