Dynamic Loading and Unloading of Liquids into Tanks

We consider the problem appearing in the loading and unloading of crude oil into storage tanks at an oil terminal or port. The numbers, sizes and initial condition of the storage tanks are known and what is required is to perform a given sequence of loading and unloading operations involving several types of crude into and out of these tanks. The different types of crude cannot be mixed, and what is required is to decide which crude is to be loaded (unloaded) into (out of) which tanks so as to minimize the value of an objective function. The objective considered is a general integral criterion and includes a criterion based only on the terminal state of the tanks as a special case. The problem is formulated as a mixed integer program in which the continuous variables are only involved in a subproblem with a network-flow structure. A branch-and-bound algorithm is described which makes use of graph theoretic lower bounds and dominance conditions to limit the search. The algorithm was tested on a number of real-world problems involving up to 45 loading and/or unloading operations, 11 types of crude and 20 storage tanks.