الگوریتم میکرو ژنتیک برای برنامه ریزی چند هدفه یک شبکه خط لوله در دنیای واقعی

The scheduling of activities to transport oil derivative products through a pipe network is a complex combinatorial problem that presents a hard computational solution. During the scheduling horizon, many batches are pumped from (or pass through) different areas. Pipes are shared resources. The balance between the demand requirements and the production campaigns, while satisfying inventory management issues and pipeline pumping procedures, is a difficult task. In order to reduce the complexity, this problem could be decomposed on three sub-problems according to the key elements of scheduling: assignment of resources, sequencing of activities, and determination of resource timing utilization by these activities. This work proposes a model to solve the sequencing and timing sub-problems, and its main objective is to develop a hybrid solution based on genetic algorithm (GA) and mixed integer linear programming (MILP) to drive batches of oil derivative products through the network. As both techniques (GA and MILP) can require significant computational efforts, we propose the use of micro-genetic algorithms (μGA)(μGA) that generally guarantee good solutions with acceptable levels of computational effort. The μGA-MILPμGA-MILP hybrid model has been implemented and tested on several practical cases of a Brazilian oil company. As a result, the model can provide a set of solutions that means different options of pipeline operations. This work contributes to the development of a tool to help the specialist solve the batch scheduling problem, which results in a more efficient use of the pipeline network.

Decision making problems arise in a variety of technical areas such as: logistics, finances, transportation, image processing, among others. In general these problems can be modeled as optimization problems with multiple objectives and constraints satisfaction and cannot be handled independently of the underlying optimizer. One approach to deal with these problems has been based on integer/linear programming methods. An alternative approach to deal with multi-objective optimization problems can be the use of meta-heuristic methods, where the guarantee of finding optimal solutions is sacrificed for the sake of getting good solutions in a limited computational time (Hertz and Widmer, 2003). Meta-heuristics are iterative methods that are not dedicated to solving a particular problem but are rather designed to handle as many different combinatorial problems as possible (Hertz and Widmer, 2003). Besides, a good meta-heuristic implementation is likely to provide a near-optimal solution to complex combinatorial problems in a suitable computational time. As black-box optimization methods, meta-heuristics can be directly applied to complex real-world problems with relatively few modifications (Dreo et al., 2006). Currently, an increasing number of researchers are investigating the possibility of combining meta-heuristics with other optimization techniques in order to deal with real-world and large-scale problems. Some of these combinations hybridize meta-heuristics with constraint programming, tree search techniques, mixed integer program and others. The resulting hybrid meta-heuristics can provide a more efficient behavior and a higher flexibility tool than the root techniques (Blum et al., 2011). Moreover, the use of hybrid meta-heuristics to tackle multiple objective optimization problems has grown giving birth to many ideas to solve real problems (Ehrgott and Gandibleux, 2008). In this context, this paper addresses the problem of a short-term scheduling in a real-world pipeline network by using hybrid meta-heuristics based on genetic algorithm (GA) and mixed integer linear programming (MILP). The distribution and transportation of oil refined products involve decisions where time varies from hours (short-term type) to months. Decisions include production and operation planning and scheduling, inventory management, transportation network utilization and others (Magalhaes, 2004). This decision making process characterizes a multiple objective optimization problem. Recently, remarkable efforts have been made to model pipeline scheduling problems by means of MILP techniques. Most published works only model a single pipeline connecting a source to one or several destinations (Magatao et al., 2004, Magatao et al., 2011, Relvas et al., 2006, Relvas et al., 2007, Cafaro and Cerda, 2008, Cafaro and Cerda, 2010 and Rejowski and Pinto, 2008). Only a few solve the scheduling problem to a pipeline network characterized by several pipeline branches, refineries, harbors, distribution centers and intermediate nodes (depot) (Neves et al.,, Lopes et al., 2010, Boschetto et al., 2010 and Boschetto et al., 2012). Due to the computational drawbacks of the MILP models, such as large amounts of continuous and integer variables to compute, all of the mentioned works apply decomposition techniques (structural or temporal decomposition) to solve the planning and scheduling problems in reasonable computational times. Despite the use of decomposition techniques, several simplifications are also carried out in order to achieve a feasible solution to the network scheduling problem. A good review of recent applications for short-term scheduling in oil supply chain problems can be found in Relvas et al. (2006) and Boschetto et al. (2012). According to these authors, the comparison among different approaches has been difficult because each problem considers different network configurations with different restrictions. Besides, unrealistic simplifications are done to deal with real situations. These simplifications are quite restrictive since they reduce the practical application and performance of models. In addition, an important conclusion from published works is that the use of decomposition approaches or even the use of other types of techniques (such as heuristics or meta-heuristics) to overcome problem complexity are relevant solutions. Concerning the first solution, we have proposed a decomposition approach to address pipeline scheduling problems (Neves et al., 2007). In this previous paper, the problem is decomposed into a hierarchy of sub-problems based on the three key elements of scheduling: assignment of resources, sequencing of activities and determination of timing for resources used by these activities (Neves et al., 2007). Each problem was solved separately by an appropriate technique. The assignment problem and the sequencing problem used constructive heuristics based on expert knowledge of network operation, and the timing solution was obtained with a MILP model (Neves et al., 2007). However, the sequencing of batches is a multi-objective problem, which includes the production and demand forecasts, the storage, and a list of transporting products priorities. Finding a solution for this multi-objective problem is a very difficult task due to conflicts between the objectives and the size of the network. In general, the network scheduler cannot easily propose several sequences of batches to transfer. They usually choose solutions (sequence) that solve the problem (transfer), without considering if there is a better or a cheaper alternative. Concerning the use of meta-heuristics, some papers have solved pipeline scheduling problems by using genetic algorithm. Crane et al. (1999) have presented the first GA based model to pipeline scheduling. The studied network is a small one composed of eight nodes with a limited capacity to store products and is connected by seven unidirectional pipes. The optimal solution for this problem was obtained, thus showing the possibility of solving scheduling problems by applying the genetic algorithm. A model for multi-objective optimization based on GA with constraints is proposed in Cruz et al. (2003) to the problem of petroleum products distribution through a pipeline network (two refineries, two intermediate depots, three final clients and 10 pipelines). The two objectives to be accomplished are the demand of products in minimum time and minimizing interface between different products. The same multi-objective problem is modeled and solved by means of a multi-objective rank niching genetic algorithm (RNGA) in Westphal et al. (2007). In this paper, apart from both original objectives (minimizing scheduling time and number of interfaces) two other objectives are accomplished: maximizing the volume of batches and the removal of products from the refineries. Both the same objective problems in Cruz et al. (2003) were also solved by means of a multi-objective genetic algorithm (MOGA) model, a MILP model and a hybrid model that combines MILP and GA techniques in Garcia et al. (2004). The performances of the three methods were compared and the authors have concluded that the hybrid method computed better solutions in a shorter time than both original techniques. Based on such results, Arruda et al. (2010) developed a MOGA model applied to the network (three refineries, one harbor, five final clients and 15 pipelines) in Neves et al. (2007). However, the model has presented a computational burden that limited its use to examples with a limited number of batches. Despite the fact that genetic algorithms can be very robust and easy to be implemented, the computational efficiency of GA methods, especially multi-objective genetic algorithm (MOGA) methods, have limited their use to small pipeline network and/or small examples as shown in the works previously mentioned. The two main processes that require computational time in a MOGA algorithm are: the ranking of the population that requires a mechanism for comparison among all individuals to determine their dominance and a mechanism to maintain diversity in order to avoid the premature convergence of the algorithm to a super individual (Coello, 2003). In order to circumvent these problems, a class of methods, named micro-genetic algorithms (μGA)(μGA), has been proposed in the literature. These methods use a genetic algorithm with a small population and a restart process with an external memory to store the non-dominated solutions previously found (Coello, 2003). In this context, this paper presents the development of a hybrid optimization model based on micro-genetic algorithm (μGA)(μGA) and mixed integer linear programming (MILP) that help schedule activities of a pipeline network in the Brazilian oil industry. The proposed μGAμGA uses the MILP model proposed in Boschetto et al. (2010) to rank the population. Based on this rank, it also combines a non-dominated sorting procedure with a technique of niche formation and speciation in order to maintain several different solutions for an infinite period of time in relation to population size, thereby ensuring the diversity of the population. The developed hybrid model is used to calculate the scheduling of a distribution network which transports oil refined products and ethanol having high-aggregated value from refineries and harbors to distribution centers. The goal of the proposed model is to support the decision-making process, which is particularly complex due to the existence of many areas and pipes subject to particular operational constraints. The remainder of the paper is organized as follows: the pipeline network and the batch sequencing sub-problem description are presented in Section 2; a description of the micro-genetic algorithm (μGA)(μGA) is detailed in Section 3; the hybrid solution to the sequencing problem is explained in Section 4. Illustrative instances of a real-world scenario are given in Section 5 and the concluding remarks are presented in Section 6.

We have developed a μGA-MILPμGA-MILP hybrid model for sequencing batches in a pipeline network scheduling problem. The proposed approach has been tested with real-world scenarios from Brazilian Oil Company. The case studies cover time horizons over a period of a month and involve scenarios with 48 batches, as well as complex scenarios containing 367 batches. The several criteria (objective functions) used to put the batches in order take operational characteristics of the network into account, such as inventory constraints and production/demand profiles (associated to time windows), presence of interface among products, and others. Since the ordered sequence of pumped products has an important impact over the final short-term scheduling, the heuristic used by the expert to put the batches in order can fail for particular cases. This way, the solutions computed by the μGAμGA model can be an alternative to support scheduler's decisions. In general, the μGAμGA model has obtained satisfactory solutions with a reduction in the number of time window violations at a low computational cost. Furthermore, the results of the model can present a better level of inventory during the time horizon or reduced product interfaces when compared to the expert solution. When compared to other MOGA model, the results computed by the developed μGAμGA model are similar in terms of quality of solutions, total number of computed non-dominated solutions and solution spread over the Pareto frontier. The computational time of the μGAμGA model is much smaller than the MOGA model for all studied scenarios. However, the fitness function used by both models is based on the solution of a MILP model whose computational time grows with the scenario complexity. This fact may prevent the use of GA models by the company schedulers, even those with small populations such as the model proposed in this work. Nevertheless, the presented results enable the combination of a MILP model with μGAμGA model to deal with real-world and large-scale problems. This is only possible due to three factors. First, the fitness assignment of the hybrid model is based on the weighted sum method that converts a multi-objective problem into a single-objective one. Second, the proposed μGAμGA model has a small population that reduces the computational burden of the ranking procedure. Finally, the use of a reset mechanism combined with niche techniques and elitist strategies assures the convergence of the μGA-MILPμGA-MILP hybrid model to the Pareto frontier and the quality of the obtained solutions. In conclusion, for future reference, a more detailed study and formulation will be carried out according to two guidelines. The first one has the main goal to obtain optimized sequences with other operational criteria such as “minimizing the time delay of batches” or “minimizing pipeline breaks”. The other guideline is related to the computational burden. We are looking for a new way to compute fitness functions in order to reduce the computational time without loss of quality of solutions. In fact, we are looking for a way to parallelize the computation of the MILP timing model associated to each individual in the μGAμGA population.