We study the distribution problem of a single commodity from one warehouse to n geographically dispersed retailers by a fleet of capacitated vehicles. Each of the retailers faces a continuous constant and deterministic demand rate over the infinite horizon. In addition, each of the retailers is characterized by its own inventory holding cost rate. The objective is to obtain a routing and replenishment strategy which minimizes the long-run average transportation and holding cost. We restrict ourselves to a class of strategies which partitions the overall region into subregions. A retailer can be assigned to several subregions: each subregion is responsible for a certain fraction of the sales of each of its retailers. We first show that the optimal solution can be bounded from below by a special partitioning problem whose solution can be given in a closed form. We then present a simple heuristic which is shown to converge to the lower-bound almost surely under mild probabilistic conditions, when the number of retailers is increased to infinity.
