Abstract

Network design models have wide applications in telecommunications and transportation planning; see, for example, the survey articles by Magnanti and Wong (1984), Minoux (1989), Chapter 16 of the book by Ahuja, Magnanti and Orlin (1993), Section 13 of Ahuja et al. (1995). In particular, Gavish (1991) and Balakrishnan et al. (1991) present reviews of important applications in telecommunications. In many of these applications, it is required to send flows (which may be fractional) to satisfy demands given arcs with existing capacities, or to install, in discrete amounts, additional facilities with fixed capacities. In doing so, one pays a price not only for routing flows, but also for using an arc or installing additional facilities. The objective is then to determine the optimal amounts of flows to be routed and the facilities to be installed. Document type: Part of book or chapter of book

Abstract

International audience; 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.