×

Heuristics for dynamic and stochastic inventory-routing. (English) Zbl 1348.90024

Summary: The combination of inventory management and vehicle routing decisions yields a difficult combinatorial optimization problem called the Inventory-Routing Problem (IRP). This problem arises when both types of decisions must be made jointly, which is the case in vendor-managed inventory systems. The IRP has received significant attention in recent years, with several heuristic and exact algorithms available for its static and deterministic versions. In the dynamic version of the IRP, customer demands are gradually revealed over time and planning must be made at the beginning of each of several periods. In this context, one can sometimes take advantage of stochastic information on demand through the use of forecasts. We propose different heuristic policies to handle the dynamic and stochastic version of the IRP. We perform an extensive computational analysis on randomly generated instances in order to compare several solution policies. Amongst other conclusions we show that it is possible to take advantage of stochastic information to generate better solutions albeit at the expense of more computing time. We also find that the use of a longer rolling horizon step does not help improve solutions. Finally, we show that ensuring consistent solutions over time increases the cost of the solutions much more under a dynamic environment than in a static setting.

MSC:

90B05 Inventory, storage, reservoirs
90B06 Transportation, logistics and supply chain management
90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adelman, D., A price-directed approach to stochastic inventory/routing, Oper Res, 52, 4, 499-514 (2004) · Zbl 1165.90302
[2] Adelman, D.; Klabjan, D., Computing near-optimal policies in generalized joint replenishment, INFORMS J Comput, 24, 1, 148-164 (2012) · Zbl 1460.90007
[3] Adulyasak, Y.; Cordeau, J.-F.; Jans, R., Optimization-based adaptive large neighborhood search for the production routing problem, Transp Sci, 48, 1, 20-45 (2014)
[4] Andersson, H.; Hoff, A.; Christiansen, M.; Hasle, G.; Løkketangen, A., Industrial aspects and literature surveycombined inventory management and routing, Comput Oper Res, 37, 9, 1515-1536 (2010) · Zbl 1190.90012
[5] Archetti, C.; Bertazzi, L.; Laporte, G.; Speranza, M. G., A branch-and-cut algorithm for a vendor-managed inventory-routing problem, Transp Sci, 41, 3, 382-391 (2007)
[6] Archetti, C.; Bertazzi, L.; Hertz, A.; Speranza, M. G., A hybrid heuristic for an inventory routing problem, INFORMS J Comput, 24, 1, 101-116 (2012) · Zbl 1460.90009
[7] Arrow, K. J.; Harris, T.; Marschak, J., Optimal inventory policy, Econometrica, 19, 3, 250-272 (1951) · Zbl 0045.23205
[9] Axsäter, S., Inventory control - international series in operations research & management science, vol. 90 (2006), Springer: Springer New York
[10] Bard, J. F.; Nananukul, N., A branch-and-price algorithm for an integrated production and inventory routing problem, Comput Oper Res, 37, 12, 2202-2217 (2010) · Zbl 1231.90010
[11] Bartodziej, P.; Derigs, U.; Malcherek, D.; Vogel, U., Models and algorithms for solving combined vehicle and crew scheduling problems with rest constraintsan application to road feeder service planning in air cargo transportation, OR Spectr, 31, 2, 405-429 (2009) · Zbl 1160.90469
[12] Berbeglia, G.; Cordeau, J.-F.; Laporte, G., Dynamic pickup and delivery problems, Eur J Oper Res, 202, 1, 8-15 (2010) · Zbl 1176.90048
[13] Bertazzi, L.; Paletta, G.; Speranza, M. G., Deterministic order-up-to level policies in an inventory routing problem, Transp Sci, 36, 1, 119-132 (2002) · Zbl 1065.90500
[14] Bertazzi, L.; Savelsbergh, M.; Speranza, M. G., Inventory routing, (Golden, B. L.; Raghavan, S.; Wasil, E. A., The Vehicle Routing Problem (2008), Springer: Springer New York), 49-72 · Zbl 1187.90039
[15] Bertazzi, L.; Bosco, A.; Guerriero, F.; Laganà, D., A stochastic inventory routing problem with stock-out, Transp Res Part C: Emerg Technol, 27, 1, 89-107 (2013)
[16] Bertsekas, D. P., Dynamic programming and optimal controlvol. 2 (2012), Athena Scientific: Athena Scientific Belmont, MA
[17] Bhatnagar, R.; Teo, C.-C., Role of logistics in enhancing competitive advantagea value chain framework for global supply chains, Int J Phys Distrib Logist Manag, 39, 3, 202-226 (2009)
[18] Campbell, A. M.; Clarke, L.; Kleywegt, A. J.; Savelsbergh, M. W.P., The inventory routing problem, (Crainic, T. G.; Laporte, G., Fleet management and logistics pages (1998), Springer: Springer Boston), 95-113 · Zbl 0972.90500
[19] Caplin, A. S., The variability of aggregate demand with (S,s) inventory policies, Econometrica, 53, 6, 1395-1409 (1985) · Zbl 0587.90036
[20] Coelho, L. C.; Laporte, G., The exact solution of several classes of inventory-routing problems, Comput Oper Res, 40, 2, 558-565 (2013) · Zbl 1349.90016
[21] Coelho, L. C.; Laporte, G., A branch-and-cut algorithm for the multi-product multi-vehicle inventory-routing problem, Int J Prod Res, 51, 23-24, 7156-7169 (2013)
[23] Coelho, L. C.; Cordeau, J.-F.; Laporte, G., The inventory-routing problem with transshipment, Comput Oper Res, 39, 11, 2537-2548 (2012) · Zbl 1251.90030
[24] Coelho, L. C.; Cordeau, J.-F.; Laporte, G., Consistency in multi-vehicle inventory-routing, Transp Res Part C: Emerg Technol, 24, 1, 270-287 (2012)
[25] Coelho, L. C.; Cordeau, J.-F.; Laporte, G., Thirty years of inventory-routing, Transp Sci, 48, 1, 1-19 (2014)
[26] Dezső, B.; Jüttner, A.; Kovács, P., LEMON - an open source C++ graph template library, Electron Notes Theor Comput Sci, 264, 5, 23-45 (2011)
[28] Ghiani, G.; Guerriero, F.; Laporte, G.; Musmanno, R., Real-time vehicle routingsolutions concepts, algorithms and parallel computing strategies, Eur J Oper Res, 151, 1, 1-11 (2003) · Zbl 1033.90014
[29] Goetschalckx, M., Supply chain engineering, International series in operations research & management science, vol. 161 (2011), Springer: Springer New York
[30] Goodwin, P.; Önkal, D.; Thomson, M., Do forecasts expressed as prediction intervals improve production planning decisions?, Eur J Oper Res, 205, 1, 195-201 (2010)
[31] Hewitt, M.; Nemhauser, G. L.; Savelsbergh, M. W.P., Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem, INFORMS J Comput, 22, 2, 314-325 (2010) · Zbl 1243.90031
[32] Hvattum, L. M.; Løkketangen, A.; Laporte, G., Scenario tree-based heuristics for stochastic inventory-routing problems, INFORMS J Comput, 21, 2, 268-285 (2009) · Zbl 1243.90015
[33] Hyndman, R. J.; Khandakar, Y., Automatic time series forecastingthe forecast package for R, J Stat Softw, 27, 3, 1-22 (2008)
[34] Hyndman, R. J.; Koehler, A. B.; Ord, J. K.; Snyder, R. D., Forecasting with exponential smoothing: the state space approach (2008), Springer-Verlag: Springer-Verlag Berlin · Zbl 1211.62165
[36] Jaillet, P.; Bard, J. F.; Huang, L.; Dror, M., Delivery cost approximations for inventory routing problems in a rolling horizon framework, Transp Sci, 36, 3, 292-300 (2002) · Zbl 1134.90307
[37] Kleywegt, A. J.; Nori, V. S.; Savelsbergh, M. W.P., The stochastic inventory routing problem with direct deliveries, Transp Sci, 36, 1, 94-118 (2002) · Zbl 1065.90508
[38] Kleywegt, A. J.; Nori, V. S.; Savelsbergh, M. W.P., Dynamic programming approximations for a stochastic inventory routing problem, Transp Sci, 38, 1, 42-70 (2004)
[39] Laporte, G.; Musmanno, R.; Vocaturo, F., An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands, Transp Sci, 44, 1, 125-135 (2010)
[40] Lee, H. L.; Seungjin, W., The whose, where and how of inventory control design, Supply Chain Manag Rev, 12, 8, 22-29 (2008)
[41] Makridakis, S. G.; Wheelwright, S. C.; Hyndman, R. J., Forecasting: methods and applications (1998), Wiley: Wiley New York
[42] Maniezzo, V.; Stützle, T.; Voß, S., Matheuristics: hybridizing metaheuristics and mathematical programming (2009), Springer: Springer New York · Zbl 1179.90007
[43] Nonås, L. M.; Jörnsten, K., Optimal solution in the multi-location inventory system with transshipments, J Math Model Algorithms, 6, 1, 47-75 (2007) · Zbl 1146.90009
[44] Özer, Ö., Inventory managementinformation, coordination, and rationality, (Kempf, K. G.; Keskinocak, P.; Uzsoy, R., Planning production and inventories in the extended enterprise, International series in operations research & management science, vol. 151 (2011), Springer: Springer New York), 321-365
[45] Paterson, C.; Kiesmüller, G.; Teunter, R.; Glazebrook, K., Inventory models with lateral transshipmentsa review, Eur J Oper Res, 210, 2, 125-136 (2011)
[46] Pepin, A.-S.; Desaulniers, G.; Hertz, A.; Huisman, D., A comparison of five heuristics for the multiple depot vehicle scheduling problem, J Sched, 12, 1, 17-30 (2009) · Zbl 1168.90464
[47] Powell, W. B., Approximate dynamic programming, Wiley series in probability and statistics (2007), Wiley: Wiley New Jersey
[48] Psaraftis, H. N., Dynamic vehicle routing problems, (Golden, B. L.; Assad, A. A., Vehicle routingmethods and studies (1998), North-Holland: North-Holland Amsterdam), 223-248
[50] Rey, D.; Neuhäuser, M., Wilcoxon-signed-rank test, (Lovric, M., International encyclopedia of statistical science (2011), Springer: Springer Berlin), 1658-1659
[51] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp Sci, 40, 4, 455-472 (2006)
[53] Silver, E. A.; Pyke, D. F.; Peterson, R., Inventory management and production planning and scheduling (1998), Wiley: Wiley New York
[54] Solyalı, O.; Süral, H., A branch-and-cut algorithm using a strong formulation and an a priori tour based heuristic for an inventory-routing problem, Transp Sci, 45, 3, 335-345 (2011)
[55] Toriello, A.; Nemhauser, G. L.; Savelsbergh, M. W.P., Decomposing inventory routing problems with approximate value functions, Nav Res Logist, 57, 8, 718-727 (2010) · Zbl 1202.90021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.