Probabilistic analyses and practical algorithms for inventory-routing models

We consider a distribution system consisting of a single warehouse and many geographically dispersed retailers. Each retailer faces demands for a single item which arise at a deterministic, retailer specific rate. The retailers' stock is replenished by a fleet of vehicles of limited capacity, departing and returning to the warehouse and combining deliveries into efficient routes. The cost of any given route consists of a fixed component and a component which is proportional with the total distance driven. Inventory costs are proportional with the stock levels. The objective is to identify a combined inventory policy and a routing strategy minimizing system-wide infinite horizon costs. We characterize the asymptotic effectiveness of the class of so-called Fixed Partition policies and those employing Zero Inventory Ordering. We provide worst case as well as probabilistic bounds under a variety of probabilistic assumptions. This insight is used to construct a very effective algorithm resulting in a Fixed Partition policy which is asymptotically optimal within its class. Computational results show that the algorithm is very effective on a set of randomly generated problems.