# A MILP Model for the Scheduling of a Multiproduct Tree-Structure Pipeline Network in Mining Industry

Meryem Bamoumen, Selwa Elfirdoussi, Libo Ren, Nikolay Tchernev

► To cite this version:

Meryem Bamoumen, Selwa Elfirdoussi, Libo Ren, Nikolay Tchernev. A MILP Model for the Scheduling of a Multiproduct Tree-Structure Pipeline Network in Mining Industry. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.299-306, 10.1007/978-3-030-85906-0_34. hal-03775608

HAL Id: hal-03775608

https://hal.science/hal-03775608v1

Submitted on 12 Sep 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# A MILP model for the scheduling of a multiproduct tree-structure pipeline network in mining industry

M. BAMOUMEN¹[0000-0002-0588-5982], S. ELFIRDOUSSI¹[0000-0002-2110-2482],
L. REN²[0000-0003-3506-0399], N. TCHERNEV³[0000-0002-7288-1076]

¹ EMINES School of Industrial Management, Université Mohammed VI Polytechnique, Ben Guerir, Morocco
{Meryem.Bamoumen, Selwa.Elfirdoussi}@emines.um6p.ma

² CRCGM EA3849, Université Clermont Auvergne, France
libo.ren@uca.fr

³ LIMOS, UMR CNRS 6158, Université Clermont Auvergne, France
nikolay.tchernev@uca.fr

**Abstract.** The scheduling of multiple products through pipelines, to meet a demand over a considered time horizon, is a challenging problem that many researchers have been interested in. Although pipelines are considered mainly in the petroleum industry, they can also be used in other industries. This paper deals with the multiproduct pipeline network scheduling problem in the context of mining industry. The objective is to schedule a sequence of batches, to be transported through the pipeline network, to ensure all product demand, while respecting the different technical constraints. The proposed approach is a MILP model with a continuous representation of time and batch volume. It provides maximizes the volume of batches to satisfy all product demands. The model was tested using different instances over a short-term horizon.

**Keywords:** pipeline network, phosphate products, scheduling, MILP.

# 1 Introduction

## 1.1 Research context

The use of pipelines to transport petroleum products has increased significantly during the last few years, as they are considered to be the most reliable and safe way to move these products [6]. Although pipelines are mainly related to petroleum industries, this paper presents a system composed of multiple pipelines used in the mining industry. The considered pipeline network transports phosphate products, which are produced by the Moroccan firm “OCP Group”. In fact, phosphate is transferred through the pipelines by mixing phosphate grains with water to obtain “phosphate slurry”, which is considered a homogenous liquid product. Phosphate slurry is characterized by its Bone Phosphate of Lime (BPL) composition, storage capacity and demand during a fixed time horizon. Therefore, the system considered is destined to transport multiple products. This transportation is achieved by pumping a sequence of batches from the source point
to the different destinations. Each batch is composed of one product and has a volume
which is comprised between an upper and a lower bound. In order to identify each batch
during the unloading phase at the destination points, each two successive batches are
separated by injecting a volume of water.

In this paper, we tackle the multi-product pipeline network scheduling problem in mining industry. The objective is to determine the schedule of batches to be pumped and transported through the pipelines to satisfy the demand on a predefined time-horizon, by taking into consideration different technical constraints, while maximizing the amount of product to be delivered. We propose a Mixed Integer Linear Program (MILP) model with a continuous time and volume formulation to study this problem.

## 1.2 Problem definition

The system under study is the pipeline network of “OCP Group” (see Fig. 1) a tree-
structure type network, and consists of a multi-product main pipeline that connects a
source “Head Station” to several destinations using secondary pipelines. The first des-
tination is for local customers, and the second destination is referred to as “Down-
stream” unit, which delivers phosphate products to international customers.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Pipeline network of “OCP Group”</figcaption></figure>

There exist eight different products: one local product delivered to the local customers and seven export products, which are delivered to international clients via the Downstream unit. These products are unloaded in different tanks organized in groups at the “Terminal Station”: the local product is unloaded in the “local group” and the “export 1 group”, due to its high demand; the “export 2 group” is shared by the export products, where each tank can contain only one product at a time. If the export product to be unloaded has a higher BPL composition than the previous one contained in a tank, then a flushing operation occurs: a volume of the product with the high BPL is added to the previous product to avoid any contamination. Based on the demands from local customers and those received by Downstream from international customers over a predefined planning horizon, the objective is to provide the scheduling of batches to meet
these demands, while maximizing the volume of the planned batches. For this, the fol-
lowing input settings are assumed to be known: 1) the length of the time horizon (in
hours); 2) the number of products; 3) the flowrate of all pipelines; 4) the storage capac-
ity of each tank/group; 5) the initial inventory of each tank/group; 6) the upper and
lower volume of batches, depending on the products; 7) the demand of local customers
and the Downstream; 8) the matrix of product compatibility; and 9) the matrix of flush-
ing.

The following assumptions are considered: A) the phosphate slurry is considered to be a homogenous material; B) the flowrate of each pipeline is considered to be uniform; C) all tank groups have an initial inventory; D) the filling level of each tank is bounded by an upper value (90%) and a lower value (13%); E) the tanks of a group can be filled simultaneously; F) the tanks can be filled and flushed at the same time; G) the “export 1 group” at the “Terminal Station” is destined to contain the local product, which can be transferred to the “local group” via a secondary pipeline; and H) the demand is uniformly distributed over the planning horizon. The resulted schedule should contain the following elements: a) the batches to be transported through the pipelines over the planning horizon, and the product contained in each batch; b) the volume of each batch; c) the start and completion time of unloading each batch; d) the duration of unloading each bloc of a batch, and the storage group destined for each bloc; and e) the inventory level of storage groups before unloading each bloc of a batch.

The rest of the paper is arranged as follows: section 2 presents a literature review on the multi-products straight pipeline network scheduling problems; section 3 details the proposed approach; section 4 gives computational experiments; finally, section 5 provides the conclusion and perspectives of future work.

2 Literature review

The numbers of researchers interested in the multiproduct pipeline scheduling problem has considerably increased over the last few years. Many published works tackle this problem in the context of petroleum industry. To the best of our knowledge, no article related to the scheduling of phosphate slurries in a pipeline network has been published in the literature.

According to [7], the multiproduct pipeline scheduling problems could be classified conforming to the pipeline structure: straight (linear), network, etc. In this paper, our focus is on the works which deal with multiproduct pipeline network scheduling problems. These problems could also be divided into two categories, depending on the structure of the pipeline network: tree-structure, where the pipelines link between one source and multiple destinations; and mesh-structure, in which the pipelines connect multiple sources to multiple destinations.

In order to study these two categories of problems, many approaches were proposed, such as discrete event simulation tools [3], mixed integer linear and non-linear programming formulations (MILP and MINLP) [9] and [10], and hybrid approaches that combine between multiple methods [4] and [7].
[1] were among the first works which focused on the multiproduct pipeline network scheduling problems. The authors consider a mesh-structure system and propose a genetic algorithm that uses multi-objective optimization. Later, [2] presented an extensive version of [1], where they propose a hybrid method that combines between a MILP model and the genetic algorithm. The performance of the hybrid method is compared to that of the model and the algorithm. The results show that the hybrid method provides a solution with the lowest number of product changes, compared to the model and algorithm. However, no information in relation to the calculation time is presented.

Recently, [10] developed MILP model to deal with tree-structure pipeline network scheduling problem. The linear model is based on continuous time and volume representation: the time horizon is divided into several periods, the duration of which is to be determined by the model. Moreover, the model allows the loading and unloading of several batches in parallel during each period of time. The objective function is to minimize the time horizon. The model is tested by considering different instances presented in [5] and [8]. The results obtained show that the proposed model provides solutions which satisfy the demand in a shorter time horizon than the models of [5] and [8] for certain scenarios.

It is interesting to note that the cited works use different optimization criteria, so the comparison between these studies is difficult. In addition, the some of the studied articles consider the product compatibility constraint in their approach to avoid contamination between products. Other works consider inserting a plug which is a small volume that separates between two successive batches to avoid contamination. However, no information is provided on how these plugs are unloaded at the destination points.

# 3 Proposed approach

In this paper, we propose a MILP model to tackle the multiproduct tree-structure pipeline network scheduling problem. The MILP model uses continuous variables to represent time and the volume of batches. In addition, it provides the optimal schedule of batches based on only determining the unloading time of these batches. The loading time of each batch is deduced from its unloading time and transport duration. Other technical constraints regarding inventory management at the destination points are detailed in this section.

## 3.1 Objective function and decision variables

The objective function is composed of two optimization criteria: the maximization of the total volume of products, noted $vp\_total$, transported through the pipeline network over the time horizon; and the minimization of the number of blocks of batches, denoted $nb\_bloc$, by using a penalty $\rho$:

$$ (max) \quad vp\_total - \rho * nb\_bloc \qquad (1) $$
Two decision variables are considered in the model: the first one is the binary variable $y_{i,p}$ which indicates the products allocated to batches in order to create the batch sequence. It is equal to 1 if batch $i$ ($i = 1, ..., N$) contains product $p$ ($p = 0, ..., P$); 0 otherwise. The second decision variable is the binary variable $sz_{k,i,j}$ which represents the allocation of products to the tanks at the “Terminal Station”. It is equal to 1 if block $j$ ($j = 1, ..., NB$) of batch $i$ is allocated to tank/group $k$ ($k = 1, ..., 5$) during the unload-ing operation of batch $i$; 0 otherwise.

## 3.2 MILP constraints

**Constraints for product selection.** The allocation of products to batches is achieved by considering the binary variable $y_{i,p}$. In addition, the number of scheduled batches, denoted by the variable $nb$, is determined by using the binary variable $y_{i,p}$ and the maximum number of products, noted by the parameter $N$. Therefore, no products are all the batches $i$ numbered from $nb$ to $N$ (i.e., $y_{i,p} = 0 \forall i = nb, ..., N$).

**Product compatibility constraints.** The separation of consecutive batches by using a volume of water can be modeled by a matrix of product compatibility $m$, where water is considered a product numbered $p = 0$. Each element $m_{p,q}$ is equal to 1 if the sequence of products ($p, q$) is allowed. In this case, only water is compatible with each product $p$ ($p = 1, ..., P$) (i.e., $m_{0,p} = m_{p,0} = 1 \forall p = 1, ..., P$). The product compatibility constraint also consider the use of the binary variable $y_{i,p}$ to determine the possible sequences between two successive batches ($i - 1$) et $i$, containing products $p$ and $q$ respectively.

**Lot sizing constraints.** The variable $Q_i$. represents the volume of batch $i$. It must be comprised between an upper bound $Vmax_p$ and a lower bound $Vmin_p$, depending on product $p$ contained in the batch $i$, and determined by the binary variable $y_{i,p}$. In addition, the variable $BQ_{ij}$ amount to the volume of block $j$ of batch $i$. This volume is comprised between an upper bound, which is the batch volume $Q_i$, and a lower bound, which is equivalent to an hour of product pumping in the main pipeline. In addition, the sum of all block volumes $BQ_{ij}$ must be equal to the batch volume $Q_i$.

**Constraints for block unloading control.** The allocation of blocks to tanks/groups at the “Terminal Station” is represented by the binary variable $sz_{k,i,j}$. Another binary variable $z_{i,j}$ is introduced, which indicates that block $j$ exists for batch $i$. If batch $i$ contains water ($p = 0$), then only one block is considered for this batch. The block unloading constraints are summed as follow: 1) only one tank/group $k$ is allocated to each existing block $j$ of batch $i$; 2) two successive blocks $j$ and ($j + 1$) cannot be unloaded in the same tank/group $k$; 3) the variable $sz_{0,i,j}$ indicates that water is allocated to a fictive tank where it is unloaded ($sz_{k,i,j} \forall k = 1, ..., 5$); 4) if batch $i$ contains the local product ($p = 1$), then $sz_{k,i,j} = 0$ for each tank $k = 3, ..., 5$ of the “export 2 group”; 5) if batch $i$
contains an export product ($p = 2, ..., P$), then $sz_{k,i,j} = 0$ for the “local group” ($k = 1$) and the “export 1 group” ($k = 2$). Moreover, the sum of all binary variables $z_{i,j}$ is equal to the total number of blocks *nb_bloc*, which is minimized in the objective function.

**Constraints related to the unloading time and duration.** The variables $T_i$. and $D_i$ amount respectively to the time and the duration of unloading batch $i$. The unloading time $T_i$ is determined by adding to the previous one $T_{i-1}$ the duration $D_{i-1}$ of the previous batch, starting with $T_1 = 0$, since no pipeline stoppages are considered. The sum of all unloading durations $D_i$ must be equal to the time horizon $h_max$. In addition, the variable $BD_{i,j}$ represents the unloading duration of block $j$ of batch $i$. It is equal to the block volume $BQ_{ij}$ divided by the flowrate of the main pipeline *db_pp*. Moreover, the sum of all the block unloading durations $BD_{i,j}$ must be equal to the batch unloading duration $D_i$.

**Constraints related to inventory management.** Two variables are introduced for inventory management: $S_{k,i}$. represents the inventory level of tank/group $k$ before unloading batch $i$; $BS_{k,i,j}$ defines the inventory level of tank/group $k$ before unloading block $j$ of batch $i$. These inventory levels are updated by using the variable $vs_{k,i,j}$, which indicates the stock variation of tank/group $k$ while unloading block $j$ of batch $i$. The stock variation $vs_{k,i,j}$ is determined for each tank/group $k$ by considering different scenarios: 1) unloading a batch containing water ($p = 0$); 2) unloading a batch which comprises the local product ($p = 1$); 3) unloading a batch which contains an export product ($p = 2, ..., P$); 4) if the operations of filling and flushing of a tank/group are done simultaneously or separately. The inventory level $BS_{k,i,j}$ is determined by considering the previous level $BS_{k,i,j-1}$, to which is added the stock variation $vs_{k,i,j}$. In addition, the inventory level $S_{k,i+1}$ is calculated by considering the inventory level $BS_{k,i,NB}$ before unloading the last block $NB$ of the previous batch $i$, and by adding the stock variation $vs_{k,i,NB}$. Moreover, the inventory levels $S_{k,i}$ and $BS_{k,i,j}$ must be positive and lower than the maximum allowed level.

**Constraints related to the total demand of export products.** The variable $vpE_{i,p}$ amounts to the total volume of export product $p$ ($p = 2, ..., P$) contained in batch $i$. The total demand of a product $p$, denoted $dem_p$, must be higher or at least equal to the batches containing product $p$, to which is added two volumes: the variable $SvrB_p$ (where $SvrB_p \ge 0$) represents the total volume received by product $p$ if the latter has a low BPL; and the variable $SvrH_p$ (where $SvrH_p \le 0$) amounts to the total volume lost by product $p$ if the latter has a high BPL. These volumes are determined by using a flushing matrix $mr$. Each element of the matrix $mr_{p,q}$ is equal to 1 if a flushing operation must occur in “export 2 group” to change from product $p$ with low BPL to product $q$ with higher BPL.
**Constraints for total product volume.** The variable $vp_i$. refers to the volume of product contained in batch $i$ (i.e. $p = 1, ..., P$). This variable is equal to the batch volume $Q_i$ if batch $i$ is not composed of water (i.e. $y_{i,0} = 0$); and is equal to 0 if $y_{i,0} = 1$. In addition, the sum of all volumes $vp_i$ containing the local product and export products is equal to the total product volume $vp\_total$, which is maximized in the objective function.

## 4 Case study

In order to evaluate the performance of the proposed model, we consider the tree-structure pipeline network in Fig. 1. The main pipeline has a length of 187 km and an average flowrate of 4000 m³/h. The average flowrate of the secondary pipelines 1, 2 and 3 are respectively: the total demand the local product divided by the time horizon, 600 m³/h and 1000 m³/h. We use different instances generated arbitrary from a typical instance with a short term time horizon (2 days): a set of 10 instances with 3 products and two scenarios of instance 3 with respectively 4 and 5 products. For the 10 instances with 3 products, the tanks of “export group 2” are aggregated, since only one export is considered. However, these tanks are separated in the two scenarios with 4 and 5 products.

<table><caption>**Table 1.** Results provided for the instances with 3 products and 2 days</caption><thead><tr><td>Instances</td><td>Objective function</td><td>Total product volume (m³)</td><td>Total number of blocks</td><td>CPU time (s)</td><td>GAP</td></tr></thead><tbody><tr><td>1</td><td>180615.52</td><td>182715.52</td><td>21</td><td>13.6</td><td>0.00%</td></tr><tr><td>2</td><td>182800.00</td><td>185000.00</td><td>22</td><td>5.4</td><td>0.00%</td></tr><tr><td>3</td><td>184100.00</td><td>186000.00</td><td>19</td><td>4.8</td><td>0.00%</td></tr><tr><td>4</td><td>172611.54</td><td>174811.54</td><td>22</td><td>12.3</td><td>0.00%</td></tr><tr><td>5</td><td>181227.80</td><td>183327.80</td><td>21</td><td>25.5</td><td>0.00%</td></tr><tr><td>6</td><td>182700.00</td><td>185000.00</td><td>23</td><td>10.8</td><td>0.00%</td></tr><tr><td>7</td><td>184100.00</td><td>186000.00</td><td>19</td><td>5.6</td><td>0.00%</td></tr><tr><td>8</td><td>171014.20</td><td>173214.20</td><td>22</td><td>17.0</td><td>0.00%</td></tr><tr><td>9</td><td>183100.00</td><td>185000.00</td><td>19</td><td>11.1</td><td>0.00%</td></tr><tr><td>10</td><td>184000.00</td><td>186000.00</td><td>20</td><td>6.1</td><td>0.00%</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>Fig. 2. Batch schedule obtained for scenario 1 of instance 3 (with 4 products)</figcaption></figure>

Table 1 gives information about the results of the 10 instances with 3 products: the objective function; the two optimization criteria (the total product volume and the total number of blocks of batches); the CPU time and the GAP. We can note that the model provides the optimal solution of all considered instances within a CPU time of few seconds with Gurobi 9.1.1. In addition, the two scenarios of instance 3 with 4 and 5 products were also tested by the proposed model using the same solver, with a time limitation of one hour. The results showed that the solutions provided by the model at the end of the time limit is 0.16% for both scenarios. Fig. 2 represents the schedule of batches over 2 days provided by the model for the first scenario of instance 3 with 4 products.

## 5 Conclusion

In this paper, a MILP model is proposed to deal with the multiproduct tree-structure pipeline network in the context of mining industry. The model aims to maximize the volume of batches which contain phosphate products to satisfy all demands over a fixed planning horizon. It also divides each batch into several blocks in order facilitate inventory management at the destination points. Different constraints were considered in the model, such as flushing operation of tanks and the use of water as batch separator to avoid contamination. The performance of the model was evaluated using different instances over a short-term horizon. It proved to be efficient by providing optimal and near-optimal solutions of these instances.

For future work, it would be interesting to adapt some constraints of the model in order to test other instances with longer planning horizon.
References

1. de la Cruz, J. M., de Andres-Toro, B., Herrán, A., Porta, E. B., Blanco, P. F.: Multiobjective optimization of the transport in oil pipelines networks. In 2003 IEEE Conference on Emerging Technologies and Factory Automation, vol. 1, pp. 566–573. IEEE Proceedings (Cat. No. 03TH8696), (2003).

2. 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. Journal of Zhejiang University-SCIENCE A, 6(1), 9–19 (2005).

3. Mori, F.M., Lüders, R., Ramos de Arruda, L.V., Yamamoto, L., Bonacin, M.V., Polli, H.L., Aires, M.C., Bernardo, L.F.: Simulating the operational scheduling of a real-world pipeline network. Computer Aided Chemical Engineering, vol. 24, 691–696 (2007).

4. Boschetto, S., Magatão, L., Brondani, W. Neves-Jr, F. Arruda, L. Barbosa-Póvoa, A., Relvas, S.: An operational scheduling model to product distribution through a pipeline network. Industrial & Engineering Chemistry Research, 49(12), 5661–5682 (2010).

5. Lopes, T., Ciré, A., de Souza, C., Moura, A.: A hybrid model for a multiproduct pipeline planning and scheduling problem. Constraints, 15(2), 151–189 (2010).

6. Cafaro, D., Cerdá, J.: Rigorous scheduling of mesh-structure refined petroleum pipeline networks. Computers & Chemical Engineering, 38, 185–203 (2012).

7. Magatão, S., Magatão, L.; Neves-Jr, F., Arruda, L.: Novel MILP decomposition approach for scheduling product distribution through a pipeline network. Industrial & Engineering Chemistry Research, 54(18), 5077–5095 (2015).

8. Castro, P. M., Mostafaei, H.: Batch-centric scheduling formulation for treelike pipeline systems with forbidden product sequences. Computers & Chemical Engineering, 122, 2–18 (2018).

9. Q. Liao, H. Zhang, Y. Wang, W. Zhang, and Y. Liang, "Heuristic method for detailed scheduling of branched multiproduct pipeline networks," Chemical Engineering Research and Design, vol. 140, pp. 82–101, 2018.

10. Liao, Q., Castro, P.M., Liang, Y., Zhang, H.: Computationally efficient MILP model for scheduling a branched multiproduct pipeline system. Industrial & Engineering Chemistry Research, 58(13), 5236–5251. (2019).