Abstract
Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Le et al. (2013) performed computational analysis for two cases of shelf-life duration: 2 and 5 days. They concluded that the former represents a more difficult case and hence our choice.
References
Anily, S. & Federgruen, A. (1990). One warehouse multiple retailer systems with vehicle routing cost. Management Science, 36(1).
Anily, S. & Federgruen, A. (1993). Two-echelon distribution systems with vehicle routing costs and central inventories. Operations Research, 41(1).
Bertazzi, L., Paletta, G., & Speranza, M. G. (2002). Deterministic order-up-to level policies in an inventory routing problem. Transportation Science, 36(1), 119–132.
Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2), 105–119.
Diabat, A. (2014). Hybrid algorithm for a vendor managed inventory system in a two-echelon supply chain. European Journal of Operational Research. doi:10.1016/j.ejor.2014.02.061.
Diabat, A., Battaïa, O., & Nazzal, D. (2014). An improved Lagrangian relaxation-based heuristic for a joint location-inventory problem. Computers and Operations Research. doi:10.1016/j.cor.2014.03.006.
Diabat, A., Richard, J.-P., & Codrington, C. W. (2013). A Lagrangian relaxation approach to simultaneous strategic and tactical planning in supply chain design. Annals of Operations Research, 203(1), 55–80.
Federgruen, A., & Zipkin, P. (1984). A combined vehicle routing and inventory allocation problem. Operations Research, 32(5), 1019–1037.
Federgruen, A., Prastacos, G., & Zipkin, P. (1986). An allocation and distribution model for perishable products. Operations Research, 34, 75–82.
Francis, P., Smilowitz, K., & Tzur, M. (2006). The period vehicle routing problem with service choice. Transportation Science, 40(4).
Francis, P., Smilowitz, K., & Tzur, M. (2007). Flexibility and complexity in periodic distribution problems. Naval Research Logistics.
Fry, M.J. (2010). Vendor-managed inventory. Wiley Encyclopedia of Operations Research and Management Science.
Gendreau, M., Hertz, A., & Laporte, G. (1992). New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 40, 1086–1094.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276–1290.
Ghare, P. M., & Schrader, G. F. (1963). A model for exponentially decaying inventory. Journal of Industrial Engineering, 14(5), 238–243.
Le, T., Diabat, A., Richard, J.-P., & Yih, Y. (2013). A column generation-based heuristic algorithm for an inventory routing problem with perishable goods. Optimization Letters, 7(7), 1481–1502.
Lee, H. L., Padmanabhan, V., & Whang, S. (1997). Information distortion in a supply chain: The bullwhip effect. Management Science, 43(4), 546–558.
Ordónez, F., Sungur, I., & Dessouky, M. (2007). A priori performance measures for arc-based formulations of vehicle routing problem. Transportation Research Record: Journal of the Transportation Research Board, 2032(1), 53–62.
Sarmiento, A. M., & Nagi, R. (1999). A review of integrated analysis of production-distribution systems. IIE Transactions, 31(11), 1061–1074.
Simchi-Levi, D. (2009). Designing and managing the supply chain concepts strategies and case studies. Noida: Tata McGraw-Hill Education.
Thomas, D. J., & Griffin, P. M. (1996). Coordinated supply chain management. European Journal of Operational Research, 94(1), 1–15.
Viswanathan, S., & Mathur, K. (1997). Integrating routing and inventory decisions in one-warehouse multiretailer multiproduct distribution system. Management Science, 43(3), 294–312.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Diabat, A., Abdallah, T. & Le, T. A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods. Ann Oper Res 242, 373–398 (2016). https://doi.org/10.1007/s10479-014-1640-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-014-1640-4