Petroleum Supply Chains (PSC) networks are complex organizations, strongly affected by competition, environmental regulation and market uncertainty. To improve profits and reduce costs and risks, companies may use mathematical programming for strategic, tactical and operational planning. The current paper identifies the research opportunities and presents our contributions with respect to the strategic and tactical planning of multiple entity, echelon, product, and transportation PSCs, under the context of crude costs, product prices, and customer demand uncertainties. In order to address these gaps, four mixed integer linear programming (MILP) models were developed, namely the individualistic, collaborative, multi-objective stochastic, and robust optimization MILPs. A detailed pricing structure and a piecewise linearization function determine the collaborative economy of scale multi-entity costs, tariffs and prices per route, location and product. A stochastic programming MILP integrates an augmented ϵ -constraint algorithm to simultaneously maximize the expected net present value (ENPV) and minimize risk represented through selected measures. The robust optimization MILP optimizes the worst-case profits considering the crude costs, product prices, and customer demand uncertainties. Test results are presented for the Portuguese downstream PSC.