We consider the Inventory-Routing Problem (IRP) where n geographically dispersed retailers must be supplied by a central facility. The retailers experience demand for the product at a deterministic rate and incur holding costs for keeping inventory. Distribution is performed by a fleet of capacitated vehicles. The objective is to minimize the average transportation and inventory costs per unit time over the infinite horizon. We focus on the set of Fixed Partition Policies (FPP). In an FPP, the retailers are partitioned into disjoint and collectively exhaustive sets. Each set of retailers is served independently of the others and at its optimal replenishment rate. Previous research has measured the effectiveness of an FPP solution relative to a lower bound over all policies. We propose an additional measure that is relative to the optimal FPP. In this paper we construct a polynomial-time partitioning scheme that is shown to yield an FPP whose cost is asymptotically within 1.5% + ε of the cost of an optimal FPP, for arbitrary ε > 0. In addition, in some cases, our polynomial-time scheme yields an FPP whose cost is asymptotically within 1.5% + ε of the minimal policy's cost (over all feasible policies).
