The problem tackled in this work consists of: given a set of production platforms; a set of terminals; a set of refineries; a set of tanker classes; the daily oil production of each platform; the consumption campaign of each crude distillation unit in refineries; the logistic infrastructure restrictions, namely, the storage capacity of production sites, terminals, and refineries, maximum pipeline flow rate between terminals and refineries, number and transportation capacity of tankers available in each tanker class, number of tankers that can operate simultaneously in each terminal. Determine, for a horizon of two months, a minimum cost offloading scheduling of each platform in order to supply each refinery with the correct type and amount of oil indicated by the strategic planning.
Our first approach to solve this problem was to build a straightforward fixed-charge network model relying on a daily discretization of the time horizon [1]. This model was important to point out the part of the model that deserves a special attention in terms of formulation, specifically, the offloading scheduling of platforms. We propose a reformulation of the inventory constraint at platforms that basically consist of projecting this constraint onto all variables but the stock variables. Even tough the original constraint and the reformulation are equivalent in terms of their Linear Programming relaxation, the latter is more suitable in an integer programming framework as it embodies a cascade knapsack constraint structure and can be better exploited by the solvers commercially available. In addition, we propose a splitting of offloading variables in order to impose a hierarchical branching on variables.
Despite the effort to tight the formulation, we observe that the lower bound obtained is quite weak due to the economies of scale, i.e., the cost per volume decreases as the ship capacities increase, hence the linear relaxation tends to use fraction of a possible bigger ship available instead of trying a smaller ship or a whole bigger ship. Studying the structure of this part of the problem, we devise some valid inequalities reasoning on the minimum and maximum storage capacity of the each platform. The results motivate us to take a step further and develop some tighter inequalities. Firstly, we can show that Chvatal inequalities rank 1 [2], which can be derived directly from the inventory constraint reformulated, dominate the valid inequalities. Moreover, using PORTA[3] we observe that the facet of the polyhedron of integer points associated with the inventory constraint at the platforms can be obtained by lifting the former valid inequalities proposed. In order to obtain lifted valid inequalities, we develop an approximate algorithm that combine inequalities derived for each class of ship. This last idea helps to speed up the solution process at the cost of the addition of a few more inequalities.
Another solution approach followed in this work is the decomposition algorithm. This problem can be viewed as the interaction between of an offloading scheduling platform problem and a refinery supply scheduling problem. The literature has been reported in the last two decades successful results using decomposition algorithms to solve large scale problems, among the most cited technique we can mention Lagrangean and Benders Decompositions [4,5]. In this work we propose a new decomposition algorithm that resembles in some aspects the Benders decomposition algorithm. It is well known in the literature that generate Benders cuts from an integer sub-problem remains a challenge and recently some promising ideas have been presented to overcome this difficult. Our decomposition algorithm relies in the idea of decomposing the problem by copying variables, and instead of generating cuts using some straightforward ideas, e.g., Combinatorial cuts (no-good constraints) or Benders cuts, we apply disjunctive programming theory to derive them. We prove that this approach of generating cuts is most effective than the Combinatorial cuts and preliminaries results show that this method is a viable alternative especially when the instance size grows.
Our algorithm was tested on test instances of the problem involving 10 platforms, 9 tanker types, 8 maritime terminals, 11 refineries, and 20 distillation units over a time horizon of 72 discretized intervals. The typical instance size is approximately 27,000 binary variables, 56,000 continuous variables, and 42,000 constraints.
References
[1] Aires, M., Lucena, A., Rocha, R., Santiago, C., Simonetti, L. (2004). Optimizing the Petroleum Supply Chain at PETROBRAS. In Proceedings of the ESCAPE 14. Lisbon, Portugal.
[2] Chvatal, V. (1973). Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics 4, 305-337
[3] T. Christof, A. LÄobel, PORTA - POlyhedron Representation Transformation Algorithm,
http://www.zib.de/Optimization/Software/Porta/.
[4] Yan H. (1996). Solving some difficult mixed-integer programming problems in production and forest mmanagement. PhD. Thesis Dissertation, University of Pennsylvania.
[5] Binato S., Pereira M.V.F., Granville S. (2001). A new Benders Decomposition approach to solve power transmission network design problems. IEEE Transactions on Power Systems, 16, 235-40.