An-effective lagrangian relaxation approach for multiple-mode crude oil transportation optimization

In this paper, an crude oil transportation planning problem for an oil distributor is studied, in which crude oil is transported by tankers and pipelines from an unlimited supply center to a set of customer harbors to satisfy their dynamic demands over multiple periods. In the problem, inventory level and shortage level of crude oil at each customer are limited; both fully loaded and partially loaded tankers are allowed in the transportation of crude oil, and part of the tankers may be rented from a third party. The objective is to determine in each period the schedule of tankers and pipelines and the number of tankers of each type to be rented/returned at the supply center in order to minimize the total logistics cost. After formulating the problem as a mixed integer programming problem, we generalize an existing Lagrangian relaxation approach that only allows fully loaded tanks to one that allows both fully loaded and partially loaded tankers of the problem. Numerical experiments show that the new approach can find a near optimal solution of the problem of large size in a reasonable computation time.