Petroleum allocation is an important link for the integration of petroleum supply chain at PETROBRAS as it is responsible for refining the strategic supply planning information to be used at the operation levels. In this work we describe how mathematical programming is being used to solve the petroleum allocation problem and we show the effectiveness of a local search method by optimization to solve real industrial problems. We propose a mixed-integer linear programming formulation of the problem that relies on a time/space discretization network. As the model cannot be solved for the industrial size instances of the problem, and not even a feasible solution can be found after 15 days of computation, we implement an algorithm based on a heuristic to find a feasible solution and on a local search procedure based on optimization to improve it. Using this algorithm. Solutions are found for all the case studies within 10% of optimality in less than 5 h. (C) 2009 Elsevier Ltd. All rights reserved.