Asymptotic Analysis of Periodic Policies for the Inventory Routing Problem

作者：Chan Lap Mui Ann; Speranza M Grazia^*; Bertazzi Luca

来源：Naval Research Logistics, 2013, 60(7): 525-540.

DOI：10.1002/nav.21550

• inventory routing
• fixed partition periodic policies
• partition based periodic policies
• asymptotic performance
• heuristic algorithms

In this article, a distribution system is studied where the sum of transportation and inventory costs is to be minimized. The inventory holding cost is assumed to be the same for all retailers. A fixed partition (FP) periodic policy is proposed with tight asymptotic worst-case performance of 3/2 with respect to the best possible policy. This bound cannot be improved in the class of FP periodic policies. In partition-based PB policies, the retailers are first partitioned into sets and then the sets are grouped in such a way that sets of retailers within a group are served together at selected times. A PB periodic, policy is presented with tight worst-case asymptotic performance of 11-4 root 6 approximate to 1.202 with respect to the best possible policy. This latter performance improves the worst-case asymptotic performance of root 2 of the previously best known policy for this problem. We also show that the proposed PB periodic policy has the best worst-case asymptotic performance within the class of PB policies. Finally, practical heuristics inspired by the analyzed policies are designed and tested. The asymptotic worst-case performances of the heuristics are shown to be the same of those of the analyzed policies. Computational results show that the heuristics suggested are less than 6.4% on average from a lower bound on the optimal cost when 50 or more retailers are involved.

• 出版日期2013-10