Premium
Decomposing inventory routing problems with approximate value functions
Author(s) -
Toriello Alejandro,
Nemhauser George,
Savelsbergh Martin
Publication year - 2010
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.20433
Subject(s) - mathematical optimization , routing (electronic design automation) , piecewise linear function , sequence (biology) , computer science , piecewise , function (biology) , decomposition , value (mathematics) , dynamic programming , bellman equation , quality (philosophy) , mathematics , operations research , computer network , mathematical analysis , ecology , philosophy , geometry , epistemology , evolutionary biology , machine learning , biology , genetics
We present a time decomposition for inventory routing problems. The methodology is based on valuing inventory with a concave piecewise linear function and then combining solutions to single‐period subproblems using dynamic programming techniques. Computational experiments show that the resulting value function accurately captures the inventory's value, and solving the multiperiod problem as a sequence of single‐period subproblems drastically decreases computational time without sacrificing solution quality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010