Analysis of Direct Shipping Policies in an Inventory Routing Problem with Discrete Shipping Times

We consider the problem in which several products have to be shipped from a supplier to a set of retailers over an infinite time horizon. Each product is made available at the supplier and absorbed by each retailer at given constant production and consumption rates. For each product, the unit inventory cost at the supplier is equal to the unit inventory cost at the retailers. Shipments can be performed in each discrete time instant by a fleet of vehicles of given transportation capacity and routing is allowed. The aim is to determine shipping policies that minimize the sum of transportation cost and inventory cost both at the supplier and at the retailers. We study direct shipping policies, i.e., policies in which each retailer is served independently. We show the worst-case performance of the best single, best double, best triple, best frequency-based, and optimal direct shipping policies. In each of these policies each link is optimized independently. We prove that, in the worst case, the ratio between the cost of the optimal direct shipping policy and the optimal cost of the problem in which routing is allowed-i.e., the worst-case performance bound of this policy-is not greater than two whenever the unit volume on each link is not lower than 1/4 of the vehicle capacity. Moreover, if the unit volume is not lower than the capacity, the bound is about 1.21. These bounds are tight and obtained by applying frequency-based policies that make use of at most three different shipping frequencies and cannot be improved by allowing more frequencies or using time-based policies on each link. Computational results show that the best among the frequency-based direct shipping policies used to obtain the worst-case results gives an average percent increase error, with respect to a lower bound on the optimal cost of the problem in which routing is allowed, of 6.44% on a large set of randomly generated problem instances.