Combined Routing and Inventory Allocation Problems: Bounds and Heuristics

摘要

The paper addresses the problem of allocating inventory and delivering stocks from a central depot to several retail outlets. Each outlet faces a random demand, so the allocations must balance the expected costs of over- and under-supply. The deliveries are made by a fleet of vehicles whose routes must be planned. The overall problem is to minimize transportation plus allocation costs. Assuming identical cost parameters and demand distributions for all outlets, the authors derive upper and lower bounds for the expected minimal costs which are efficiently computable and asymptotically accurate. The authors also describe a number of asymptotically optimal heuristics and epsilon-approximation schemes, both with polynomial running times. Finally, the authors exhibit a number of interesting qualitative properties shared by the proposed heuristics.