CLC number: TU375

On-line Access:

Received: 2004-05-08

Revision Accepted: 2004-10-11

Crosschecked: 0000-00-00

Cited: 4

Clicked: 3722

DE LA CRUZ J.M., HERRÁN-GONZÁLEZ A., RISCO-MARTÍN J.L., ANDRÉS-TORO B.. Hybrid heuristic and mathematical programming in oil pipelines networks: Use of immigrants[J]. Journal of Zhejiang University Science A, 2005, 6(1): 9~19.

@article{title="Hybrid heuristic and mathematical programming in oil pipelines networks: Use of immigrants",

author="DE LA CRUZ J.M., HERRÁN-GONZÁLEZ A., RISCO-MARTÍN J.L., ANDRÉS-TORO B.",

journal="Journal of Zhejiang University Science A",

volume="6",

number="1",

pages="9~19",

year="2005",

publisher="Zhejiang University Press & Springer",

doi="10.1631/jzus.2005.A0009"

}

%0 Journal Article

%T Hybrid heuristic and mathematical programming in oil pipelines networks: Use of immigrants

%A DE LA CRUZ J.M.

%A HERRÁ

%A N-GONZÁ

%A LEZ A.

%A RISCO-MARTÍ

%A N J.L.

%A ANDRÉ

%A S-TORO B.

%J Journal of Zhejiang University SCIENCE A

%V 6

%N 1

%P 9~19

%@ 1673-565X

%D 2005

%I Zhejiang University Press & Springer

%DOI 10.1631/jzus.2005.A0009

TY - JOUR

T1 - Hybrid heuristic and mathematical programming in oil pipelines networks: Use of immigrants

A1 - DE LA CRUZ J.M.

A1 - HERRÁ

A1 - N-GONZÁ

A1 - LEZ A.

A1 - RISCO-MARTÍ

A1 - N J.L.

A1 - ANDRÉ

A1 - S-TORO B.

J0 - Journal of Zhejiang University Science A

VL - 6

IS - 1

SP - 9

EP - 19

%@ 1673-565X

Y1 - 2005

PB - Zhejiang University Press & Springer

ER -

DOI - 10.1631/jzus.2005.A0009

**Abstract: **We solve the problem of petroleum products distribution through oil pipelines networks. This problem is modelled and solved using two techniques: A heuristic method like a multiobjective evolutionary algorithm and Mathematical Programming. In the multiobjective evolutionary algorithm, several objective functions are defined to express the goals of the solutions as well as the preferences among them. Some constraints are included as hard objective functions and some are evaluated through a repairing function to avoid infeasible solutions. In the Mathematical Programming approach the multiobjective optimization is solved using the Constraint Method in Mixed Integer Linear Programming. Some constraints of the mathematical model are nonlinear, so they are linearized. The results obtained with both methods for one concrete network are presented. They are compared with a hybrid solution, where we use the results obtained by Mathematical Programming as the seed of the evolutionary algorithm.

**
**

. INTRODUCTION

The polyducts in a specific geographical area (region, country, etc.) are interlinked to form polyduct pipelines. To move the products, pumps are distributed strategically along the network. From an operative point of view, a polyduct network will be constituted by a set of nodes with storage capacity, and a set of edges (the polyducts) which interconnect the nodes. The edges are mostly unidirectional, but for reasons of operative flexibility, there can also be bidirectional edges. The network topology can be very varied, depending on the oil activity and geographical region conditions. The nodes, in general, will have the capacity to supply, store and receive products (De la Cruz et al.,

On a logistic level, the problem of polyduct pipelines is to plan the way different products are temporarily transported from source nodes to demand nodes, passing through intermediate nodes. Planning must satisfy a set of temporary constraints, related to the minimum and maximum dates for the delivery of different products. Also, constraints related to the products at the sources availability must be dealt with and the proper physical conditions after network utilization must be satisfied. The quality of the solutions to these problems is usually measured in terms of minimization of planning time, and the appropriate arrangement of the successive packages to obtain interfaces without mixing. This quality measurement is usually formulated as a multiobjective function of an optimization problem (Chankong and Haimes,

In this paper we present a solution to a simplified problem of the optimal distribution of products through pipeline networks using two methods, namely, Multiobjective Evolutionary Algorithm (MOEA) (Goldberg,

. MODEL OF THE NETWORK

Every source and intermediate connections may have different polyducts to different nodes and can deliver different products in different polyducts simultaneously.

We consider that the different products are delivered as discrete packages. There might be as many different types of packages as the number of different products. A unit package is the minimum fluid volume delivered by a source or intermediate node in unit time. Every sink and intermediate node have as many tanks as products it can receive, to store the different products. Also we can assume that the sources take the fluids from tanks. In order to simplify the problem we assume that all polyducts have the same diameter and characteristics.

We also assume that all packages flow with the same speed and that they occupy a similar volume in the polyduct. If two packages of different fluids follow one another there exists the possibility of both products becoming contaminated. In a number of polyducts the fluids may flow in both directions from one node to the other. One of the studied networks can be seen in Fig.

. HEURISTIC METHOD

To code the topology of the network we use a matrix having as entries the distance among the nodes (Botros et al.,

However, this codification does not necessarily fulfil the problem statement conditions yet, because the product type produced for each source could be different, and all the elements in the row vector solution are in the range [0, number of product types]. The easiest way to handle this aspect of the problem is to code, for each source, the types of oils from 1 to the number of different oils sent by that source (leaving the 0 for the case of not sending any product at that instant of time). This coding will not overload the genetic operators and the real type of oil coded in the individual must be obtained, before evaluating the individuals to obtain their fitness, by means of the ProductType variable.

For example, for the network of Fig.

This information coding can be kept easily in a structure where every row is a cell associated with a node, and within every row, there are as many columns as connections departing from this node. So the value of the gene acts as entry to get the product associated with it. In Matlab notation the representation of this information is as follows:

ProductType={[1 2];

[3 4];

[1 2 3 4];

[1 2 3 4]}

With this representation the products associated with the genes of the first node are:

ProductType {1}(1)=1;

ProductType {1}(2)=2;

and those of the second node are

ProductType {2}(1)=3;

ProductType {2}(2)=4;

and so on.

Instant | 1 | 2 | (( | 14 | 15 | ||||||||||||||||

Connection | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | (( | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 |

Gen | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | (( | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 |

Then, if we have Nind=20 individuals (with 8 connections and 15 time instants) we can use the mask to generate the initial population as follows (using Matlab notation):

Nconex=8;

Ninst=15;

Ngenes=Ninst*Nconex;

Nind=20;

mask=[2 2 4 4 4 4 4 4];

pop_aux=rand(Nind,Ngenes);

mask=repmat(mask,Nind,Ninst);

pop=round(pop_aux.*mascara);

Now, we explain the genetic operators used in the reproduction process:

probMut=0.008;

mutp=(rand(Nind,Ngenes)

pop_aux=rand(Nind,Ngenes);

mutated=round(mask.*pop_aux).*mutp;

new_pop=pop.*(˜mutp) + mutated;

The constraints are as follows:

It is necessary to satisfy a minimal production:

The tank capacity must not be violated:

packets of tank

Every destination must receive the amount of demanded packets:

destination

There must be no collisions of packets through a bidirectional pipe:

The arrival of a packet to a node must be at due time:

The objectives are as follows:

Minimize the number of product changes, or fragmentation:

Minimize the time it takes to verify the demand:

The MOEA implemented is schematised in Fig.

The algorithm begins with the creation of an initial population. Next some repairs are applied to these individuals and then the objective functions are evaluated and the population is ranked using the priority parameter given in Fig.

Finally we explain the priority scheme. The objective functions for each population are evaluated, and the population is ranked using the preferability relation given in Fig.

. MATHEMATICAL PROGRAMMING

satisfied in this time interval. For the network components

For the system variables and system parameters,

Auxiliary variables are needed to determine the different changes of product type that is made in each polyduct. In this way,

For constraint problem modelling, the standard network topology constraints are defined first, i.e., node balances in nodes and edge limits, later adding other dependent constraints directly to the treated problem characteristics, since they might be the product changes or conditions derived from polyduct bidirectionality (Magatão et al.,

In this case, the problem constraints can be classified by examining their linearity or nonlinearity (Schrijver,

Secondly, the balance constraint is defined in every network node, i.e., for each

In the third situation, the maximum and minimum transporting capacities are defined. Provided that the product transport is normalized, for each

Next, the constraint based on only one product entering a polyduct per time unit is defined, for each

The fifth point is that it is important to emphasize that a product will not leave the polyduct if it does not arrive at its destination, i.e., for each

To conclude the examination of linear constraints the fact that in bidirectional polyducts products scan only be sent in one direction should be considered. If a product, at a given moment in time

with

The sum is calculated for the first section of each polyduct in consecutive time periods. Being a function

when requiring that each

with

which the demand is satisfied

According to this equation, the system will try to fill up the storage facilities in the shortest possible time. The second component represents the product changes produced in the different polyducts. The system will reduce the sum of the changes to the lowest possible number.

When trying to achieve multiobjective optimization, different optimization methods are considered (Chankong and Haimes,

Let us suppose that

is added where

In the first case, the constraints are the ones specified in this section, while the optimization function is reduced to

In the second case, constraint is added, with the intention of reducing the feasible region.

. RESULTS

Node | Product type A |
Product type B |
Product type C |
Product type D |
||||||||||||

MIN TINI MAX DEM | MIN TINI MAX DEM | MIN TINI MAX DEM | MIN TINI MAX DEM | |||||||||||||

N1 |
0 | 20 | 35 | 0 | 0 | 30 | 35 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

N2 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 25 | 35 | 0 | 0 | 15 | 35 | 0 |

N3 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

N4 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

N5 |
0 | 0 | 20 | 5 | 0 | 0 | 20 | 5 | 0 | 0 | 20 | 5 | 0 | 0 | 20 | 5 |

N6 |
0 | 0 | 20 | 6 | 0 | 0 | 20 | 7 | 0 | 0 | 20 | 5 | 0 | 0 | 20 | 4 |

N7 |
0 | 0 | 20 | 9 | 0 | 0 | 20 | 18 | 0 | 0 | 20 | 15 | 0 | 0 | 20 | 6 |

Parameters | Value |

Number of individual | 21 |

Number of substitutions | 7 |

Number of generations | 12000 |

Crossover probability | 0.8 |

Number of cross points | 2 |

Probability of mutation | 0.008 |

For the recombination process we took one of the recombination methods provided by the Toolbox EVOCOM (Besada-Portas et al.,

The MOEA must obtain a set of solutions that satisfy the constraints of the problem, that is to say, possible solutions to the problem. Fig.

In this figure we can see a response to the priority scheme shown in Fig.

Once there are possible solutions of the problem, the next objective is to minimize the fragmentation of the shipments. The number of groups of packages sent by each node appears in Fig.

As the hard constraints are fulfilled after a few initial generations (over 1000 in this case) and

Once the upper bound for the time is fixed, five solutions with

Iterations | Fragmentation |

0 | 160 |

1000 | 91 |

2000 | 49 |

3000 | 44 |

4000 | 43 |

5000 | 41 |

The model had been solved using ILOG OPL (Van Hentenryck,

The final algorithm implementing this feedback given by the MILP solutions is shown in Fig.

As we can see, the algorithm consists of the periodical introduction of MILP solutions as immigrants in the MOEA population. In our case we introduce these solutions if the generation number is in the set of iterations shown in Table

If we run our network example for the three methods, the results obtained are shown in Fig.

Here, we can see the evolution of the fragmentation among the three methods. The surrounding points represent the iterations in which the immigration of solutions takes place. The hybrid algorithm solutions are better in all the time. Then, the hybrid method improves feasible solutions more quickly than the MOEA or MILP.

. CONCLUSION

The developed algorithm uses the knowledge of the problem to let the MOEA converge at an acceptable speed. This knowledge is introduced while designing the coding of the problem solutions and uses a repairing operator that modifies the working strategies which do not verify part of the constraints imposed by the network.

The implemented algorithm is flexible and can be used for different networks and problems specifications. While modelling the problems, several features are included in its definition to let the algorithm optimize a big range of networks. Any number of sources, intermediate nodes and destinies can be selected and bidirectional pipes are contemplated. Additionally, the types of products handled by each source can be different; the size and initial content of each storing tank for all the products, sources and intermediate nodes must be specified; and the correct time interval of products arrival in each destiny has to be defined.

The MOEA and the MILP solver can avoid local optimal solutions and yield similar results. We have implemented a hybrid algorithm that gives better optimal solutions in a shorter time of execution.

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou
310027, China

Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn

Copyright © 2000 - Journal of Zhejiang University-SCIENCE

Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn

Copyright © 2000 - Journal of Zhejiang University-SCIENCE

Open peer comments: Debate/Discuss/Question/Opinion

<1>