Efficient formulation for transportation scheduling of single refinery multiproduct pipelines

Multiproduct pipeline transportation scheduling is a complex operations research problem that is characterized by the movement of the cargo rather than the carrier. Hence, it cannot be solved using vehicle routing methods. While most formulations for short-term scheduling adopt a continuous-time representation, they often lead to suboptimal solutions because of the dependence on the number of time slots in the grid, which is difficult to predict. Furthermore, some of these formulations have poor linear relaxations due to the presence of inefficient big-M constraints. In this paper, we develop a discrete-time mixed integer linear programming (MILP) model for the detailed scheduling of a straight pipeline with a single refinery and multiple depots. The proposed formulation rigorously detects interface material generated between adjacent products and considers planned shutdowns in pipeline segments due to maintenance operations, as well as local market demands occurring at multiple intermediate due dates. The main novelty is that continuous tasks can span multiple time slots to enforce minimum batch sizes on injection and delivery nodes, which allows for the model to generate better schedules than those obtained with previously proposed formulations. To ensure an efficient model by design, we rely on generalized disjunctive programming (GDP) and on the convex hull reformulation of disjunctions, which results in stronger and often more computationally efficient formulations. We present numerical results for a set of benchmark instances and show that the proposed model applies to large-scale industrial cases.