Improved rounding procedures for the discrete version of the capacitated EOQ problem

We consider a transportation problem where different products have to be shipped from an origin to a destination by means of vehicles with given capacity. The production rate at the origin and the demand rate at the destination are constant over time and identical for each product. The problem consists in deciding when to make the shipments and how to fill the vehicles, with the objective of minimizing the sum of the average transportation and inventory costs at the origin and at the destination over an infinite horizon. This problem is the well known capacitated EOQ (economic order quantity) problem and has an optimal solution in closed form. In this paper we study a discrete version of this problem in which shipments are performed only at multiples of a given minimum time. It is known that rounding-off the optimal solution of the capacitated EOQ problem to the closest lower or upper integer value gives a tight worst-case ratio of 2, while the best among the possible single frequency policies has a performance ratio of 5/3. We show that the 5/3 bound can be obtained by a single frequency policy based on a rounding procedure which considers classes of instances and, for each class, identifies a shipping frequency by rounding-off in a different way the optimal solution of the capacitated EOQ problem. Moreover, we show that the bound can be reduced to 3/2 by using two shipping frequencies, obtained by a rounding procedure, in one class of instances only. (c) 2004 Elsevier B.V. All rights reserved.