Analysis of practical policies for a single link distribution system

In this paper we consider a transportation problem where several products have to be shipped from an origin to a destination by means of vehicles with given capacity. Each product is made available at the origin and consumed at the destination at the same constant rate. The time between consecutive shipments must be greater than a given minimum time. All demand needs to be satisfied on time and backlogging is not allowed. The problem is to decide when to make the shipments and how to load the vehicles with the objective of minimizing the long run average of the transportation and the inventory costs at the origin and at the destination over an infinite horizon. We consider two classes of practical shipping policies, the zero inventory ordering (ZIO) policies and the frequency-based periodic shipping (FBPS) policies. We show that, in the worst-case, the Best ZIO policy has a performance ratio of root 2. A better performance guarantee of 16 root 3045/255 - 37/17 approximate to 1.286 is shown for the best possible FBPS policy. The performance guarantees are tight. Finally, combining the Best ZIO and the Best FBPS policies, a policy that guarantees a 4 performance is obtained. Computational results show that this policy gives an average percent optimality gap on all the tested instances of <1%. (c) 2007 Wiley Periodicals, Inc.