(612b) A Novel Two-Stage Scheduling Algorithm for Branched Pipeline Systems

A multiproduct pipeline network is a complex and massive system that plays an important role in moving large volumes of petroleum derivatives from refineries to depots over long distances. The main goal of pipeline operation is to generate the detailed scheduling plan that meets downstream market demand on time while considering refinery production and pipeline transportation capacity, inventory and flowrate limits. Specifically, the following decisions are involved: (a) finding the start and end times of each pumping run; (b) the quantity and sequence of batches to inject/download at the input/output nodes.

In terms of topology, the most-studied problem refers to the branched structure with a single input node and multiple output nodes. With the increase in the number of nodes along the pipeline and the scheduling horizon, the size of the mathematical problem increases exponentially, resulting in high computational workload or failure to find a feasible solution [1]. Improving operations while rapidly adapting to changes in production and market environment can increase the profit of oil companies by millions of dollars.

To generate the detailed pipeline scheduling plan in a reasonable computational time, many researchers have developed decomposition algorithms. The most common is a two-level hierarchical method, with each level solving a mixed-integer linear programming (MILP) formulation based on a continuous-time representation. The higher-level model takes many key decisions into account, while the lower-level model generates the detailed schedule. For instance, Cafaro et al. [2,3] obtained the detailed pipeline scheduling plan by sequentially solving a continuous-time model at the upper and lower levels. In [3], the upper level provides an aggregate plan by only considering maximum flowrate limits in segments and nodes, while the lower-level model provides the detailed schedule by also considering lower flowrate limits. Each time slot from the upper-level is subdivided at the lower-level. However, if the division of the upper-level is not appropriate, we may fail to generate a feasible solution by the lower-level model, particularly for systems with a narrow flowrate range.

Aiming at solving the problem just described, this paper proposes a novel two-stage algorithm featuring continuous-time models that allow multiple batches to be injected/delivered over a slot [4]. The first-stage model reduces the complexity by neglecting the lower flowrate limits, enforced by big-M constraints, and minimizes the makespan. The second-stage model works with the first-stage assignments and with an extended time grid. Coupled with a backtracking mechanism, the proposed algorithm can significantly reduce computational time and improve the pipeline transportation capacity. We use four benchmark instances from the literature [5] to test and validate the effectiveness and superiority of the method proposed in this paper. Compared to the literature, a new optimal solution is reported in one case, while the computational time is reduced by a few orders of magnitude in the other cases.

Acknowledgments: Financial support from the National Natural Science Foundation of China, Grant No. 51874325 and Fundação para a Ciência e Tecnologia (FCT) through projects CEECIND/00730/2017 and UIDB/04561/2020.

References:

[1] Liao, Q., Liang, Y., Xu, N., Zhang, H., Wang, J., & Zhou, X. An MILP approach for detailed scheduling of multi-product pipeline in pressure control mode. Chemical Engineering Research and Design 2018, 136, 620-637.

[2] Cafaro, V. G., Cafaro, D. C., Méndez, C. A., & Cerdá, J. Detailed Scheduling of Operations in Single-Source Refined Products Pipelines. Industrial & Engineering Chemistry Research 2011, 50, 6240-6259.

[3] Cafaro, V. G., Cafaro, D. C., Méndez, C. A., & Cerdá, J. Detailed Scheduling of Single-Source Pipelines with Simultaneous Deliveries to Multiple Offtake Stations. Industrial & Engineering Chemistry Research 2012, 51, 6145-6165.

[4] Liao, Q., Castro, P. M., Liang, Y., & Zhang, H. Computationally Efficient MILP Model for Scheduling a Branched Multiproduct Pipeline System. Industrial & Engineering Chemistry Research 2019, 58, 5236-5251.

[5] Castro, P. M., & Mostafaei, H. Batch-centric scheduling formulation for treelike pipeline systems with forbidden product sequences. Computers & Chemical Engineering 2019, 122, 2-18.