An inventory routing problem in crude oil transportation is studied, in which crude oil is transported from a supply center to multiple customer harbors to satisfy their demands over multiple periods. In the problem, a heterogeneous fleet of tankers consisting of tankers owned by a distributor and tankers rented from a third party, a pipeline, and multiple types of routes are considered; both inventory level and shortage level at each customer harbor are limited. The objective is to determine for each period over a given time horizon the number of tankers of each type to be rented/returned at the supply center, the number of tankers of each type to be dispatched on each route, and the quantity of crude oil flowing through the pipeline that minimizes the total logistics cost. After formulating the problem as a mixed integer programming problem, a Lagrangian relaxation approach is developed for finding a near optimal solution of the problem. The approach is also applied to a variant of the problem in which both fully and partially loaded tankers are allowed in the transportation of crude oil. Numerical experiments show that this approach outperforms an existing meta-heuristic algorithm, especially for the instances of large sizes. (C) 2011 Elsevier Ltd. All rights reserved.