Heuristics for a one-warehouse multiretailer distribution problem with performance bounds

We investigate the one warehouse multiretailer distribution problem with traveling salesman lour vehicle routing costs. Ne model the system in the framework of the more general production/distribution system with arbitrary non-negative monotone joint order costs. We develop polynomial time heuristics whose policy costs are provably close to the cost of an optimal policy. In particular, we show that given a submodular function which is close to the true order cost then we can find a power-of-two policy whose cost is only moderately greater than the cost of an optimal policy. Since such submodular approximations exit for traveling salesman tour vehicle routing costs we present a detailed description of heuristics for the one warehouse multiretailer distribution problem. We formulate a nonpolynomial dynamic program that computes optimal power-of-two policies for the one warehouse multiretailer system assuming only that the order costs are non-negative monotone. Finally, we perform computational tests which compare our heuristics to optimal power of two policies for problems of up to sixteen retailers. We also perform computational tests on larger problems; these tests give us insight into what policies one should employ.