Sequencing inputs to multi-commodity pipelines

This paper examines the problem of sequencing the input of commodities, e.g. petroleum products, to a pipeline so that a surrogate for pumping and maintenance costs is minimized. This problem is complicated by the need to impose a discrete framework which handles the sequencing choices on a continuous flow problem. By focusing on the discrete aspects of the problem, the proposed model allows decomposition of the sequencing problem into subproblems which can be easily priced out in a branch-and-bound algorithm. Computational results on data generated to mimic a large U.S. petroleum pipeline are presented. These results show that the branch-and-bound algorithm only explores a small region of the solution space within a reasonable amount of time, less than 2.5 minutes to optimally sequence deliveries to twenty-four destinations.