Premium
Asymptotic analysis of periodic policies for the inventory routing problem
Author(s) -
Chan Lap Mui Ann,
Speranza M. Grazia,
Bertazzi Luca
Publication year - 2013
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21550
Subject(s) - heuristics , partition (number theory) , asymptotic analysis , upper and lower bounds , mathematical optimization , computer science , routing (electronic design automation) , class (philosophy) , mathematics , operations research , mathematical economics , combinatorics , computer network , mathematical analysis , artificial intelligence
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 6 ≈ 1.202 with respect to the best possible policy. This latter performance improves the worst‐case asymptotic performance of2of 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 Wiley Periodicals, Inc. Naval Research Logistics 00: 000–000, 2013